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, structure, space, models, and change.
History
On ...
. He worked in
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
, especially in
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, and was a lifelong friend and collaborator of
Paul Erdős
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 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 ...
. He was a student of
Dénes Kőnig
Dénes Kőnig (September 21, 1884 – October 19, 1944) was a Hungarian mathematician of 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 mathematician Gyu ...
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 ( hu, Magyar Tudományos Akadémia, MTA) is the most important and prestigious learned society of Hungary. Its seat is at the bank of the Danube in Budapest, between Széchenyi rakpart and Akadémia utca. Its ma ...
(1991).
His main results
The
Edmonds–Gallai decomposition theorem, which was proved independently by Gallai and
Jack Edmonds
Jack R. Edmonds (born April 5, 1934) is an American-born and educated computer scientist and mathematician who lived and worked in Canada for much of his life. He has made fundamental contributions to the fields of combinatorial optimization, pol ...
, describes finite graphs from the point of view of matchings. Gallai also proved, with
Milgram Milgram is a surname derived from the Yiddish word for pomegranate (מילגרוים, Milgroim) and may refer to:
* Arthur Milgram (1912–1961), American mathematician
** R. James Milgram (born 1939), American mathematician, son of Arthur
* ...
,
Dilworth's theorem
In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician . ...
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. It started in 1981, with László Babai and László Lovász as the editors-in-chief with Paul Erdős as honorar ...
'', 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 ( hu, Erdős Pál ; 26 March 1913 – 20 September 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 ...
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
The Erdős–Gallai theorem is a result in graph theory, a branch of combinatorial mathematics. It provides one of two known approaches to solving the graph realization problem, i.e. it gives a necessary and sufficient condition for a finite sequen ...
.
See also
*
Gallai–Hasse–Roy–Vitaver theorem
In graph theory, the Gallai–Hasse–Roy–Vitaver theorem is a form of duality between the colorings of the vertices of a given undirected graph and the orientations of its edges. It states that the minimum number of colors needed to properly c ...
*
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
Austro-Hungarian mathematicians
{{Europe-mathematician-stub