
Endre Szemerédi
Hungarian mathematician known for combinatorics and theoretical computer science, Abel Prize 2012 · 1940
- Born
- August 21, 1940
- Country
- Hungary, United States
- Section
- Mathematics
Biography
Endre Szemerédi is a Hungarian-American mathematician whose work in combinatorics, the branch of mathematics that studies how finite collections of objects can be counted, arranged and combined, has shaped the field for decades. Born in 1940, he received the Abel Prize in 2012 for his contributions to discrete mathematics and theoretical computer science. His results link number theory, geometry, graph theory and the analysis of algorithms.
He was born in Budapest. His parents wanted him to become a doctor, so he enrolled in a medical college, but he left after six months. In an interview he explained that he did not feel sure he could handle work carrying such responsibility. He then studied at the Faculty of Sciences of Eötvös Loránd University in Budapest, where his mathematical advisers were Paul Erdős and András Hajnal, two central figures of Hungarian mathematics. Erdős in particular shaped his way of approaching combinatorial problems.
He received his doctorate from Moscow State University under Israel Gelfand. The usual account is that this choice came from a mix-up: Szemerédi had wanted to work with Alexander Gelfond, but the name was misspelled and the result was Gelfand. The story is often repeated, but it should be treated with some caution, since it rests on anecdote rather than on a documented record.
His best-known breakthrough came in 1975. He proved a conjecture that Erdős and Pál Turán had posed decades earlier: if a sequence of natural numbers has positive upper density, meaning that it occupies a non-negligible share of the integers, then it contains arithmetic progressions of every length. An arithmetic progression is a list of numbers spaced by the same step, such as 3, 7, 11, 15. The result is now called Szemerédi's theorem. To prove it, he introduced an auxiliary tool, the Szemerédi regularity lemma, which splits a graph into parts that behave in a nearly uniform way. That lemma became a basic instrument of combinatorics and is used in testing graph properties and in the theory of graph limits.
His collaborations were numerous. With Miklós Ajtai he proved the corners theorem, a step toward higher-dimensional versions of his theorem. With Ajtai and János Komlós he bounded the Ramsey number R(3,t) and built a sorting network of optimal depth. With Ajtai, Václav Chvátal and Monroe Newborn he proved the crossing number inequality, which gives a lower bound on how many times the edges of a graph must cross when it is drawn in the plane. With Erdős he proved the Erdős–Szemerédi theorem on the number of sums and products in a finite set. Together with Wolfgang Paul, Nick Pippenger and William Trotter he established a separation between classes of computational problems, in the spirit of the famous P versus NP question.
Much of his career unfolded in the United States. Since 1986 he has held a chair in computer science at Rutgers University in New Jersey, and he spent visiting periods at Stanford, McGill, the University of South Carolina and the University of Chicago. He also kept close ties with the Alfréd Rényi Institute of Mathematics in Budapest. He is married to Anna Kepes, and they have five children.
His legacy is twofold. He helped turn combinatorics into a central area of mathematics, a point the Abel committee singled out. His tools, such as the regularity lemma, now serve theoretical computer science and fields ranging from cryptography to network analysis. In 2010 a conference in Budapest marked his 70th birthday, and the volume An Irregular Mind gathered papers in his honour.
Main contributions
- 1975Szemerédi's theorem: if a sequence of natural numbers has positive upper density, it contains arithmetic progressions of any length.
- 1975Szemerédi regularity lemma: a tool that splits a graph into nearly uniform parts and is now basic in combinatorics.
- 2012Abel Prize, awarded for his contributions to discrete mathematics and theoretical computer science.
- Corners theorem, with Miklós Ajtai, a step toward higher-dimensional generalizations of his progression theorem.
- Crossing number inequality, with Ajtai, Chvátal and Newborn, which bounds how many times the edges of a graph cross when drawn in the plane.
- Erdős–Szemerédi theorem, with Paul Erdős, on the number of sums and products in a finite set.
Teachers and students
Studied under:
Taught:
Trivia and anecdotes
A medical career cut short
He enrolled in medicine at his parents' wish, but left after six months, as he explained in an interview.
A supervisor by misspelling
According to a common account, he wanted to work with Alexander Gelfond, but a misspelling led him to Israel Gelfand. The story is repeated but not firmly documented.
Their contemporaries
While Endre Szemerédi was alive (1940–)…
Alive at the same time
Discovered or invented in those years
- 1945ComputerA programmable machine that takes in data, processes it by following stored instructions, and produces results, able to switch tasks simply by running different software.
- 1957Artificial satelliteAn artificial satellite is a human-made object placed in orbit around a celestial body, usually Earth, to collect information, relay signals, or carry out a specific task.
- 1969InternetA global network of interconnected computer networks that communicate using the TCP/IP protocol suite.
- 1971EmailA network service that lets users send and receive digital messages through addressed mailboxes, much like postal mail but electronic.
- 1973Mobile phoneA handheld wireless phone that lets people make and receive calls while moving across a cellular network area.
- 1989World Wide WebA system of linked documents and resources, connected by hyperlinks and accessed over the Internet with web browsers.
Vladimir Arnold1937–2010 · Mathematics
Robert Aumann1930 · Mathematics
Alexander Grothendieck1928–2014 · Mathematics
Andrew Wiles1953 · Mathematics
John Tate1925–2019 · Mathematics
Benoit Mandelbrot1924–2010 · Mathematics