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.

Robin Thomas was born in Prague, Czechoslovakia and received his doctorate from Charles University. He came to Georgia Tech in 1989 and served as director of our renowned interdisciplinary Ph.D. program in ACO (Algorithms, Combinatorics, and Optimization) from 2006-2019. As Georgia Tech Professor Emeritus Gary Parker puts it, “In my mind, Robin Thomas was ACO.” Robin graduated 16 Ph.D. students from Georgia Tech, including my collaborator Serguei Norine (see this blog post for the story of how I ended up collaborating with Serguei; it would not have happened without Robin).

Robin Thomas’s work in graph theory earned him significant acclaim. He was a two-time winner of the Fulkerson Prize, which is awarded once every three years for outstanding papers in Discrete Mathematics. He was an invited speaker at the 2006 International Congress of Mathematicians in Madrid (I attended the fascinating talk he gave there). And he won all of Georgia Tech’s highest honors, including (in 2016) the institute’s Distinguished Professor award.

The physical ravaging which Robin suffered from the relentless march of ALS was painful to watch, but Robin handled it with gritty tenacity. He continued to teach classes, run the ACO program, supervise students, and write papers until nearly the end of his life despite being confined to a wheelchair and gradually losing both motor control and the ability to speak. My family and I visited Robin, his wife, and their three children a number of times during Robin’s long illness; Robin was extremely devoted to them and vice-versa.

Here is a short video of my Georgia Tech colleagues and I taking part in the ALS Ice Bucket Challenge in 2014 as a show of solidarity with Robin:

Hadwiger’s conjecture

One of Robin’s most famous results (for which he won the first of his two Fulkerson prizes) was his 1993 proof, with Robertson and Seymour, of Hadwiger’s conjecture for graphs without a K_6-minor. Motivated by the four-color conjecture, Hugo Hadwiger conjectured in 1943 that any graph with no minor isomorphic to the complete graph K_t admits a (t-1)coloring. For t=3, this follows from the easy fact that a graph with no K_3-minor must be bipartite, and for t=4 it’s a not-too-difficult theorem of Hadwiger.

The t=5 case of Hadwiger’s conjecture is equivalent to the four-color theorem, first proved by Appel and Haken (the proof was later greatly simplified by Robertson, Samuels, Seymour, and Thomas). Indeed, by the Kuratowski-Wagner theorem a non-planar graph must have a minor isomorphic to either K_{3,3} (which is 2-colorable) or K_5.

The t=6 case was proved by Robertson-Seymour-Thomas, and the conjecture is still open for t \geq 7.

Linklessly embeddable graphs are 5-colorable

A graph is called intrinsically linked if every embedding in {\mathbb R}^3 contains a pair of linked cycles, and linklessly embeddable otherwise. The first nontrivial result about such graphs was the theorem (proved independently by Conway-Gordon and Horst Sachs; see Chapter 8 in Colin Adams’s The Knot Book for a nice exposition) that K_6 is intrinsically linked.

Linked cycles in a spatial embedding of K_6 (Source: “The Knot Book”)

By the K_6-free case of Hadwiger’s conjecture, it follows that every linklessly embeddable graph is 5-colorable.

Forbidden minors for linklessly embeddable graphs

The other theorem of Robertson-Seymour-Thomas which I’d like to highlight is their classification (announced in 1993 and published in 1995) of the forbidden minors for linklessly embeddable graphs. The property of being linklessly embeddable is minor-closed (this was first proved by Robin Thomas and his thesis advisor Nešetril), so by the celebrated Robertson-Seymour theorem it can be characterized by a finite set of excluded minors.

We’ve already seen that a graph with a K_6-minor is intrinsically linked, and the same is true for the famous Petersen graph. Sachs found five other minor-minimal graphs which are intrinsically linked; together, these seven graphs are now known as the Petersen family. The theorem of Robertson-Seymour-Thomas asserts, conversely, that a graph with no minor belonging to the Petersen family is linklessly embeddable.

The 7 intrinsically linked graphs in the Petersen family (Credit: David Eppstein)

Linklessly embeddable graphs are a natural generalization of planar graphs, and in this sense one can view the Robertson-Seymour-Thomas theorem as a (vastly more difficult) analogue of the Kuratowski-Wagner theorem.

Colin de Verdiere’s Conjecture

One way to see that linklessly embeddable graphs are a natural extension of planar graphs is through the lens of the Colin de Verdiere number, a fascinating invariant of graphs of spectral origin. The definition, which is rather bewildering at first sight, is as follows. Let G be a graph on with vertices v_1,\ldots,v_n. The Colin de Verdiere number of G is the maximum size of the nullspace of an n \times n real symmetric matrix M=(M_{ij}) such that:

(1a) M_{ij}=0 if i \neq j and there is no edge of G between v_i and v_j.

(1b) M_{ij}<0 if there is an edge of G between v_i and v_j.

(2) M has precisely one negative eigenvalue (counting multiplicities).

(3) If X=(X_{ij}) is an n \times n real symmetric matrix with MX=0 and X_{ij}=0 whenever i=j or M_{ij} \neq 0, then X=0.

Property (3) is called the Strong Arnol’d Property, and geometrically it means that the space of matrices with the same-sign eigenvalues as M and the space of matrices with the same-sign off-diagonal entries as M intersect transversely at M.

The set {\mathcal C}_k of graphs with Colin de Verdiere number at most k is minor-closed. Moreover:

  • {\mathcal C}_2 is the set of outerplanar graphs (graphs with a planar drawing where all vertices belong to the outer face).
  • {\mathcal C}_3 is the set of planar graphs.
  • {\mathcal C}_4 is the set of linklessly embeddable graphs. (This was conjectured by Robertson-Seymour-Thomas and proved by Lovasz and Schrijver.)

Colin de Verdiere conjectured that every graph in {\mathcal C}_k is (k+1)-colorable. One can show that K_t has Colin de Verdiere number t-1, and therefore Hadwiger’s conjecture implies Colin de Verdiere’s conjecture. In particular, by the four-color theorem and the work of Robertson-Seymour-Thomas, Colin de Verdiere’s conjecture is true for k\leq 4.

Intinsically knotted graphs

A graph G is intrinsically knotted if, for every embedding of G in {\mathbb R}^3, some cycle of G is embedded as a non-trivial knot. The first example of an intrinsically knotted graph, K_7, was discovered by John Conway (and later published in his paper with Cameron Gordon).

Let’s call a graph knotlessly embeddable if it is not intrinsically knotted (try saying that three times fast). Any graph with an intrinsically knotted minor is also intrinsically knotted. By the Robertson-Seymour theorem, it follows that the class of knotlessly embeddable graphs admits a finite set of excluded minors. One might hope, by analogy with the class of linklessly embeddable graphs, for a simple characterization or enumeration of these excluded minors. Unfortunately, this appears to be fiendishly difficult: there are more than 250 known minimal intrinsically knotted graphs.

Parting thoughts

Of course, I’ve barely scratched the surface here, both in terms of Robin Thomas’s contributions to mathematics (he published over 115 papers from 1984 to 2019) and on the subjects of graph colorings and graph embeddings. But I hope this little panoply helps highlight some of the marvelous contributions of Robin Thomas (and John Conway) to the subject.

One thought on “Colorings and embeddings of graphs

  1. Pingback: Some Mathematical Gems from John Conway | Matt Baker's Math Blog

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s