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 
edges. Clearly, this forces
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.
Flow Conjectures
Suppose that 
A flow is a 
It is called a called nowhere-zero 
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.
Tensor Trick
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
zeroes. Then, the nowhere-zero
Sketch of Proof
The proof is based on the notion of amplification. Suppose that 
More precisely, assume that
Call this resulting graph 
For enough copies of
Recall we added the extra two edges to
The flow must satisfy
The last equality holds since the net flow into a subgraph must be 
Open Problems
Can these tensor results be used to actually prove the nowhere-zero
Can the same tensor ideas be used on other open questions concerning graphs? We believe it can also work on Tutte 
The tensor method may apply, we think, to other graph conjectures like the Double Cover Conjecture. See Melody Chan’s 2009 paper for details.
See my algorithmic three edge coloring of the bridgeless cubic planar graphs.
1. http://www.flickr.com/photos/49058045@N00/4452379002/
(Edge three coloring of the Grinberg- graph)
2. http://www.flickr.com/photos/49058045@N00/710394490/
3. http://arxiv.org/abs/math/0507127
(Spiral Chains: The Proofs of Tait’s and Tutte’s Three-Edge-Coloring Conjectures)
Amongst the numerous discoveries made by William Tutte one that I found pretty remarkable (because it is easy enough for me to understand) concerns the problem of tiling a bigs square with smaller squares all of which have different sizes.
The wonderful method Tutte and party used at Cambridge when they were around 19 or 20 involved a detour among all things to electrical networks which almost magically solved the problem.
I came across his work in a book by Martin Gardner who sadly passed away on May 22 this year.
Could you please explain this statement in a bit more detail –
“For enough copies of {G} there must be a {5}-flow of {H} with so few zeroes that one copy of {G} and its extra edges are all non-zero.”
I am sorry but I could not follow this one.
Naman,
Sure, I was pretty brief. The graph H has cn vertices for a fixed c that depends just on the size of G. So let n be large. Then, the number of edges with zeroes is by assumption o(n). So eventually, cn >> o(n) and so one whole copy of G must be zero free. Otherwise, there would be too many zeroes.
I hope this helps.
Pardon me if the doubt is a bit trivial, but I don’t understand how the following holds…
“For enough copies of {G} there must be a {5}-flow of {H} with so few zeroes that one copy of {G} and its extra edges are all non-zero.”
Please reply or give a pointer to relevant pointer to the concept.
Say there are $x$ copies of $G$, $G$ has $i$ vertices and the cycle has $j$ vertices.
Then, the graph $H$ has $x(i+2)+j$ vertices and there are only $Z = o(x(i+2)+j)$ zeroes.
This means that as $x \rightarrow \infty$, $\tfrac{x(i+2)+j}{Z} \rightarrow \infty$. So
\[\lim_{x \rightarrow \infty} \frac{x(i+2)+j}{Z} = \lim_{x \rightarrow \infty} (i+2)\frac{x}{Z}+\frac{j}{Z} = \infty\]
\[\lim_{x \rightarrow \infty} \frac{x}{Z} = \infty\]
For $x$ large enough, $x>Z$. By pigeonhole, there must be a copy of $G$ without zeroes.
Not sure what this means…
I’m sorry, I thought I could use latex. Here goes a non-latex version:
Say there are x copies of G, G has i vertices and the cycle has j vertices.
Then, the graph H has x(i+2) + j vertices and there are only Z = o( x(i+2) + j ) zeroes.
This means that as x➝∞, ( x(i+2) + j )/Z➝∞. So
lim_{x➝∞} [ ( x(i+2) + j )/Z ] = lim_{x➝∞} [ (i+2)*x/Z + j/Z ] = ∞
lim_{x➝∞} [ x/Z ] = ∞
Thus, for x large enough, x>Z. By pigeonhole, there must be a copy of G without zeroes.