The Tensor Trick and Tutte’s Flow Conjectures
An approximation approach to the 5-flow conjecture of Tutte
William Tutte was one of the founders of modern graph theory. He left his mark on almost all aspects of graph theory, and both solved hard problems and created much of the foundations of graph theory. He was a Fellow of the Royal Society, and won many other awards for his seminal work.
Today I will talk about a new result that is joint with Atish Das Sarma. It concerns a famous open problem of Tutte, and a new approach to the problem.
Peter Tait thought he had proved the four color theorem in 1880. He did prove that the four color theorem was equivalent to proving that every cubic bridgeless planar graph was three edge colorable. He then “proved” that there was always a three edge coloring by asserting the following: every such graph has a Hamiltonian Cycle. If this was true—it is not—then there is an easy way to three-color the edges. Color the edges on the cycle alternately green and blue. Then, color all the remaining edges yellow. This is a legal three coloring.
The cycle must have an even number of edges; otherwise, the alternation of colors will fail. I once got a negative referee report back on a paper from an unnamed conference, saying this was a problem—what if the Hamiltonian Cycle had an odd number of edges. Well, the number of edges on such a cycle is the same as the number of vertices. And, of course, every cubic graph has an even number of vertices. The proof of this is simple: the degree of each node is so the vertices have
edges. Clearly, this forces to be even, since we cannot have graphs with a fractional number of edges. Oh well.
The statement of Tait stood for decades, until Tutte thought about it. In 1946 he discovered the following graph:
This graph is easily seen to be cubic, planar, and bridgeless. Also a simple case argument shows there is no Hamiltonian Cycle. Tait was wrong, and his proof of the four color theorem was incorrect. It would be exactly thirty years until a proof of the Four-Color Theorem would be found, but a computer proof, a proof nonetheless by Kenneth Appel and Wolfgang Haken.
Suppose that is a undirected graph. Direct the edges of the graph in any manner at all; it will turn out not to make any difference. Then a flow is a mapping from the edges to the integers, so that Kirchhoff’s Rule is satisfied: the amount flowing into each vertex is the same as the amount flowing out of the vertex. Formally, for each vertex , let be the edges directed to and the edges directed from . Then
A flow is a -flow if the values are all in the range
It is called a called nowhere-zero -flow provided is never .
Tutte made a number of conjectures about nowhere-zero flows on graphs; he was motivated by the coloring theorems for planar graphs. His conjectures have been partially solved, but some are still open. In particular he conjectured:
Conjecture: Every bridgeless graph has a nowhere-zero -flow.
The best known to date is François Jaeger’s 8-flow theorem and Paul Seymour’s 6-flow theorem. See this for a nice survey of what is known about flows.
One of the powerful ideas in science and mathematics is the notion of amplification. I have discussed this before—see this. Sometimes amplification is called the Tensor Trick: it is a simple idea, but can yield surprisingly powerful consequences.
Theorem: Suppose all bridgeless graphs on vertices have -flows with zeroes. Then, the nowhere-zero -flow conjecture is true.
Sketch of Proof
The proof is based on the notion of amplification. Suppose that is a graph that is a counter-example graph. That is, every -flow on has at least one zero. Then we construct another graph that contains many copies of . Moreover, if there is a flow on that has zeroes, then there is a way to recover a perfect nowhere-zero flow for .
More precisely, assume that is a bridgeless graph without a nowhere-zero -flow. Create many copies of and attach them via two edges to a cycle. In the picture below, the blue graphs are copies of , and the yellow cloud is a cycle.
Call this resulting graph . It is important to see how we do this attachment. We take an edge of and split it into three edges and add edges to the cycle. See the picture below.
For enough copies of there must be a -flow of with so few zeroes that one copy of and its extra edges are all non-zero. The last step of the proof is to argue that we can use these values on and the extra edges to create a valid nowhere-zero flow for .
Recall we added the extra two edges to as in the following figure. We are using the edge labels to also stand for their values—to avoid excessive notation.
The flow must satisfy
The last equality holds since the net flow into a subgraph must be . Then it is easy to see that . This shows we can collapse and join the edge and into one, since they have the same value. This collapse forms the original graph , since this replaces the edge we split into three pieces. Note, the resulting flow is non-zero, and this yields a nowhere-zero -flow for .
Can these tensor results be used to actually prove the nowhere-zero -flow conjecture?
Can the same tensor ideas be used on other open questions concerning graphs? We believe it can also work on Tutte -flow conjecture, but there are some details to be checked. The above method does not depend on the flow being a -flow. Tutte’s nowhere-zero -flow conjecture has an additional constraint on the family of graphs, since some bridgeless graphs do not have -flows.
The tensor method may apply, we think, to other graph conjectures like the Double Cover Conjecture. See Melody Chan’s 2009 paper for details.