Jaeger-type orientations of random regular graphs

Abstract

We consider $p$-orientations, which are defined to be orientations of $d$-regular graphs such that every vertex either has in-degree $p$ or out-degree $p$. These generalise the orientations considered in Jaeger's conjecture, where $d=4p+1$. Working with random $d$-regular graphs using the small subgraph conditioning method, we prove that a $d$-regular graph has a $p$-orientation with high probability for several values of $(d,p)$, including the $p=3,4$ cases of Jaeger's conjecture (known to be deterministically false). Some negative results are obtained by exploiting a connection with maximum bisection size.

37 pages