Tibor Gallai
# Tibor Gallai

Tibor Gallai (eigentlich Tibor Grünwald, * 15. Juli 1912 in Budapest; † 2. Januar 1992 ebenda) war ein ungarischer Mathematiker, der sich insbesondere mit Graphentheorie beschäftigte.
Gallai fiel schon als Gymnasiast durch die Lösung mathematischer Probleme in der von Andor Faragó herausgegebenen ungarischen Mathematikzeitschrift für Schüler auf. Nachdem er den Eötvös-Wettbewerb gewonnen hatte, konnte er ab 1930 in Budapest Mathematik studieren, was sonst für Juden im damaligen Ungarn eingeschränkt war. Mit seinem Freund Paul Erdős besuchte er die Vorlesungen von Dénes Kőnig über Graphentheorie und promovierte bei Kőnig (Über Polynome mit reellen Wurzeln, erschienen 1939). Gallai war auch an der Herausgabe der Monographie (1936) von Kőnig über Graphentheorie beteiligt, in der mehrere seiner frühen Resultate erwähnt sind. 1950 bis 1956 war er Professor an der Technischen Hochschule in Budapest.
1933 bewies er den Satz von Sylvester-Gallai: Gegeben seien $n$ Punkte in der euklidischen Ebene, die nicht alle auf einer Geraden liegen. Dann gibt es immer eine Gerade, die zwei der $n$ Punkte, aber keinen anderen der Punkte enthält.
Insbesondere befasste er sich mit Paarungen (Matchings) und charakterisierte perfekte Paarungen in regulären Graphen. Das wurde überholt, als William T. Tutte 1947 notwendige und hinreichende Bedingungen für perfekte Paarungen angab (1-Faktor-Theorem). 1963 fand Gallai einen einfacheren Beweis für den Satz von Tutte. Der Struktursatz von Gallai und Jack Edmonds (mit der zugehörigen Gallai-Edwards-Zerlegung) beschreibt die größten Paarungen (Maximum-Matchings) eines Graphen. 1959 zeigte er, dass die Summe der Paarungszahl und die Knotenüberdeckungszahl eines Graphen (ohne isolierte Punkte) gleich der Zahl seiner Knoten ist (Satz von Gallai).
Erdős hob hervor, dass Gallai zurückhaltend war und viele seiner Resultate nicht oder nur zögerlich publizierte. 1947 fanden er und Arthur Milgram den 1950 von Robert Dilworth wiedergefundenen und nach diesem benannten Satz, da Dilworth ihnen in der Publikation zuvorkam.
Er bewies 1933 eine höherdimensionale Version des Satzes von van der Waerden (1927) über arithmetische Progressionen.
Mit Rózsa Péter schrieb er ein Mathematikbuch für Schüler.
1956 erhielt er den Kossuth-Preis, dessen Preisgeld er für Flutopfer spendete. Seit 1991 war er korrespondierendes Mitglied der Ungarischen Akademie der Wissenschaften.
Zu seinen Doktoranden zählt László Lovász (1971), und auch Lajos Pósa zählt nach Erdős zu seinen Schülern. In den 1940er Jahren war er auch Gymnasiallehrer an einer jüdischen Mädchenschule, wo die Mathematikerin Vera T. Sós zu seinen Schülerinnen zählte.