# Colorings and embeddings of graphs

My previous post was about the mathematician John Conway, who died recently from COVID-19. This post is a tribute to my Georgia Tech School of Mathematics colleague Robin Thomas, who passed away on March 26th at the age of 57 following a long struggle with ALS. Robin was a good friend, an invaluable member of the Georgia Tech community, and a celebrated mathematician. After some brief personal remarks, I’ll discuss two of Robin’s most famous theorems (both joint with Robertson and Seymour) and describe the interplay between these results and two of the theorems I mentioned in my post about John Conway.

We will deduce this from a more general result due to Philip Hall commonly known as Hall’s Marriage Theorem.  Suppose you are given finite sets $A_1, A_2,\ldots, A_n$ and you wish to find distinct elements $x_1 \in A_1,\ldots, x_n \in A_n$.  (In our solitaire example, take $A_j$ to be the values of the cards in the $j^{\rm th}$ pile.)  Such a collection is called a transversal or SDR (system of distinct representatives).  Under what conditions is this possible?  Well, for a transversal to exist it is necessary that for each subset $J \subset \{ 1,\ldots, n \}$, the set $A_J:= \bigcup_{j \in J} A_j$ contains at least $\#J$ elements.  Hall’s theorem asserts that these conditions are also sufficient. Continue reading