A density result for random sparse oriented graphs and its relation to a conjecture of Woodall (Q1856340): Difference between revisions

Let \(h\) \((\geq 3)\) be any given integer and let \(\varepsilon\) be any positive number. The authors show that if \(n\) is sufficiently large then there exists an oriented graph \(G\) with \(n\) vertices and \(e= O(n^{h/(h- 1)})\) arcs and girth \(h\) such that if \(k/e\geq 1/2+ \varepsilon\), then any \(k\) arcs of \(G\) induce an oriented cycle of length \(4\).