Linear perimeter gap in vertex-transitive digraphs

Conjecture 4.1 · 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.1 from arXiv:2602.16333 asserts that the perimeter gap in connected vertex transitive digraphs can be linear in the order n, i.e., there exist ε > 0 and infinitely many n for which the gap is at least εn. The source paper itself establishes only a logarithmic lower bound of (1-o(1)) ln n on the maximum perimeter gap and a circumference lower bound of Ω(n^{1/3}), and proposes the conjecture as a natural intermediate target asserting the logarithmic bound is far from tight. No follow-up paper addressing this conjecture was found in the three months since the paper was posted.

Reviewer notes. No follow-up found. The paper is very recent (February 2026, ~3 months before review date). The related undirected paper arXiv:2408.04618 (Longest cycles in vertex-transitive and highly connected graphs, Bulletin of the London Mathematical Society 2025) predates the source paper and addresses the undirected setting only; it is not a follow-up to this conjecture.

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

Conjecture. There exists an $\varepsilon>0$ and infinitely many values of $n$ for which there exists a connected vertex transitive digraph of order $n$, whose perimeter gap is at least $\varepsilon n$.

Context

The paper proves the perimeter gap grows at least as fast as $(1-o(1))\ln n$ and that circumference is always at least $\Omega(n^{1/3})$. Determining the best possible bounds seems far out of reach; this conjecture is proposed as a natural intermediate target, asserting that the logarithmic lower bound on the gap is far from tight.

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