Endre Szemerédi

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen
Endre Szemerédi

Endre Szemerédi (Boedapest, 21 augustus 1940) is een Hongaars wiskundige die sinds 1986 professor is aan de Rutgers-universiteit in New Jersey.

Opleiding[bewerken]

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

Werk[bewerken]

Endre Szemerédi heeft meer dan 200 wetenschappelijke artikels 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 ct2/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 m3 / 64n2 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.

Onderscheidingen[bewerken]

Szemerédi won de volgende prijzen:

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]

Privé[bewerken]

Szemerédi is getrouwd en heeft vijf kinderen.