Tibor Gallai | |
---|---|

Born | |

Died | 2 January 1992 79) Budapest, Hungary | (aged

Nationality | Hungarian |

Alma mater | Technical University of Budapest |

Known for | Sylvester–Gallai theorem |

Scientific career | |

Fields | Mathematics |

Institutions | Eötvös Loránd University |

Doctoral advisor | Dénes Kőnig |

Doctoral students | László Lovász |

**Tibor Gallai** (born Tibor Grünwald, 15 July 1912 – 2 January 1992) 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).

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.^{ [1] }

Gallai was the first to prove the higher-dimensional version of van der Waerden's theorem.

With Paul Erdős he gave a necessary and sufficient condition for a sequence to be the degree sequence of a graph, known as the Erdős–Gallai theorem.

**Richard Rado** FRS was a German-born British mathematician whose research concerned combinatorics and graph theory. He was Jewish and left Germany to escape Nazi persecution. He earned two PhDs: in 1933 from the University of Berlin, and in 1935 from the University of Cambridge. He was interviewed in Berlin by Lord Cherwell for a scholarship given by the chemist Sir Robert Mond which provided financial support to study at Cambridge. After he was awarded the scholarship, Rado and his wife left for the UK in 1933. He was appointed Professor of Mathematics at the University of Reading in 1954 and remained there until he retired in 1971.

In graph theory, a **perfect graph** is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

In graph theory, the **perfect graph theorem** of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.

In graph theory, a **critical graph** is an undirected graph all of whose proper subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a **critical element**, in the sense that its deletion would decrease the number of colors needed in a graph coloring of the given graph. The decrease in the number of colors cannot be by more than one.

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 Robert P. Dilworth (1950).

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, who posed it as a problem in 1893, and Tibor Gallai, who published one of the first proofs of this theorem in 1944.

**Dénes Kőnig** was a Hungarian mathematician of Hungarian Jewish heritage who worked in and wrote the first textbook on the field of graph theory.

In graph theory, the **degree** of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex is denoted or . The **maximum degree** of a graph , denoted by , and the **minimum degree** of a graph, denoted by , are the maximum and minimum of its vertices' degrees. In the multigraph shown on the right, the maximum degree is 5 and the minimum degree is 0.

In mathematics, the **Erdős–Szekeres theorem** asserts that, given *r*, *s,* any sequence of distinct real numbers with length at least (*r* − 1)(*s* − 1) + 1 contains a monotonically increasing subsequence of length *r**or* a monotonically decreasing subsequence of length *s*. The proof appeared in the same 1935 paper that mentions the Happy Ending problem.

* Proofs from THE BOOK* is a book of mathematical proofs by Martin Aigner and Günter M. Ziegler. The book is dedicated to the mathematician Paul Erdős, who often referred to "The Book" in which God keeps the most elegant proof of each mathematical theorem. During a lecture in 1985, Erdős said, "You don't have to believe in God, but you should believe in The Book."

In graph theory, a **comparability graph** is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called **transitively orientable graphs**, **partially orderable graphs**, **containment graphs**, and **divisor graphs**. An **incomparability graph** is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order.

In graph theory, a mathematical discipline, a **factor-critical graph** is a graph with n vertices in which every subgraph of *n* − 1 vertices has a perfect matching.

**Václav (Vašek) Chvátal** is a Professor Emeritus in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Quebec, Canada, and a visiting professor at Charles University in Prague. He has published extensively on topics in graph theory, combinatorics, and combinatorial optimization.

**András Hajnal** was a professor of mathematics at Rutgers University and a member of the Hungarian Academy of Sciences known for his work in set theory and combinatorics.

**Vera Turán Sós** was a Hungarian mathematician who specialized in number theory and combinatorics. She was a student and close collaborator of both Paul Erdős and Alfréd Rényi. She also collaborated frequently with her husband Pál Turán, an analyst, number theorist, and combinatorist. Until 1987, she worked at the Department of Analysis at the Eötvös Loránd University, Budapest. Afterwards, she was employed by the Alfréd Rényi Institute of Mathematics. She was elected a corresponding member (1985) and member (1990) of the Hungarian Academy of Sciences. In 1997, Sós was awarded the Széchenyi Prize.

* László Pyber* is a Hungarian mathematician. He is a researcher at the Alfréd Rényi Institute of Mathematics, Budapest. He works in combinatorics and group theory.

In mathematics, in the areas of order theory and combinatorics, **Mirsky's theorem** characterizes the height of any finite partially ordered set in terms of a partition of the order into a minimum number of antichains. It is named for Leon Mirsky (1971) and is closely related to Dilworth's theorem on the widths of partial orders, to the perfection of comparability graphs, to the Gallai–Hasse–Roy–Vitaver theorem relating longest paths and colorings in graphs, and to the Erdős–Szekeres theorem on monotonic subsequences.

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 sequence of natural numbers to be the degree sequence of a simple graph. A sequence obeying these conditions is called "graphic". The theorem was published in 1960 by Paul Erdős and Tibor Gallai, after whom it is named.

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 color any graph equals one plus the length of a longest path in an orientation of chosen to minimize this path's length. The orientations for which the longest path has minimum length always include at least one acyclic orientation.

In graph theory, the **Gallai–Edmonds decomposition** is a partition of the vertices of a graph into three subsets which provides information on the structure of maximum matchings in the graph. Tibor Gallai and Jack Edmonds independently discovered it and proved its key properties.

- ↑ P. Erdős: In memory of Tibor Gallai,
*Combinatorica*,**12**(1992), 373–374.

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.