Extending an old conjecture of Tutte, Jaeger conjectured in 1988 that for any fixed positive integer p, the edges of any 4p-edge connected graph can be oriented so that the difference between the outdegree and the indegree of each vertex is divisible by 2p+1. It is known that it suffices to prove this conjecture for (4p+1)-regular, 4p-edge connected graphs. I will show that there exists a finite p_0 so that for every p>p_0 the assertion of the conjecture holds asymptotically almost surely for random (4p+1)-regular graphs. The proof is based on the spectral properties of these graphs, and applies to (appropriately defined) pseudo-random (4p+1)-regular graphs as well. (This is a joint work with Noga Alon.)
I hope to be able to announce that the conjecture holds asymptotically almost surely for random 5-regular graphs which corresponds to the conjecture of Tutte. (Work in progress with Nick Wormald.)
The ACO Seminar (2010-2011)