Tibor Gallai

Tibor Gallai (actually Tibor Grünwald , born July 15, 1912 in Budapest , † January 2, 1992 in Budapest ) was a Hungarian mathematician who was particularly concerned with graph theory.

Even as a high school student, Gallai was noticed by solving mathematical problems in the Hungarian mathematics magazine for schoolchildren published by Andor Faragó. After winning the Eötvös competition, he was able to study mathematics in Budapest from 1930, which was otherwise restricted for Jews in what was then Hungary. With his friend Paul Erdős he attended Dénes Kőnig's lectures on graph theory and received his doctorate from Kőnig ( On Polynomials with Real Roots , published 1939). Gallai was also involved in editing Kőnig's 1936 monograph on graph theory, which mentions several of his early results. 1950 to 1956 he was a professor at the Technical University in Budapest .

In 1933 he proved Sylvester-Gallai's theorem : Given are points in the Euclidean plane that do not all lie on a straight line. Then there is always a straight line that contains two of the points but no other of the points. ${\ displaystyle n}$ ${\ displaystyle n}$

In particular, he dealt with pairings (matchings) and characterized perfect pairings in regular graphs . This was overtaken when William T. Tutte specified necessary and sufficient conditions for perfect pairings in 1947 (1- factor theorem). In 1963, Gallai found a simpler proof for Tutte's theorem . The structure theorem by Gallai and Jack Edmonds (with the associated Gallai-Edwards decomposition) describes the greatest pairings (maximum matchings) of a graph.

In 1959 he showed that the sum of the pairing number and the vertex coverage number of a graph (without isolated points) is equal to the number of its vertices (Gallai's theorem).

Erdős emphasized that Gallai was cautious and did not publish many of his results or only published them hesitantly. In 1947 he and Arthur Milgram found the sentence, which was found again by Robert Dilworth in 1950 and named after it, as Dilworth anticipated them in the publication.

In 1933 he proved a higher dimensional version of the van der Waerden theorem (1927) on arithmetic progressions.

With Rózsa Péter he wrote a math book for schoolchildren.

In 1956 he received the Kossuth Prize , the money of which he donated for flood victims. Since 1991 he has been a corresponding member of the Hungarian Academy of Sciences .

László Lovász (1971) is one of his doctoral students , and Lajos Pósa is one of his students after Erdős. In the 1940s he was also a high school teacher at a Jewish girls' school, where the mathematician Vera T. Sós was one of his students.

Web links

Paul Erdős: Personal reminiscences and remarks on the mathematical work of Tibor Gallai , Combinatorica, Vol. 2, 1982, p. 207, PDF file (the edition of Combinatorica is dedicated to him on his 70th birthday)

Footnotes

↑ According to Erdős, he was more successful in this than Erdős himself, but not as good as E. Vázsonyi and György Hajós
↑ Studying abroad like with John von Neumann was out of the question, as he did not come from a wealthy family
↑ The suggestion for this came from Erdős, who could not find any evidence himself. Sylvester suspected the phrase in a letter to the Educational Times in 1893. It plays a role in the configuration of straight lines on algebraic curves. Proof of the theorem can be found in Aigner, Ziegler Proofs from the Book
↑ Pairing covering all nodes (1-factor)
↑ Lovasz, Combinatorica Vol. 2, 1982, p. 203. Gallai New proof of Tutte's theorem , Magyar Tud. Akad. Mat. Kutato Int. Közl., Vol. 8, 1963, pp. 135-139
↑ Those with the maximum number of edges
^ Gallai Critical Graphs II , Magyar Tud. Akad., Vol. 8, 1963, p. 373, Maximum Systems of Independent Edges , Magyar Tud. Akad., Vol. 9, 1964, pp. 401-413, Edmonds Paths, trees and flows , Canadian J. Math., Vol. 17, 1965, p. 449
↑ Matching number, the cardinality of the maximum matching
↑ Gallai, On Extreme Point and Edge Sets, Ann. Univ. Sci. Budapest. Eötvös Sect. Math., Vol. 2, 1959, pp. 133-138
↑ Despite the urging of Erdős and others, he refused, for example, to accept the "doctorate", which corresponds to Russian usage according to a habilitation. Erdős, loc. Cit.
↑ Paul Erdős, Obituary for Gallai, Combinatorica, Vol. 12, 1992, p. 373. Erdős, who calls Gallai one of his oldest friends (they first met in 1930), writes in it that Gallai and Milgram wanted to publish in English which was delayed as Gallai spoke poor English and Milgram, as a topologist, failed to see the meaning of the sentence.

personal data
SURNAME	Gallai, Tibor
ALTERNATIVE NAMES	Grünwald, Tibor (real name)
BRIEF DESCRIPTION	Hungarian mathematician
DATE OF BIRTH	July 15, 1912
PLACE OF BIRTH	Budapest
DATE OF DEATH	2nd January 1992
Place of death	Budapest

[1] According to Erdős, he was more successful in this than Erdős himself, but not as good as E. Vázsonyi and György Hajós

[2] Studying abroad like with John von Neumann was out of the question, as he did not come from a wealthy family

[3] The suggestion for this came from Erdős, who could not find any evidence himself. Sylvester suspected the phrase in a letter to the Educational Times in 1893. It plays a role in the configuration of straight lines on algebraic curves. Proof of the theorem can be found in Aigner, Ziegler Proofs from the Book

[4] Pairing covering all nodes (1-factor)

[5] Lovasz, Combinatorica Vol. 2, 1982, p. 203. Gallai New proof of Tutte's theorem , Magyar Tud. Akad. Mat. Kutato Int. Közl., Vol. 8, 1963, pp. 135-139

[6] Those with the maximum number of edges

[7] Gallai Critical Graphs II , Magyar Tud. Akad., Vol. 8, 1963, p. 373, Maximum Systems of Independent Edges , Magyar Tud. Akad., Vol. 9, 1964, pp. 401-413, Edmonds Paths, trees and flows , Canadian J. Math., Vol. 17, 1965, p. 449

[8] Matching number, the cardinality of the maximum matching

[9] Gallai, On Extreme Point and Edge Sets, Ann. Univ. Sci. Budapest. Eötvös Sect. Math., Vol. 2, 1959, pp. 133-138

[10] Despite the urging of Erdős and others, he refused, for example, to accept the "doctorate", which corresponds to Russian usage according to a habilitation. Erdős, loc. Cit.

[11] Paul Erdős, Obituary for Gallai, Combinatorica, Vol. 12, 1992, p. 373. Erdős, who calls Gallai one of his oldest friends (they first met in 1930), writes in it that Gallai and Milgram wanted to publish in English which was delayed as Gallai spoke poor English and Milgram, as a topologist, failed to see the meaning of the sentence.