Newtonpedia ES
Home › Mathematics › Endre Szemerédi
Endre Szemerédi
Image: Wikimedia Commons

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:

Gábor N. SárközyJaikumar RadhakrishnanRyan R. MartinYi ZhaoCsaba László MagyarSarmad AbbasiAyman Ahmed KhalfalahBéla CsabaSachin Premsukh LodhaAli ShokoufandehImdadullah KhanAsif JamshedMarcelo MydlarzSimao HerdadeIan Levitt

See their academic family tree →

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

  • 1945
    ComputerA programmable machine that takes in data, processes it by following stored instructions, and produces results, able to switch tasks simply by running different software.
  • 1957
    Artificial 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.
  • 1969
    InternetA global network of interconnected computer networks that communicate using the TCP/IP protocol suite.
  • 1971
    EmailA network service that lets users send and receive digital messages through addressed mailboxes, much like postal mail but electronic.
  • 1973
    Mobile phoneA handheld wireless phone that lets people make and receive calls while moving across a cellular network area.
  • 1989
    World Wide WebA system of linked documents and resources, connected by hyperlinks and accessed over the Internet with web browsers.

See this life on the timeline →

More people in Mathematics