A density result for random sparse oriented graphs and its relation to a conjecture of Woodall
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\).
scientific article; zbMATH DE number 1862490