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.
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?
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 .
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 .
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?