# Tibor Gallai

Tibor Gallai (né Tibor Grünwald' le 15 juillet 1912 à Budapest et mort le 2 janvier 1992 à Budapest) est un mathématicien hongrois qui a travaillé principalement en combinatoire et en théorie des graphes.

## Biographie

Gallai, encore lycéen, cherchait avec son ami d'enfance Paul Erdős à résoudre les problèmes mathématiques proposés dans un périodique pour élèves édité par Andor Faragó$^,$. Gallai a étudié les mathématiques à partir de 1930 à l'université de Budapest. Après l’obtention de son diplôme universitaire, Gallai travaille dans les assurances et dans l’industrie jusqu’en 1939. Ami de Paul Erdős dès leur enfance, ils suivent les cours de Dénes Kőnig sur la théorie des graphes ; Gallai soutient une thèse dirigée par Kőnig (Über Polynome mit reellen Wurzeln) en 1939. Gallai a aussi participé à l'édition de la monographie de 1936 de Kőnig sur la théorie des graphes, où figurent plusieurs de ses résultats. De 1945 à 1949, il enseigne dans une école secondaire. De 1950 à 1956, il est professeur à l'Université polytechnique et économique de Budapest. Il obtient le diplôme de candidate en 1952. Il quitte son poste de professeur en 1958, et rejoint l’Institut de recherche mathématiques, tout en enseignant dans une école secondaire. Il devient docteur en sciences mathématiques en 1988, et membre correspondant de l’Académie hongroise des sciences en 1990.
Pour son implication dans l’éducation en mathématiques, il reçoit le prix Kossuth en 1956. En 1972, il reçoit le prix Tibor Szele.

## Recherche

En 1933, Gallai démontre le théorème de Sylvester-Gallai qui dit : Étant donné $n$ points du plan, si toute droite passant par deux points passe aussi par un troisième point, alors les $n$ points sont alignés.$^,$.
Gallai a notamment travaillé sur les couplages en théorie des graphes et a caractérisé les couplages parfaits dans les graphes réguliers. Ce résultat est dépassé depuis que William T. Tutte a donné en 1947 des conditions nécessaires et suffisantes pour les couplages parfaits. En 1963, Gallai a trouvé une démonstration plus simple du théorème de Tutte (en)$^,$. Le théorème de structure de Gallai et Jack Edmonds, avec sa décomposition dite de Gallai-Edwards, décrit les couplages maximaux d'un graphe$^,$$^,$$^,$.
En 1959 Gallai démontre le théorème dit théorème de Gallai sur la couverture par sommets d'un graphe sans point isolé : La somme de la taille d'un couplage maximal et de la taille d'une couverture par sommets minimale est égale au nombre de sommets du graphe. En 1933, Gallai démontre une version en dimension supérieure du théorème de van der Waerden sur les progressions arithmétiques.
Erdős mentionne que Gallai était extrêmement modeste et réservé ; aussi publiait-il ses résultats soit pas du tout, soit après de longues hésitations. En 1947, il démontre avec Arthur Milgram un théorème, redécouvert en 1950 par Robert Dilworth, et qui porte le nom de ce dernier parce que Dilworth le publie avant eux$^,$.
Parmi ses élèves, il y a László Lovász (1971), et aussi Lajos Pósa (en) (d'après Erdős). Lorsque Gallai enseignait dans un lycée pour filles juives dans les années 1940, l'une de ses élèves était la future mathématicienne Vera T. Sós.

## Prix et distinctions

* Prix Kossuth (1956)
* Médaille Tibor-Szele (1972)

## Publications (sélection)

* [1959] Tibor Gallai, « Über extreme Punkt- und Kantenmengen », Ann. Univ. Sci. Budapest. Eötvös Sect. Math., vol. 2,‎ 1959, p. 133-138.
* [1963] Tibor Gallai, « Neuer Beweis des Tutte'schen Satzes », Magyar Tud. Akad. Mat. Kutato Int. Közl., vol. 8,‎ 1963, p. 135-139.
* [1963] Tibor Gallai, « Kritische Graphen II », Magyar Tud. Akad., vol. 8,‎ 1963, p. 373.
* [1964] Tibor Gallai, « Maximale Systeme unabhängiger Kanten », Magyar Tud. Akad., vol. 9,‎ 1964, p. 401-413.