Short directed cycles in bipartite digraphs (Q2221004)

It was conjectured in the literature that for every integer \(k\) greater or equal to 1, and all \(n\) greater than 0, every \(n\)-vertex digraph in which every vertex has out-degree at least \(n/k\) has girth at most \(k\), which implies that for every integer \(k\) greater or equal to 1, if \(G\) is a bipartite digraph, with \(n\) vertices in each part, and every vertex has out-degree more than \(n/(k+1)\), then \(G\) has a directed cycle of length at most \(2k\). The purpose of the present paper is to show that if this is true, then this is best possible for \(k = 1, 2, 3, 4, 6\) and all \(k\) greater or equal to \(224.539\).\par For a given digraph \(G\) with a bipartition \((A, B)\) and for real \(a, b\) greater or equal to 0, we say that \(G\) is \((a, b)\)-compliant or complies with \((a, b)\) if \(G\) is non-null and every vertex in \(A\) has at least \(b\vert B\vert \) out-neighbors in \(B\) and every vertex in \(B\) has at least \(a\vert A\vert \) out-neighbors in \(A\). The paper is to show that for an integer \(k\) greater or equal to 1, if \(a\) is greater than \(1/(k +1)\), and if \(G\) is an \((a, a)\)-compliant digraph via a bipartition \((A, B)\), such that every vertex in \(A\) has in-degree exactly \(a\vert B\vert \), and every vertex in \(B\) has in-degree exactly \(a\vert A\vert \), then \(G\) has girth at most \(2k\), and that for all \(a, b\) greater than 0 with \(a + b\) greater than \(2/5\), every \((a, b)\)-compliant digraph has girth at most eight.