Mathematik

Endre Szemerédi | Ungarisch-amerikanischer Mathematiker

Endre Szemerédi , (geb. August 21, 1940 Budapest , Ungarn), ungarischen amerikanischen Mathematiker die 2012 vergeben Abel - Preis „für seine grundlegenden Beiträge zur diskreten Mathematik und der theoretischen Informatik .“

Szemerédi studierte ursprünglich, um Arzt zu werden, brach jedoch bald die medizinische Fakultät ab und nahm eine Stelle in einer Fabrik an. Anschließend trat er in die Eötvös Loránd Universität in Budapest ein, wo er studiertePaul Erdős . 1965 erhielt er einen Master-Abschluss in Mathematik . 1970 promovierte er in Mathematik an der Moskauer Staatlichen Universität . Er wurde Fellow am Alfréd Rényi-Institut für Mathematik der Ungarischen Akademie der Wissenschaften in Budapest und war ab 1986 a Professor für Informatik an der Rutgers University in New Brunswick, New Jersey .

Einer seiner bekanntesten Beiträge zur Mathematik ist ein Satz über arithmetische Progressionen. Der Satz, der bekannt wurde alsDer Satz von Szemerédi bewies eine Vermutung von Erdős und dem ungarischen Mathematiker Paul Turán aus dem Jahr 1936. In der Zahlentheorie ist eine arithmetische Folge eine Folge von Zahlen, die in Schritten des gleichen Betrags abläuft. Zum Beispiel ist 2, 4, 6, 8 eine Folge mit vier Termen und mit 2 als Schrittgröße. Der Satz von Szemerédi beruht auf dem Konzept der Dichte einer Menge natürlicher Zahlen. Für eine Teilmenge der natürlichen Zahlen ist die Dichte das Verhältnis zwischen der Anzahl der ganzen Zahlen im Schnittpunkt zwischen dieser Teilmenge und der Menge {1,2,…, N } und N, wenn N gegen unendlich geht. Erdős und Turán vermuteten, dass für eine positive Dichte d und eine beliebige Anzahl von ganzen Zahlen kgibt es eine Zahl N ( d , k ), so dass eine Teilmenge von {1,2,…, N }, die d N Zahlen enthält, eine k- terminale Progression aufweist, wenn N größer als N ( d , k ) ist. Der britische Mathematiker Klaus Roth hatte 1953 die Vermutung für Drei-Zeit-Progressionen bewiesen. Szemerédi bewies 1969 die Vermutung für Vier-Term-Progressionen und 1975 für Progressionen beliebiger Länge. (Erdős gab Mathematikern häufig Geldpreise für die Lösung ungelöster Probleme und betrachtete sie Die Vermutung war ziemlich schwierig. Szemerédi erhielt von Erdős 1.000 Dollar für seinen Beweis.)

Als Teil von Szemerédis allgemeinem Beweis der Erdős-Turán-Vermutung brachte er ein Schlüsselergebnis in der Graphentheorie hervor, das als bekannt wurdeSzemerédis Regelmäßigkeits-Lemma; Es besagt, dass jedes Diagramm in kleinere Diagramme unterteilt werden kann, die zufällig erscheinen. Szemerédi bewies das Lemma zunächst in eingeschränkter Form und dann allgemein 1978. Das Lemma erwies sich in der Graphentheorie als äußerst nützlich, da es zeigt, dass Ergebnisse, die für Zufallsgraphen gelten, allgemein auf Graphen angewendet werden können.

Erhalten Sie mit Ihrem Abonnement exklusiven Zugriff auf Inhalte aus unserer 1768 First Edition. Abonnieren Sie noch heute

Trotz Szemerédis erklärter Gleichgültigkeit gegenüber Computern fand seine Arbeit viele Anwendungen in der Informatik, insbesondere seine Zusammenarbeit mit dem Informatiker Miklós Ajtai und dem Mathematiker (und Rutgers-Kollegen) János Komlós beim Sortieren. 1983 entwickelte das Trio dieAjtai-Komlós-Szemerédi (AKS) -Sortiernetzwerk, ein Algorithmus zum Sortieren von n Objekten in einer bestimmten Reihenfolge in log n Zeitschritten, der theoretisch geringstmöglichen Zeit.