pith. sign in

arxiv: 2606.09742 · v1 · pith:3EB3ALT2new · submitted 2026-06-08 · 🧮 math.CO

Towards the Lov\'{a}sz conjecture via sublinear expanders

Matija Buci\'c , Micha Christoph , Alexey Pokrovskiy , Raphael Steiner This is my paper

Pith reviewed 2026-06-27 15:54 UTC · model grok-4.3

classification 🧮 math.CO
keywords vertex-transitive graphscycle lengthLovász conjecturesublinear expandersHamiltonian pathsgraph decompositionsexpander graphslong cycles
0
0 comments X

The pith

Every connected vertex-transitive graph of order n contains a cycle of length at least n^{2/3-o(1)}.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves a new lower bound on the longest cycle in any connected vertex-transitive graph on n vertices. It shows these graphs always contain a cycle whose length is at least n raised to the power 2/3, minus a term that goes to zero. This improves the earlier guarantee of roughly n to the 9/14 and narrows the gap to the Lovász conjecture that such graphs contain Hamiltonian paths. The argument works by embedding long paths inside sublinear expanders after decomposing the input graph into almost-regular pieces that keep enough expansion. A reader would care because the result rules out the possibility that vertex-transitive graphs can be forced to have only short cycles.

Core claim

The central claim is that every connected vertex-transitive graph of order n contains a cycle of length at least n^{2/3-o(1)}. The proof combines embedding techniques for paths in sublinear expanders, sublinear expander decompositions of almost-regular graphs, and additional combinatorial ideas. This bound improves the previous best lower bound of Omega(n^{9/14}) and reaches a natural barrier for several existing approaches.

What carries the argument

Embedding techniques for paths in sublinear expanders together with sublinear expander decompositions of almost-regular graphs.

If this is right

  • The longest cycle in any connected vertex-transitive graph is at least n^{2/3-o(1)} long.
  • The exponent in the known lower bound improves from 9/14 to 2/3.
  • The result reaches a natural barrier for several prior approaches to the problem.
  • The same techniques show that vertex-transitive graphs cannot have all cycles confined to a shorter length scale.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same embedding methods may also yield long paths of comparable length in the same graphs.
  • Removing the o(1) term in the exponent would bring the bound closer to linear in n.
  • The decomposition approach could be tested on other highly symmetric graph families to see if similar length gains appear.
  • Further work might check whether the barrier at 2/3 is an artifact of the current expander techniques or a deeper limit.

Load-bearing premise

The embedding and decomposition methods retain enough expansion when applied to vertex-transitive graphs to produce cycles of the stated length.

What would settle it

A connected vertex-transitive graph on n vertices whose longest cycle has length at most n^{2/3 - c} for some fixed c greater than zero and for infinitely many n would disprove the claim.

read the original abstract

Lov\'{a}sz' famous Hamiltonicity conjecture (1969) states that every connected vertex-transitive graph has a Hamiltonian path. A stronger version of the conjecture, often attributed to Thomassen (1978), states that every sufficiently large such graph even has a Hamiltonian cycle. Despite the great amount of attention these conjectures have attracted over the past decades both in the combinatorial and algebraic communities, for more than 40 years the best known lower bound for the maximum length of a cycle (path) in a connected vertex-transitive graph of order $n$ remained of the form $\Omega(\sqrt{n})$, due to Babai (1979). A series of recent works has successively improved the exponent in this lower bound further. In this paper, improving the previous state-of-the-art bound $\Omega(n^{9/14})$ due to Norin et al.~(2025), we prove that every connected vertex-transitive graph of order $n$ contains a cycle of length at least $n^{2/3-o(1)}$. This hits a natural barrier for several existing approaches from previous work. Our proofs combine recent embedding techniques for paths in sublinear expanders, sublinear expander decompositions of almost-regular graphs, and several additional combinatorial ideas.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The manuscript proves that every connected vertex-transitive graph of order n contains a cycle of length at least n^{2/3-o(1)}, improving the prior bound of Ω(n^{9/14}) from Norin et al. The argument combines path-embedding lemmas for sublinear expanders, sublinear expander decompositions of almost-regular graphs, and additional combinatorial arguments tailored to the vertex-transitive setting.

Significance. If correct, the result constitutes a substantial advance on the longest-cycle problem in vertex-transitive graphs and moves the best-known exponent past the previous 9/14 barrier. The explicit attribution of the o(1) loss to quantitative parameters of existing embedding and decomposition theorems, together with the direct applicability of the decomposition step to regular graphs, strengthens the contribution.

major comments (2)
  1. [Section 3] The central claim relies on the sublinear-expander decomposition preserving sufficient expansion after the almost-regular decomposition step; a concrete verification that the expansion parameters survive the decomposition with only o(1) loss in the exponent is needed in the main proof (likely around the application of the decomposition theorem to the vertex-transitive input).
  2. [Section 4] The embedding lemma for paths in sublinear expanders is invoked to obtain the n^{2/3} term; the precise dependence of the hidden o(1) on the expansion parameter and the degree must be tracked explicitly through the composition with the decomposition to confirm the final exponent (see the quantitative statement of the embedding result used in the proof of the main theorem).
minor comments (3)
  1. [Abstract] The abstract refers to 'several additional combinatorial ideas' without naming them; a one-sentence list of these ideas in the abstract or introduction would improve readability.
  2. [Section 2] Notation for the sublinear expansion parameter (typically denoted something like h or φ) should be introduced once and used consistently; occasional switches between different symbols appear in the technical sections.
  3. [Introduction] A short table comparing the new exponent 2/3-o(1) with the sequence of prior exponents (Babai, Norin et al., etc.) would help readers track progress.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment and the recommendation of minor revision. The comments correctly identify places where making the quantitative parameter tracking more explicit will improve readability. We respond to each major comment below and will incorporate the clarifications in the revised manuscript.

read point-by-point responses

  1. Referee: [Section 3] The central claim relies on the sublinear-expander decomposition preserving sufficient expansion after the almost-regular decomposition step; a concrete verification that the expansion parameters survive the decomposition with only o(1) loss in the exponent is needed in the main proof (likely around the application of the decomposition theorem to the vertex-transitive input).

    Authors: We agree that an explicit verification strengthens the presentation. While the o(1) loss is already attributed to the quantitative parameters of the cited decomposition theorem, we will add a short paragraph immediately following the application of the decomposition in Section 3. This paragraph will recall the precise expansion and degree bounds guaranteed by the decomposition theorem and verify that, when applied to the almost-regular graph arising from the vertex-transitive input, the resulting sublinear expander retains an expansion parameter of the form n^{-o(1)} sufficient to preserve the overall 2/3-o(1) exponent. This is a minor textual addition that does not alter the proof. revision: yes

  2. Referee: [Section 4] The embedding lemma for paths in sublinear expanders is invoked to obtain the n^{2/3} term; the precise dependence of the hidden o(1) on the expansion parameter and the degree must be tracked explicitly through the composition with the decomposition to confirm the final exponent (see the quantitative statement of the embedding result used in the proof of the main theorem).

    Authors: We accept this request for greater explicitness. In the revised proof of the main theorem we will insert a brief parameter-tracking step that composes the quantitative statement of the embedding lemma (including its dependence on the expansion parameter and maximum degree) with the output parameters of the decomposition. This will make transparent that the hidden o(1) term remains o(1) after composition and yields the claimed n^{2/3-o(1)} bound. The addition will be a few sentences outlining the choice of constants and will not change any logical steps. revision: yes

Circularity Check

0 steps flagged

No significant circularity; bound derived from external cited techniques

full rationale

The derivation combines external embedding lemmas for paths in sublinear expanders and almost-regular decompositions (cited from prior works such as Norin et al. 2025) applied to vertex-transitive graphs, which are exactly regular so the decomposition applies directly. The n^{2/3-o(1)} bound and o(1) loss are explicitly tied to quantitative parameters of those independent results rather than any self-definitional fit, self-citation chain, or renamed ansatz within this paper. No load-bearing step reduces to the paper's own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof rests on standard graph-theoretic axioms and recent results on sublinear expanders cited in the abstract; no free parameters or invented entities are introduced in the abstract statement.

axioms (1)
  • standard math Standard definitions and basic properties of vertex-transitive graphs and expanders from prior literature
    Invoked implicitly when applying embedding techniques and decompositions to vertex-transitive graphs.

pith-pipeline@v0.9.1-grok · 5765 in / 1173 out tokens · 20666 ms · 2026-06-27T15:54:45.920524+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 2 linked inside Pith

  1. [1]

    B. Alspach. The search for long paths and cycles in vertex-transitive graphs and digraphs. InCombina- torial mathematics, VIII (Geelong, 1980), volume 884 ofLecture Notes in Math., pages 14–22. Springer, Berlin, 1981

    1980

  2. [2]

    L. Babai. Long cycles in vertex-transitive graphs.J. Graph Theory, 3(3):301–304, 1979

    1979

  3. [3]

    Bedert, N

    B. Bedert, N. Dragani´ c, A. M¨ uyesser, and M. Pavez-Sign´ e. The Lov´ asz conjecture holds for moderately dense Cayley graphs.preprint arXiv:2603.08675, 2026. 17

    Pith/arXiv arXiv 2026

  4. [4]

    J. A. Bondy. Basic graph theory: paths and circuits. InHandbook of Combinatorics. Elsevier, 1995

    1995

  5. [5]

    J. A. Bondy and S. C. Locke. Relative lengths of paths and cycles in 3-connected graphs.Discrete Math., 33(2):111–122, 1981

    1981

  6. [6]

    Bradaˇ c and O

    D. Bradaˇ c and O. Janzer. Hamiltonicity of regular sublinear expanders.preprint arXiv:2605.15043, 2026

    Pith/arXiv arXiv 2026

  7. [7]

    Buci´ c, K

    M. Buci´ c, K. Hendrey, B. Mohar, R. Steiner, and L. Yepremyan. Long cycles in vertex transitive digraphs.preprint arXiv:2602.16333, 2026

    arXiv 2026

  8. [8]

    G. Chen, R. J. Faudree, and R. J. Gould. Intersections of longest cycles ink-connected graphs.J. Combin. Theory Ser. B, 72(1):143–149, 1998

    1998

  9. [9]

    M. DeVos. Longer cycles in vertex transitive graphs.preprint arXiv:2302.04255, 2023

    arXiv 2023

  10. [10]

    Dragani´ c, R

    N. Dragani´ c, R. Montgomery, D. M. Correia, A. Pokrovskiy, and B. Sudakov. Hamiltonicity of ex- panders: optimal bounds and applications.preprint arXiv:2402.06603, 2024

    arXiv 2024

  11. [11]

    T. Gallai. Problem 4. In P. Erd˝ os and G. Katona, editors,Proceedings of the Colloquium Held at Tihany, Hungary, September 1966, page 362, New York, 1968. Academic Press

    1966

  12. [12]

    Groenland, S

    C. Groenland, S. Longbrake, R. Steiner, J. Turcotte, and L. Yepremyan. Longest cycles in vertex- transitive and highly connected graphs.Bull. Lond. Math. Soc., 57(10):2975–2990, 2025

    2025

  13. [13]

    Gr¨ otschel

    M. Gr¨ otschel. On intersections of longest cycles. In B. Bollob´ as, editor,Graph theory and combinatorics: proceedings of the Cambridge Combinatorial Conference in honour of Paul Erd¨ os, pages 171 – 189, 1984

    1984

  14. [14]

    R. M. Karp. Reducibility among combinatorial problems. InComplexity of computer computations, The IBM Research Symposia, pages 85–103. 1972

    1972

  15. [15]

    H. A. Kierstead and E. R. Ren. Improved upper bounds on longest-path and maximal-subdivision transversals.Discrete Math., 346(9):Paper No. 113514, 5, 2023

    2023

  16. [16]

    Kutnar and D

    K. Kutnar and D. Maruˇ siˇ c. Hamilton cycles and paths in vertex-transitive graphs—current directions. Discrete Math., 309(17):5491–5500, 2009

    2009

  17. [17]

    Letzter, A

    S. Letzter, A. Methuku, and B. Sudakov. Nearly Hamilton cycles in sublinear expanders and applica- tions.J. Lond. Math. Soc. (2), 113(2):Paper No. e70452, 42, 2026

    2026

  18. [18]

    J. A. Long, Jr., K. G. Milans, and A. Munaro. Sublinear longest path transversals.SIAM J. Discrete Math., 35(3):1673–1677, 2021

    2021

  19. [19]

    Lov´ asz

    L. Lov´ asz. Problem 11. InCombinatorial Structures and Their Applications, Proc. Calgary Internat. Conf. on Combinatorial structures and their applications, 1969, page 497. Gordon and Breach, 1970

    1969

  20. [20]

    Ma and Z

    J. Ma and Z. Zhao. Intersections of longest cycles in vertex-transitive and highly connected graphs. preprint arXiv:2508.17438, 2025

    arXiv 2025

  21. [21]

    Merino, T

    A. Merino, T. M¨ utze, and Namrata. Kneser graphs are Hamiltonian.Adv. Math., 468:Paper No. 110189, 80, 2025

    2025

  22. [22]

    Norin, R

    S. Norin, R. Steiner, S. Thomass´ e, and P. Wollan. Small hitting sets for longest paths and cycles.Proc. Amer. Math. Soc., 154(6):2319–2335, 2026

    2026

  23. [23]

    R. A. Rankin. A campanological problem in group theory.Proc. Cambridge Philos. Soc., 44:17–25, 1948. 18

    1948

  24. [24]

    Rapaport-Strasser

    E. Rapaport-Strasser. Cayley color groups and Hamilton lines.Scripta Math., 24:51–58, 1959

    1959

  25. [25]

    Rautenbach and J.-S

    D. Rautenbach and J.-S. Sereni. Transversals of longest paths and cycles.SIAM J. Discrete Math., 28(1):335–341, 2014

    2014

  26. [26]

    H. Walther. ¨Uber die Nichtexistenz eines Knotenpunktes, durch den alle l¨ angsten Wege eines Graphen gehen.J. Combinatorial Theory, 6:1–6, 1969

    1969

  27. [27]

    Walther.Anwendungen der Graphentheorie

    H. Walther.Anwendungen der Graphentheorie. VEB Deutscher Verlag der Wissenschaften, Berlin, 1979

    1979

  28. [28]

    M. E. Watkins. Connectivity of transitive graphs.J. Combinatorial Theory, 8:23–29, 1970

    1970

  29. [29]

    Witte and J

    D. Witte and J. A. Gallian. A survey: Hamiltonian cycles in Cayley graphs.Discrete Math., 51(3):293– 304, 1984

    1984

  30. [30]

    Zamfirescu

    T. Zamfirescu. On longest paths and circuits in graphs.Math. Scand., 38(2):211–239, 1976. A Proof of Theorem 1.2, assuming Theorem 1.3 As announced in the introduction, in this section, we give the proof of Theorem 1.2 assuming Theorem 1.3. As mentioned, the proof of this implication is fully analogous to the proofs of Norin et al. [22] and hence is inclu...

    1976