Die offizielle Laudatio:
Die Norwegische Akademie der Wissenschaften verleiht den Abel-Preis 2012 an
Endre Szemerédi
Alfréd-Rényi-Institut für Mathematik der ungarischen Akademie der Wissenschaften, Budapest und Department of Computer Science, Rutgers, The State University of New Jersey, USA
«für seine fundamentalen Beiträge zur diskreten Mathematik und theoretischen Informatik und in Anerkennung ihres durchgreifenden und nachhaltigen Einflusses auf additive Zahlentheorie und Ergodentheorie. »
Die diskrete Mathematik untersucht Strukturen wie Graphen, Codes, Permutationen und geometrische Konfigurationen. Die Mathematik solcher Strukturen bildet die Grundlage der theoretischen Informatik und der Informationstheorie. Zum Beispiel lassen sich Kommunikationsnetze wie das Internet mit den Methoden der Graphentheorie beschreiben und analysieren, und der Design von effizienten Berechnungsalgorithmen beruht ganz wesentlich auf Einsichten aus der diskreten Mathematik. Die Kombinatorik diskreter Strukturen ist auch in vielen Bereichen der reinen Mathematik eine wichtige Komponente, insbesondere in der Zahlentheorie, Wahrscheinlichkeitstheorie, Algebra, Geometrie und Analysis.
Endre Szemerédi hat durch die Einführung genialer (without comma) neuartiger Verfahren die diskrete Mathematik revolutioniert und eine ganze Reihe grundlegender Probleme gelöst. Durch seine Arbeiten hat er der Kombinatorik einen zentralen Platz in der Mathematik eröffnet, indem er ihre tiefliegenden Verbindungen mit Bereichen wie additiver Zahlentheorie, Ergodentheorie, theoretischer Informatik und Inzidenzgeometrie freilegte.
Im Jahre 1975 zog Endre Szemerédi mit seiner Lösung der berühmten Erdős-Turán-Vermutung zum ersten Mal die Aufmerksamkeit vieler Mathematiker auf sich, als er zeigte, dass jede Folge natürlicher Zahlen mit positiver Dichte beliebig lange arithmetische Progressionen enthält. Das war eine Sensation, denn schon der Fall von Progressionen der Länge 3 oder 4 hatte erhebliche Anstrengungen erfordert, von Klaus Roth wie auch von Szemerédi selbst.
Eine noch größere Überraschung stand bevor. Szemerédis Beweis war eine Meisterleistung kombinatorischer Beweisführung, deren aussergewöhnliche Tiefe und Bedeutung sehr schnell erkannt wurde. Ein Meilenstein im Beweis, inzwischen bekannt als das «Regularitätslemma von Szemerédi», ist eine strukturelle Klassifikation großer Graphen. Dieses Lemma wurde seither eines der wichtigsten Werkzeuge sowohl in der Graphentheorie wie in der theoretischen Informatik. So ermöglichte es die Lösung zentraler Probleme beim Testen von Eigenschaften und führte zur Theorie der Graph-Limiten.
Weitere Überraschungen folgten. Außer dem Einfluss, den es auf die diskrete Mathematik und die additive Zahlentheorie hatte, inspirierte Szemerédis Theorem Hillel Fürstenberg dazu, die Ergodentheorie in neue Richtungen zu entwickeln. Fürstenberg gab einen neuen Beweis für Szemerédis Theorem, indem er den Satz der multiplen Rekurrenz in der Ergodentheorie
aufstellte und damit in unerwarteter Weise Fragestellungen der diskreten Mathematik mit der Theorie der dynamischen Systeme verknüpfte. Diese fundamentale Verbindung führte ihrerseits zu zahlreichen neuen Erkenntnissen, so zum Satz von Green und Tao, wonach es unter den Primzahlen arithmetische Progressionen beliebiger Länge gibt.
Szemerédi hat viele weitere tief liegende, wichtige und einflussreiche Beiträge zur diskreten Mathematik und theoretischen Informatik geliefert. Auf dem Gebiet der diskreten Mathematik seien beispielhaft der Satz von Szemerédi–Trotter, die semi-random Methode von Ajtai, Komlós und Szemerédi, Erdős-Szemerédis Summe-Produkt-Theorem und das Lemma von Balog, Szemerédi und Gowers erwähnt. Zu den Beiträgen in der theoretischen Informatik gehőren das Sortiernetzwerk von Ajtai, Komlós und Szemerédi, das Hashing-Schema von Fredman, Komlós und Szemerédi und der Satz von Paul–Pippenger–Szemerédi–Trotter, der deterministische von nicht-deterministischer linearer Zeit unterscheidet.
Die Art und Weise, wie Szemerédi an die Mathematik herangeht, kann als anschauliches Beispiel für die lange Tradition der ungarischen Schule der Problem-orientierten Mathematik dienen. Darüber hinaus hat der theoretische Einfluss seines Werkes die Mathematik nachhaltig verändert.