Asymmetric out-degree girth bound for bipartite digraphs

Conjecture 1.5 · arXiv:1809.08324

arXiv Conjecture high confidence— first stated 2019-07-24

Authors: Paul Seymour, Sophie Spirkl

Status open medium confidence

Conjecture 1.5 from arXiv:1809.08324 generalizes the Caccetta-Häggkvist conjecture to bipartite digraphs with asymmetric degree conditions. The original paper (Combinatorica 2020) proves the conjecture for k=1 and k=2, and a weaker bound (α+β > 2/(k+1)) for k=3 and k=4. No follow-up paper specifically resolving the full conjecture was found across searches covering 2019–2026; the conjecture remains open alongside the still-unsettled Caccetta-Häggkvist conjecture.

Reviewer notes. The conjecture implies the Caccetta-Häggkvist conjecture (via β→0) and is best possible for infinitely many pairs (α,β). The SIAM paper 'Nonuniform Degrees and Rainbow Versions of the Caccetta-Häggkvist Conjecture' (doi:10.1137/22M1529658, 2023) appeared in searches as potentially related but its content could not be retrieved via WebFetch. arXiv:2102.12830 (Grzesik-Volec, 2021) concerns optimal semidegree thresholds for directed cycles in general oriented graphs, not the bipartite asymmetric setting of this conjecture. No confirmed resolution found.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. For every integer $k \geq 1$, and every pair of reals $\alpha, \beta > 0$ with $k\alpha + \beta > 1$, if $G$ is a non-null bipartite digraph with bipartition $(A, B)$, where every vertex in $A$ has out-degree at least $\beta|B|$, and every vertex in $B$ has out-degree at least $\alpha|A|$, then $G$ has girth at most $2k$.

Context

A conjecture stronger than Conjecture 1.2 (the case $\alpha = \beta$) that also implies the Caccetta-Häggkvist conjecture (via $\beta \to 0$). It is best possible for infinitely many pairs $(\alpha, \beta)$, as witnessed by an explicit circulant-type extremal construction; the maximal bad pairs all lie on the lines $\alpha + k\beta = 1$ or $k\alpha + \beta = 1$.

Source paper

Short directed cycles in bipartite digraphs
Paul Seymour, Sophie Spirkl · 2019-07-24
https://arxiv.org/abs/1809.08324 PDF source