In Rome we have an expression, mai una gioia (literally, “never (a moment of) joy”) that applies well to the present times. Yesterday, there was, finally, something to be joyous about: the announcement that two of my heroes, Laszlo Lovasz and Avi Wigderson, will share the 2021 Abel Prize, one of the highest honors of mathematics.
The reader can find a very good article about them on Quanta Magazine.
Instead of talking about their greatest accomplishment, here I would like to recall two beautiful and somewhat related results, that admit a short treatment.
Avi’s first paper was on the 3-coloring problem. He described a polynomial time algorithm that, given a 3-colorable graph , finds a valid coloring of with colors, where is the number of vertices. The starting point is that if every vertex in had degree then there is an easy way to color the graph with colors (look at the vertices in any order, choose for each vertex a color not already used for the neighbors that have already been considered).
What if there is some vertex of degree ? Well, and this is the idea of the paper, the neighbors of must induce a bipartite subgraph, so we can color the neighbors of with 2 colors in a way that is consistent with all the edges between neighbors of , then remove the neighbors of and continue with the rest of the graph, committing to never use those two colors again. Every time we do this, we consume two colors but we get rid of vertices, so this costs us at most colors. When we are done, all remaining vertices have degree and we just need more colors as observed above.
In total, we used at most colors.
This remained the state of the art for approximate graph coloring for a few years, until Avrim Blum improved the bound for 3-colorable graphs to and then to colors, using more sophisticated combinatorial arguments. Later, Karger, Motwani and Sudan devised an approximation algorithm that uses colors to color 3-colorable graphs, and is based on a semidefinite programming relaxation of the coloring problem, which is related to the Lovasz theta function. It is still open whether there is a polynomial time algorithm that uses colors.
The Lovasz theta function of a graph is a convex relaxation of the maximum independent set problem in . It is, or it can be formulated as, a semidefinite programming relaxation of the maximum independent set problem, and so it can be computed (up to arbitrarily good accuracy) in polynomial time.
Lovasz defined the theta function to study the Shannon capacity of a graph. This is a question that arises when one wants to find error-correcting codes for a channel that may introduce errors. Suppose that the channel carries an element of an alphabet of size , and that certain pairs of alphabet elements can be “confused” by the channel, meaning that for certain pairs the channel may output given or viceversa. If we construct the graph whose vertex set is and whose edges are the pairs of “confusable” pairs, then an independent set in this graph gives a set of length-1 codewords that are not confusable, and , where is the size of a maximal independent set in , is the number of bits that we can transmit in an errorless way by making one use of the channel. If we can access the channel times, then an errorless code is an independent set in , the graph that has vertex set and such that is an edge if and only if all the pairs are edges of . The number of bits of information per channel use that we can send is
and so we are interested in
Nicely, we have
so we have
and the theta function provides an upper bound to the Shannon capacity of a graph.
If we compute , where is the complement of the graph (that is, the graph whose edges are all the non-edges of ), then we see that is a relaxation of the maximum clique problem in . Remarkably, is also a lower bound to the chromatic number of , and so it is sandwiched between the clique number and the chromatic number. Don Knuth has used this fact as a starting point for a wonderful 49-page treatise on convex relaxations of the chromatic number and the clique number; here we will see a quick proof of this fact.
As you can see in Knuth’s survey, there are several equivalent ways to define the theta function. Below we define as a natural semidefinite programming relaxation of the maximum clique problem (we have a variable plus one variable for every vertex ; all variables are vectors).
To see that it is a relaxation, given a clique , let be any unit vector, and let for and for . We satisfy all constraints and the objective function is .
If we write the semidefinite dual of the above relaxation, we can see that we get a minimization problem which is a relaxation of the chromatic number problem (and which is equivalent to the relaxation used by Karger, Motwani and Sudan to improve on Avi’s result on 3-coloring), so that the “sandwich theorem” follows from weak duality.
The reader should try to write down the semidefinite dual and reason about why it relaxes the chromatic number problem. Below, we collapse the construction of the dual, the way of embedding colorings into dual solutions, and the proof of weak duality for semidefinite programming, into a short but mystifying “sum of squares” proof.
Suppose that and let be a feasible solution to the max clique relaxation defined above. Suppose that the graph is -colorable and let be a partition of into color classes. We have
so that the objective function always satisfies
In particular, this is true for an optimal solution and for an optimal coloring, so we have that is upper bounded by the chromatic number of as promised.
Above, we used various properties of feasible solutions, such as , and
which follows from the fact that each color class is an independent set, and so all inner products for have to be equal to zero, because .