Modular Orientations of Random and Quasi-Random Regular Graphs

Source abstract

Extending an old conjecture of Tutte, Jaeger conjectured in 1988 that for any fixed integer p ≥ 1, the edges of any 4 p -edge connected graph can be oriented so that the difference between the outdegree and the indegree of each vertex is divisible by 2 p +1. It is known that it suffices to prove this conjecture for (4 p +1)-regular, 4 p -edge connected graphs. Here we show that there exists a finite p 0 such that for every p > p 0 the assertion of the conjecture holds for all (4 p +1)-regular graphs that satisfy some mild quasi-random properties, namely, the absolute value of each of their non-trivial eigenvalues is at most c 1 p 2/3 and the neighbourhood of each vertex contains at most c 2 p 3/2 edges, where c 1 , c 2 > 0 are two absolute constants. In particular, this implies that for p > p 0 the assertion of the conjecture holds asymptotically almost surely for random (4 p +1)-regular graphs.