# Endre Szemerédi

Endre Szemerédi [ˈɛndrɛ ˈsɛmɛreːdi] (* 21. August 1940 in Budapest) ist ein ungarisch-US-amerikanischer Mathematiker und Informatiker, der sich mit Kombinatorik (Graphentheorie), Informatik und Zahlentheorie beschäftigt. Seit 1986 ist er State of „New Jersey Professor“ für Informatik an der Rutgers University. Außerdem ist er emeritierter Professor am Alfréd Rényi Institut für Mathematik der Ungarischen Akademie der Wissenschaften. Szemerédi hat mit dem Abelpreis (2012) und dem Leroy P. Steele Prize einige der bedeutendsten Mathematikpreise gewonnen.

## Ausbildung und Karriere

Szemerédi wurde in Budapest geboren. Obwohl er auf der Schule gut in Mathematik war, besuchte er weder eine der Eliteschulen für Mathematiker in Ungarn (wie Fazekas) noch nahm er an den mathematischen Wettbewerben in Ungarn teil. Da seine Eltern wünschten, dass er Arzt wird, schrieb sich Szemerédi an einer medizinischen Hochschule ein, brach das Studium aber nach sechs Monaten ab und arbeitete zwei Jahre in einer Maschinenfabrik, bevor er auf Rat eines Freundes ein Mathematikstudium begann. Er studierte an der naturwissenschaftlichen Fakultät der Eötvös-Loránd-Universität in Budapest (Diplom 1965) bei András Hajnal. Wichtige Einflüsse waren auch Pál Turán (mit dem er aber nicht zusammenarbeitete da dieser Zahlentheoretiker war) und Paul Erdős, mit dem er insgesamt fast 30 Arbeiten veröffentlichte und der häufig Ungarn besuchte. Szemerédi wurde 1970 an der Lomonossow-Universität in Moskau bei Israel Gelfand promoviert (genauer Kandidaten-Status, entspricht einer Dissertation im Westen). Er ist seit 1965 am Alfréd-Rényi-Institut der Ungarischen Akademie der Wissenschaften und seit 1986 Professor für Informatik an der Rutgers University (New Jersey Professor of Computer Science). Nach seiner Emeritierung am Alfred Renyi Institut ist er dort noch ständiger Forschungsstipendiat.
Er war Gastwissenschaftler und Gastprofessor an der Stanford University (1974), an der McGill University (1980), der University of South Carolina (1981–1983), der University of Chicago (1985–1986), am Institute for Advanced Study (Mitglied 2007 bis 2010), an der Universität Montreal (Aisenstadt Chair, Centre de Recherches Mathématiques), dem MSRI (Eisenbud Professor 2008) und am Caltech (Fairchild Scholar 1987/88).
Szemerédi ist verheiratet und hat fünf Kinder.

## Werk

Szemerédi bewies 1975 die alte (1936) Vermutung von Pál Turán und Paul Erdős, dass eine Folge natürlicher Zahlen, die positive Dichte in den natürlichen Zahlen hat, beliebig lange arithmetische Folgen enthält (Satz von Szemerédi). Das beim Beweis verwendete Regularitätslemma von Szemerédi fand Anwendungen in der Komplexitätstheorie, der Theorie zufälliger Graphen und der Zahlentheorie. Es besagt in etwa, dass große dichte Graphen als Vereinigung einer begrenzten Menge „regulärer“ Graphen von etwa gleicher Größe approximiert werden können. Der Beweis führte zu Fortschritten in der Ramsey-Theorie (Ramsey-Sätze vom Szémeredi-Typ) und in der Ergodentheorie (durch Hillel Fürstenberg, Yitzhak Katznelson).
1977 fand Fürstenberg einen alternativen Beweis zum Satz von Szemerédi mit Methoden der Ergodentheorie, und 2001 fand Timothy Gowers einen weiteren Beweis, bei dem neben der Kombinatorik auch die Fourier-Analysis verwendet wurde. Terence Tao und Ben Green konnten 2004 sogar die Existenz von arithmetischen Progressionen beliebiger Länge in den Primzahlen (die keine positive Dichte haben) zeigen, wobei sie Szemerédis Methoden weiterentwickelten.
Von Szemerédi und seinem Lehrer András Hajnal stammt der Satz von Szemerédi-Hajnal über Graphenfärbung (1970), der von Erdős vermutet worden war. Von Szemerédi und Erdős stammt der Satz von Erdős–Szemerédi (1983), dem Prototyp einer Aussage zu Summen-Produkt-Phänomenen wie sie beispielsweise auch in Ringen und Körpern auftreten. Der Satz besagt, dass für eine endliche Menge natürlicher Zahlen A die Kardinalität der Menge der paarweisen Summen $A+A$ oder die Menge der paarweisen Produkte $A\cdot A$ von Elementen aus $A$ von unten durch die Kardinalität $|A|$ von $A$ beschränkt ist mit Konstanten $c,\varepsilon$:
    $\max(|A+A|,|A\cdot A|)\geq c|A|^{1+\varepsilon }$.
Der Satz von Szemerédi und Trotter (zusätzlich nach William T. Trotter benannt) aus der Diskreten Geometrie macht Aussagen über die Anzahl der Inzidenzen von $n$ Punkten und $m$ Geraden in der euklidischen Ebene. Nach dem Satz ist sie von der Größe
    $O\left(n^{2/3}m^{2/3}+n+m\right)$
mit dem Landau-Symbol $O$.
Er veröffentlichte über 200 wissenschaftliche Arbeiten (2011).

## Preise und Mitgliedschaften

* 1967, 1968 Géza-Grünwald-Preis der Ungarischen Mathematischen Gesellschaft
* 1973 Rényi-Preis
* 1975 George-Pólya-Preis
* 1979 Preis der Ungarischen Akademie der Wissenschaften
* 2008 Leroy P. Steele Prize
* 2008 Rolf-Schock-Preis
* 2012 Széchenyi-Preis
* 2012 Abelpreis
* 2012 Prima Primissima-Preis
* 2020 Ungarischer Sankt Stephans-Orden
Szemerédi ist seit 1987 volles Mitglied der Ungarischen Akademie der Wissenschaften (seit 1982 korrespondierendes Mitglied). 2010 wurde er Mitglied der National Academy of Sciences. Er ist Ehrendoktor der Karls-Universität in Prag. Er ist auswärtiges Mitglied der Norwegischen Akademie der Wissenschaften. 2012 wurde er zum Mitglied der Academia Europaea gewählt. 2010 wurde er Ehrendoktor der Karls-Universität Prag. 2022 wurde Szemerédi in die American Academy of Arts and Sciences gewählt.