Tibor Gallai
Tibor Gallai (actually Tibor Grünwald, born July 15, 1912 in Budapest, † January 2, 1992 ) was a Hungarian mathematician who has been dealing with graph theory.
Gallai fell even as a high school student on the solution of mathematical problems in released by Andor Faragó Hungarian mathematics magazine for students. After winning the Eötvös Competition, he was from 1930 to study mathematics in Budapest, which was otherwise restricted for Jews in what was then Hungary. With his friend Paul Erdős, he attended the lectures of Dénes Kőnig on graph theory and a doctorate in Kőnig (over polynomials with real roots, published 1939). Gallai was also involved in the publication of the monograph (1936 ) of Kőnig on graph theory, in which several of his early results are mentioned. 1950 to 1956 he was professor at the Technical University of Budapest.
In 1933 he proved the theorem of Sylvester and Gallai: Given n points in the Euclidean plane, which do not all lie on a straight line. There is always a straight line, two of the n points, but has no other of said points.
In particular, he focused on pairings ( matching ) and characterized perfect pairings in regular graphs. This has been overhauled, as William T. Tutte 1947 necessary and sufficient conditions for perfect pairings stated (1- factor theorem). 1963 was Gallai a simpler proof for the theorem of Tutte. The structure theorem of Gallai and Jack Edmonds ( with the associated Gallai decomposition Edwards ) describes the greatest pairings ( maximum matching ) of a graph.
In 1959 he showed that the sum of the pairing number and the vertex cover number of a graph (without isolated points ) in the number of nodes is the same ( set of Gallai ).
Erdős emphasized that Gallai was restrained and many of its results are not published or only hesitantly. In 1947, he and Arthur Milgram found the 1950 by Robert Dilworth recovered and designated pursuant to this sentence because Dilworth forestalled them in the publication.
He proved in 1933 a higher dimensional version of the theorem of van der Waerden (1927 ) on arithmetic progressions.
With Rózsa Péter he wrote a math book for students.
In 1956 he was awarded the Kossuth Prize, the prize money he donated for flood victims. Since 1991 he was a corresponding member of the Hungarian Academy of Sciences.
His doctoral counts László Lovász (1971 ), and Lajos Erdős Pósa recounts to his students. In the 1940s he was also a high school teacher at a Jewish girls' school, where the mathematician Vera T. Sós was among his pupils.