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.^[1] 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.^[2] 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 ${\displaystyle n}$ Punkte in der euklidischen Ebene, die nicht alle auf einer Geraden liegen. Dann gibt es immer eine Gerade, die zwei der ${\displaystyle n}$ Punkte, aber keinen anderen der Punkte enthält.^[3]

Insbesondere befasste er sich mit Paarungen (Matchings) und charakterisierte perfekte^[4] 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.^[5] Der Struktursatz von Gallai und Jack Edmonds (mit der zugehörigen Gallai-Edwards-Zerlegung) beschreibt die größten Paarungen (Maximum-Matchings)^[6] eines Graphen.^[7]

1959 zeigte er, dass die Summe der Paarungszahl^[8] und die Knotenüberdeckungszahl eines Graphen (ohne isolierte Punkte) gleich der Zahl seiner Knoten ist (Satz von Gallai).^[9]

Erdős hob hervor, dass Gallai zurückhaltend war^[10] 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.^[11]

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.

Weblinks

• Paul Erdős: Personal reminiscences and remarks on the mathematical work of Tibor Gallai, Combinatorica, Bd. 2, 1982, S. 207, PDF-Datei (die Ausgabe von Combinatorica ist ihm zu seinem 70. Geburtstag gewidmet)

Fußnoten

1. ↑ Nach Angaben von Erdős war er darin erfolgreicher als Erdős selbst, allerdings nicht so gut wie E. Vázsonyi und György Hajós
2. ↑ Ein Studium im Ausland wie bei John von Neumann kam nicht in Frage, da er aus keiner wohlhabenden Familie stammte
3. ↑ Die Anregung dafür kam von Erdős, der selbst keinen Beweis finden konnte. Sylvester vermutete den Satz 1893 in einem Brief an die Educational Times. Er spielt eine Rolle im Rahmen von Konfigurationen von Geraden auf algebraischen Kurven. Beweise des Satzes finden sich in Aigner, Ziegler Proofs from the Book
4. ↑ Alle Knoten überdeckende Paarung (1-Faktor)
5. ↑ Lovasz, Combinatorica Bd. 2, 1982, S. 203. Gallai Neuer Beweis des Tutte´schen Satzes, Magyar Tud. Akad. Mat. Kutato Int. Közl., Bd. 8, 1963, S. 135–139
6. ↑ Solche mit maximaler Zahl an Kanten
7. ↑ Gallai Kritische Graphen II, Magyar Tud. Akad., Bd. 8, 1963, S. 373, Maximale Systeme unabhängiger Kanten, Magyar Tud. Akad., Bd. 9, 1964, S. 401–413, Edmonds Paths, trees and flows, Canadian J. Math., Bd. 17, 1965, S. 449
8. ↑ Matching number, die Kardinalität der Maximum-Matching
9. ↑ Gallai, Über extreme Punkt- und Kantenmengen, Ann. Univ. Sci. Budapest. Eötvös Sect. Math., Bd. 2, 1959, S. 133–138
10. ↑ Trotz Drängen von Erdős und anderen weigerte er sich zum Beispiel, den „Doktortitel“ anzunehmen, der dem russischen Gebrauch entsprechend einer Habilitation entspricht. Erdős, loc.cit.
11. ↑ Paul Erdős, Nachruf auf Gallai, Combinatorica, Bd. 12, 1992, S. 373. Erdős, der Gallai als einen seiner ältesten Freunde bezeichnet (zuerst lernten sie sich 1930 kennen), schreibt darin, das Gallai und Milgram in Englisch veröffentlichen wollten, was sich verzögerte, da Gallai schlecht Englisch sprach und Milgram als Topologe die Bedeutung des Satzes nicht erkannte.