Endre Szemerédi

Szemerédi studeerde aan de Loránd Eötvös-universiteit te Boedapest en promoveerde aan de Staatsuniversiteit van Moskou bij Israel Gelfand.^[1]

Endre Szemerédi heeft meer dan 200 wetenschappelijke artikelen gepubliceerd.

Hij bewees in 1975 het vermoeden van Paul Erdős en Paul Turán: als een rij natuurlijke getallen een positieve asymptotische dichtheid heeft, dan bevat ze een willekeurig lange rekenkundige rij. Dit staat nu bekend als de Stelling van Szemerédi.

Een van de lemma's die hij voor zijn bewijs invoerde staat bekend als het lemma van Szemerédi en is belangrijk in combinatoriek, bijvoorbeeld in property testing voor grafen en de theorie van graaflimieten.

Hij bewees de stelling van Szemerédi–Trotter in incidentiemeetkunde en de stelling van Hajnal–Szemerédi in grafentheorie.

Miklós Ajtai en Szemerédi bewezen de hoekenstelling, een stap naar veralgemeningen van de Stelling van Szemerédi tot meer dimensies.

Met Miklós Ajtai en János Komlós bewees hij de ct²/log t bovengrens voor het Ramseygetal R(3,t), en ze construeerden een sorteernetwerk van optimale diepte.

Met Miklós Ajtai, Václav Chvátal en M. M. Newborn bewees Szemerédi het kruisingslemma, dat een graaf met n knopen en m randen, waar m > 4n heeft ten minste m³ / 64n² kruisingen.

Met Paul Erdős bewees hij de stelling van Erdős–Szemerédi over het aantal sommen en producten in een eindige verzameling.

Met Wolfgang Paul, Nick Pippenger en William Trotter bepaalde hij een onderscheid tussen de lineaire tijd van een niet-deterministische Turing machine en lineaire tijd van een deterministisch automaton in de geest van het P versus NP probleem.

Szemerédi won de volgende prijzen:

• Grünwald Prize in 1967
• Grünwald Prize in 1968
• Alfréd Rényi Prize in 1973
• Pólya Prize voor verdienste in toegepaste wiskunde (SIAM) in 1975
• Prijs van de Hongaarse Academie van Wetenschappen in 1979
• De Steele-prijs van de American Mathematical Society voor bijdrage tot onderzoek in 2008
• De Rolf Schock-prijs in wiskunde voor diep pionierswerk vanaf 1975 over arithmetische progressie in deelverzamelingen van de gehele getallen in 2008
• De Abelprijs “voor zijn fundamentele bijdragen tot discrete wiskunde en theoretische computerwetenschap en voor de diepgaande en blijvende invloed van die bijdragen op additieve getaltheorie en ergodentheorie” in 2012^{[2][3][4][5][6]}

Szemerédi is sinds 1982 corresponderend lid en sinds 1987 lid van de Hongaarse Academie van Wetenschappen en sinds 2010 lid van de National Academy of Sciences. Hij is lid van het Institute for Advanced Study (IAS) te Princeton, New Jersey. Hij is permanent research fellow aan het Rényi Instituut voor wiskunde te Boedapest.^[7]

Hij is eredoctor van de Karelsuniversiteit Praag.^[8]

Szemerédi is getrouwd en heeft vijf kinderen.