Circumference equivalence vertex transitive digraphs

Conjecture 4.2 · arXiv:2602.16333

arXiv Conjecture high confidence— first stated 2026-02-18

Authors: Matija Bucić, Kevin Hendrey, Bojan Mohar, Raphael Steiner, Liana Yepremyan

Status open high confidence

Conjecture 4.2 from arXiv:2602.16333 proposes that the minimum circumference of connected vertex transitive digraphs and undirected graphs on n vertices are asymptotically equivalent: d(n) = Θ(c(n)). The source paper establishes the first nontrivial lower bound Ω(n^{1/3}) for the directed case, while the best undirected bound stands at Ω(n^{9/14}) (improved to Ω(n^{13/21}) by Groenland et al., arXiv:2408.04618, predating this conjecture). No follow-up paper resolving or making further progress on the conjecture has been found in the three months since posting.

Reviewer notes. No follow-up found. The conjecture is very recent (posted 2026-02-18, reviewed 2026-05-14). The gap between the directed bound Omega(n^{1/3}) and the undirected bound Omega(n^{9/14}) is the main motivation. The related undirected paper arXiv:2408.04618 (Groenland et al., 2024) improves the undirected bound to Omega(n^{13/21}) but predates the conjecture.

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

Conjecture. Let $c(n)$ denote the minimum circumference of a connected vertex transitive graph on $n$ vertices. Let $d(n)$ denote the minimum circumference of a connected vertex transitive digraph on $n$ vertices. Then $d(n)=\Theta(c(n))$.

Context

The paper's bound of $\Omega(n^{1/3})$ on the circumference of connected vertex transitive digraphs is slightly weaker than the best known $\Omega(n^{9/14})$ undirected bound. This conjecture asserts that the directed and undirected cases are asymptotically the same, proposed as a natural intermediate target.

Source paper

Long cycles in vertex transitive digraphs
Matija Bucić, Kevin Hendrey, Bojan Mohar, Raphael Steiner, Liana Yepremyan · 2026-02-18
https://arxiv.org/abs/2602.16333