# Coloring Graphs Made Easy?

* A history of expanders, innovation, and coloring graphs *

Mark Pinsker was an eminent mathematician who worked on many aspects of information theory: coding theory, ergodic theory, and communication networks. He received prestigious awards, including the IEEE Claude Shannon Award in 1978, and the IEEE Richard Hamming Medal in 1996.

Today I want to talk about one of his great discoveries and how it relates to our recent discussion on innovation.

His Wikipedia biography has this summary of his achievements:

His accomplishments included a classic paper on the entropy theory of dynamical systems which introduced the maximal partition with zero entropy, later known as Pinsker’s partition. His work in mathematical statistics was devoted mostly to the applications of information theory, including asymptotically sufficient statistics for parameter estimation and nonparametric estimation. He also produced notable results in the theory of switching networks and complexity problems in coding theory.

These are some of the reasons he won two of IEEE’s most distinguished awards. Curiously, only indirect mention is made of the greatest result of his—from the point of view of theory—*expander graphs*. The exact history is a bit complex: I believe that they were first defined in a joint paper of his with Leonid Bassalygo, and then proved to exist by Pinsker alone later in: On the complexity of a concentrator. In the 7 International Teletraffic Conference, 1973. Here he showed that random regular graphs are expanders.

** Innovation **

Pinsker’s paper is a perfect example of a submission to a conference on a practical problem—telephony routing—that would not have been accepted at STOC or FOCS at the time. But the paper contained an idea that changed the face of theory. His interest in expanders and related graphs were driven by telephone-routing problems. At the time, telephone switches were built not out of computers but out of real switches, relays, and wires. Making them contain fewer wires was a real and important problem—saving wires translated into reduced cost and thus increased profits.

This is why his research was at the 7 International Teletraffic Conference, rather than at a theory conference. Other papers at this conference were, for example:

- Leonard Kleinrock and Jiunn Hsu: A Continuum of Computer Processor-Sharing Queueing Models.
- Karoly Koperniczky: Modeling of Telephone Services.
- Denis Breary and James Gates: A Long Term Study of the United Kingdom Trunk Network.

While this conference was happening in Stockholm, FOCS 14 was in Iowa City. Some of the papers there were:

- Emily Friedman: Equivalence Problems in Monadic Recursion Schemes.
- Thomas Szymanski and John Williams: Non-Canonical Parsing.
- Michael Machtey: A Notion of Helping and Pseudo-Complementation in Lattices of Honest Subrecursive Classes.

Clearly the overlap at the time in interests was small. Pinsker’s conference was all about models of traffic, real and simulated. Meanwhile FOCS was all about parsing, models of computing, and correctness of programs.

Who would have guessed that there would be a result at the practical conference that would have changed the world of the theory conference? Indeed. My point is exactly this: suppose back in 1973 we planned a conference on *innovations* in theory. How could we get work like Pinsker’s to appear at the Innovation conference? How could we at least make this possible, even if not probable?

** Expanders **

Since we are already talking about expanders, I thought I would share a simple but potentially useful insight: for many problems expander graphs are near the worst case. This is related to and motivated by the recent work on playing Unique Games on expanders—see here for discussion and links.

Denote a graph as usual and let . For any define to be the **edge boundary** of , i.e. the set of edges with one endpoint in . Also define

This is the **expansion parameter** of . There are other notions of expansion—we will focus just on this single one. A graph is considered an expander provided . Usually we talk about a family of graphs, and insist that all the graphs have their expansion parameter lower-bounded by the same .

** Coloring **

One of the key problems in computational graph theory is to find better methods of coloring a graph that has a -coloring. The current best known upper bounds are essentially of the form: if is -colorable, then there is an algorithm that can color in colors, where is about . See this for example.

The following lemma shows that general graphs are about as hard to approximate as expanders, at least for graphs that can be colored by few colors.

Lemma:Suppose there is a polynomial time algorithm that can color any -colorable graph with colors, provided the graph is an expander with expansion parameter at least . Then, there is a polynomial time algorithm that can color any -colorable graph with colors.

*Proof:* Let be a -colorable graph on vertices. Let be a bipartite graph that is an expander on vertices so that its expansion parameter is at least . Consider the new graph on vertices that has an edge between if either is in or is in . Call this graph .

The new graph is -colorable: just use the coloring from and . That is a vertex gets a pair of colors, and this must be a good coloring of .

Claim: the graph is at least an expander. Assume this for the moment. Then, use the approximation algorithm for -colorable expander graphs. This yields a coloring with at most colors. Clearly this coloring works also for just , and the lemma would follow.

It remains to check the claim. Let be a set of vertices of . Then,

This implies that .

** Open Problems **

What other properties can be reduced to expanders? Does this reduction really help? Also I think graph isomorphism might also be hardest on expanders, but the above argument does not work. Any way what is the complexity of isomorphism for expander graphs?

“This yields a coloring with at most F(n) colors.”

Shouldn’t that be F(n^2), also changing the claim’s statement?

No, the coloring remains the same: You obtain a F(n)-coloring of G^*, and now simply remove the edges of the expander H to get G back. Clearly, the F(n)-coloring is still valid for G.

Neat. But you are not using anything essential about expanders. Here is an attempt at a minimal formulation:

Let P be a graph property satisfying the following conditions:

* P is monotone, i.e. if P holds for a subgraph H of a graph G, then it holds for G

* for any n there is a k-colorable graph G on n vertices, s.t. G is constructible in poly time and it’s k-coloring can be found in poly time

Then if there exists a poly time algorithm that finds a coloring with F(n) colors for a 3*k-colorable graph satisfying property P, there also exists an algorithm that finds a coloring with F(n) colors for any 3-colorable graph.

So the moral seems to be that monotone properties don’t make coloring much easier.

A small note regarding the history of expanders : Though usually the idea of expanders is attributed to Pinsker’s paper from 1973, expander graphs already appeared in a paper of Barzdin and Kolmogorov from 1967 (and later re-discovered by Pinsker). The paper is in Russian but contains a recognizable definition of expanders, a probabilistic proof for the existence of expanders and also a very nice application of expander graphs. I came to know of this from a couple of blog posts (see [1] and [2]) by Emmanuel Kowalski who also describes the Barzdin-Kolmogorov paper in some detail. As Emmanuel also points out in [2] that there is a recent paper on arxiv by Gromov and Guth which discusses and expands the work by Barzdin and Kolmogorov.

I’ve thought about this Lemma when working on the new coloring algorithm with Lasserre Hierarchies. Actually you don’t need to be able to color 6-colorable graphs: it’s enough to color all 4-colorable graphs.

The proof is just by introducing n additional vertices and add a bipartite expander between new vertices and old vertices. Now the graph is 4 colorable (1 color for the new vertices and 3 for the original), it’s also an expander because of the bipartite expander we added. Similarly every coloring for the new graph induces a coloring on the original graph with at most the same number of colors.

We do have an algorithm for expanding 3-colorable graphs if the expansion is really nice in terms of eigenvalues (to be more precise we just find a large independent set, which is progress towards a good coloring), however it does not extend easily to 4-colorable graphs.

There are earlier uses of random constant-degree regular bipartite graphs. They are of course expanders, but the term was not yet defined.

The first reference I know is in von Neumann’s paper “Probabilistic logics and the synthesis of reliable organisms from unreliable components”. They are the basis of his “restoring organ” which reduces errors.

The second reference, which certainly was the inspiration for the work of Pinsker, is Gallager’s low-density parity-check codes.

Tiny typo – In your definition of expander, it should be h(G) instead of h(S).

Also: should be 0 < |S| <= n/2 instead of 0 <= |S| <= n/2

I learned from Lubotzky (http://www.ams.org/amsmtgs/2011_colloquium_lecture_notes_lubotzky_expanders.pdf (page 5)) that already in 1967 Barzdin and Kolmogorov (A. N.Kolmogorov and Y.M. Barzdin, On the realization of nets in 3- dimensional space, Probl. Cybernet, 8, 261–268, 1967) talked about expander graphs and even proved their existence by random methods. (There is a very nice new article of Gromov and Guth (http://arxiv.org/abs/1103.3423), where the results of Barzdin and Kolmogorov are discussed and generalized. )

ps. while looking for references, I found out E. Kowalski has a relevant blog post: http://blogs.ethz.ch/kowalski/2011/02/13/kolmogorov-and-expanders-i/

This is a basic question, but is it even known that k-coloring k-chromatic expanders is NP-hard? I saw this old post on the cstheory stack exchange with no references to coloring: http://cstheory.stackexchange.com/questions/1580/np-hard-problems-on-expander-graphs