Endre Szemerédi

from Wikipedia, the free encyclopedia
Endre Szemerédi (2010)

Endre Szemerédi [ ˈɛndrɛ ˈsɛmɛreːdi ] (born August 21, 1940 in Budapest ) is a Hungarian mathematician who deals with combinatorics ( graph theory ), computer science and number theory.

Education and career

Szemerédi studied (after studying medicine for a year and working in a factory - his mathematical talent was then recognized by Paul Erdős ) mathematics at the University of Budapest (diploma from the Loránd Eötvös University in 1965) with András Hajnal and Paul Erdős and received his doctorate from Israel Gelfand at Lomonossow University in Moscow in 1970 (more precisely, candidate status, corresponds to a dissertation in the West). He has been at the Alfréd Rényi Institute of the Hungarian Academy of Sciences since 1965 and Professor of Computer Science at Rutgers University (New Jersey Professor of Computer Science) since 1990 . He was visiting scholar and visiting professor at Stanford University (1974), at McGill University (1980), the University of South Carolina (1981-1983), the University of Chicago (1985-1986), at the Institute for Advanced Study , at the University of Montreal (Aisenstadt Chair), the MSRI ( Eisenbud Professor 2008) and at Caltech ( Fairchild Scholar 1987/88).

plant

In 1975, Szemerédi proved the old (1936) conjecture by Pál Turán and Paul Erdős that a sequence of natural numbers that has positive density in the natural numbers contains arithmetic sequences of any length (Szemerédi theorem). The regularity lemma of Szemerédi used in the proof found applications in complexity theory , the theory of random graphs and number theory. It says roughly that large dense graphs can be approximated as the union of a limited set of “regular” graphs of roughly the same size. The proof led to advances in Ramsey theory (Ramsey theorems of the Szémeredi type) and in ergodic theory (by Hillel Fürstenberg , Yitzhak Katznelson ).

In 1977 Fürstenberg found an alternative proof to Szemerédi’s theorem using methods of ergodic theory , and in 2001 Timothy Gowers found another proof using Fourier analysis as well as combinatorics . In 2004, Terence Tao and Ben Green were even able to show the existence of arithmetic progressions of arbitrary length in the prime numbers (which have no positive density), whereby they further developed Szemerédi's methods.

Szemerédi and his teacher András Hajnal wrote the Szemerédi-Hajnal theorem about graph coloring (1970), which Erdős had suggested.

He published over 200 scientific papers (2011).

Prices and memberships

Szemerédi has been a full member of the Hungarian Academy of Sciences since 1987 (corresponding member since 1982). In 2010 he became a member of the National Academy of Sciences . He is an external member of the Norwegian Academy of Sciences . In 2012 he was elected a member of the Academia Europaea . In 2010 he received an honorary doctorate from Charles University in Prague .

literature

  • Imre Bárány , József Solymosi (Ed.) An irregular. Szémeredi is 70 , Springer 2010 (Bolyai Society Mathematical Studies 21), with list of publications

Web links

Commons : Endre Szemerédi  - collection of images, videos and audio files

Footnotes

  1. It builds on the theorem of Bartel Leendert van der Waerden from 1927, who in turn proved a conjecture by Baudet: If you divide the natural numbers into classes, at least one contains arithmetic progressions of any length.
  2. ^ On sets of integers containing no elements in arithmetic progression. Acta Arithmetica , Vol. 27, 1975, pp. 199-245. He had previously proven the conjecture for progressions of length 4 in 1969. Klaus Friedrich Roth proved the case of length 3 in 1953.