Tibor Gallai (born Tibor Grünwald, 15 July 1912 – 2 January 1992) was a
Hungarian mathematician
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, mathematical structure, structure, space, Mathematica ...
. He worked in
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
, especially in
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, and was a lifelong friend and collaborator of
Paul Erdős
Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
. He was a student of
Dénes Kőnig
Dénes Kőnig (September 21, 1884 – October 19, 1944) was a Hungarian mathematician of Hungarian Jewish heritage who worked in and wrote the first textbook on the field of graph theory.
Biography
Kőnig was born in Budapest, the son of mathemat ...
and an advisor of
László Lovász
László Lovász (; born March 9, 1948) is a Hungarian mathematician and professor emeritus at Eötvös Loránd University, best known for his work in combinatorics, for which he was awarded the 2021 Abel Prize jointly with Avi Wigderson. He ...
. He was a corresponding member of the
Hungarian Academy of Sciences
The Hungarian Academy of Sciences ( , MTA) is Hungary’s foremost and most prestigious learned society. Its headquarters are located along the banks of the Danube in Budapest, between Széchenyi rakpart and Akadémia utca. The Academy's primar ...
(1991).
His main results
The
Edmonds–Gallai decomposition theorem, which was proved independently by Gallai and
Jack Edmonds, describes finite graphs from the point of view of matchings. Gallai also proved, with
Milgram,
Dilworth's theorem in 1947, but as they hesitated to publish the result, Dilworth independently discovered and published it.
[P. Erdős]
In memory of Tibor Gallai
''Combinatorica
''Combinatorica'' is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science
Computer science is the study of computation, information, and automation. Computer science spans Theore ...
'', 12(1992), 373–374.
Gallai was the first to prove the higher-dimensional version of
van der Waerden's theorem
Van der Waerden's theorem is a theorem in the branch of mathematics called Ramsey theory. Van der Waerden's theorem states that for any given positive integers ''r'' and ''k'', there is some number ''N'' such that if the integers are colored, eac ...
.
With
Paul Erdős
Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
he gave a
necessary and sufficient condition
In logic and mathematics, necessity and sufficiency are terms used to describe a conditional or implicational relationship between two statements. For example, in the conditional statement: "If then ", is necessary for , because the truth of ...
for a sequence to be the degree sequence of a graph, known as the
Erdős–Gallai theorem.
See also
*
Gallai–Hasse–Roy–Vitaver theorem
*
Sylvester–Gallai theorem
The Sylvester–Gallai theorem in geometry states that every finite set of points in the Euclidean plane has a line that passes through exactly two of the points or a line that passes through all of them. It is named after James Joseph Sylvester, ...
*
Gallais-Edmonds decomposition
References
External links
*
1912 births
1992 deaths
20th-century Hungarian mathematicians
Members of the Hungarian Academy of Sciences
Graph theorists
Mathematicians from Austria-Hungary
{{Europe-mathematician-stub