Tibor Gallai
Encyclopedia
Tibor Gallai was a Hungarian
mathematician
. He worked in combinatorics
, especially in graph theory
, and was a lifelong friend and collaborator of Paul Erdős
. He was a student of Dénes König
and an advisor of László Lovász
. He was a corresponding member of the Hungarian Academy of Sciences
(1991).
, describes finite graphs from the point of view of matchings. Gallai also proved, with Milgram
the Dilworth's theorem
in 1947, but as they hesitated to publish the result, Dilworth independently discovered and published it.
Gallai was the first to prove the higher dimensional version of van der Waerden's theorem.
With Paul Erdős
he gave a sufficient and necessary condition
for a sequence to be the degree sequence of a graph.
Hungary
Hungary , officially the Republic of Hungary , is a landlocked country in Central Europe. It is situated in the Carpathian Basin and is bordered by Slovakia to the north, Ukraine and Romania to the east, Serbia and Croatia to the south, Slovenia to the southwest and Austria to the west. The...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
. He worked in combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, especially in graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, and was a lifelong friend and collaborator of Paul Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
. He was a student of Dénes König
Dénes König
Dénes Kőnig was a Jewish Hungarian mathematician who worked in and wrote the first textbook on the field of graph theory....
and an advisor of László Lovász
László Lovász
László Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....
. He was a corresponding member of the Hungarian Academy of Sciences
Hungarian Academy of Sciences
The Hungarian Academy of Sciences is the most important and prestigious learned society of Hungary. Its seat is at the bank of the Danube in Budapest.-History:...
(1991).
His main results
The Edmonds–Gallai decomposition theorem, which was proved independently by Gallai and Jack EdmondsJack Edmonds
Jack R. Edmonds is a mathematician, regarded as one of the most important contributors to the field of combinatorial optimization...
, describes finite graphs from the point of view of matchings. Gallai also proved, with Milgram
Arthur Milgram
Arthur Norton Milgram was an American mathematician. He made contributions in functional analysis, combinatorics, differential geometry, topology, partial differential equations, and Galois theory...
the Dilworth's theorem
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...
in 1947, but as they hesitated to publish the result, Dilworth independently discovered and published it.
Gallai was the first to prove the higher dimensional version of van der Waerden's theorem.
With Paul Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
he gave a sufficient and necessary condition
Erdős–Gallai theorem
The Erdős–Gallai theorem is a result in graph theory, a branch of combinatorics, that gives a necessary and sufficient condition for a finite sequence to be the degree sequence of a simple graph...
for a sequence to be the degree sequence of a graph.