Cycle lengths in vertex-transitive digraphs
Question 4.4 · arXiv:2602.16333
Status open high confidence
Question 4.4 asks whether there exists a constant C>0 such that in any vertex transitive digraph the length of a longest path is at most a factor of C larger than the length of a longest directed cycle. The source paper itself establishes Omega(n^{1/3}) for cycles and Omega(sqrt(n)) for paths, exhibiting a gap between the two quantities, and notes that in the undirected setting the analogous ratio is bounded by a constant. No follow-up resolving this question was found in the three months since posting.
Reviewer notes. Question 4.4 full statement (retrieved from arXiv HTML): 'Does there exist C>0 such that in any vertex transitive digraph, the length of a longest path is by at most a factor of C larger than the length of a longest directed cycle?' The paper's own results show Omega(n^{1/3}) cycle length and Omega(sqrt(n)) path length, so the ratio is not trivially 1, but whether it is bounded by a constant remains open. No follow-up paper addressing this question was found; the conjecture is very recent (February 2026).
Context
Appears as a labelled question environment in the concluding remarks section alongside Question 4.3, but its full statement was not included in the provided paper content.
Notes. Statement not available in the provided input; only the label [qn] was given with no accompanying text.
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