A Density Result for Random Sparse Oriented Graphs and its Relation to a Conjecture of Woodall

Abstract

We prove that for all $\ell \ge 3$ and $\beta >0$ there exists a sparse oriented graph of arbitrarily large order with oriented girth $\ell$ and such that any $1/2 + \beta$ proportion of its arcs induces an oriented cycle of length $\ell$. As a corollary we get that there exist infinitely many oriented graphs with vanishing density of oriented girth $\ell$ such that deleting any $1/\ell$-fraction of their edges does not destroy all their oriented cycles. The proof is probabilistic.