Cycle lengths in vertex-transitive digraphs

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).

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