Pith. sign in

REVIEW 8 cited by

Hamiltonicity of expanders: optimal bounds and applications

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2402.06603 v2 pith:463G6I5D submitted 2024-02-09 math.CO

Nemanja Draganić , Richard Montgomery , David Munhá Correia , Alexey Pokrovskiy , Benny Sudakov This is my paper
classification math.CO
keywords everygraphshamiltonicityapplicationsexpanderthereboundscayley
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

An $n$-vertex graph $G$ is a $C$-expander if $|N(X)|\geq C|X|$ for every $X\subseteq V(G)$ with $|X|< n/2C$ and there is an edge between every two disjoint sets of at least $n/2C$ vertices. We show that there is some constant $C>0$ for which every $C$-expander is Hamiltonian. In particular, this implies the well known conjecture of Krivelevich and Sudakov from 2003 on Hamilton cycles in $(n,d,\lambda)$-graphs. This completes a long line of research on the Hamiltonicity of sparse graphs, and has many applications, including to the Hamiltonicity of random Cayley graphs.

Discussion (0). Sign in to comment.

Forward citations

Cited by 8 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A proof of Andersen's rainbow path conjecture for large $n$

    math.CO 2026-08 conditional novelty 8.0 of 10

    For all sufficiently large n, every properly edge-coloured n-vertex complete graph has a rainbow path on n-1 vertices, resolving Andersen's conjecture and its Latin-square analogue for large n.

  2. Universality in random graphs via optimal linking systems: trees and beyond

    math.CO 2026-08 conditional novelty 8.0 of 10

    An absolute constant C suffices for bounded-degree tree universality in G(n, C ln n/n), and cycle-factor universality is optimal up to constants via depth-optimal linking systems.

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

    math.CO 2026-06 unverdicted novelty 8.0 of 10

    Every connected vertex-transitive graph of order n contains a cycle of length at least n^(2/3-o(1)), up from the previous n^(9/14).

  4. Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions

    math.CO 2025-07 conditional novelty 8.0 of 10

    For pseudorandom graphs with large spectral gap, every subgraph with minimum degree above d/2 is Hamiltonian, and the whole edge set can be packed into, and covered by, about d/2 Hamilton cycles.

  5. Efficient Hamilton covers and linear arboricity of random graphs

    math.CO 2026-07 conditional novelty 7.0 of 10

    Random graphs with any edge probability have Hamilton covers of the smallest possible size, once Hamilton cycles exist.

  6. The Hamilton cycle space of random regular graphs and randomly perturbed graphs

    math.CO 2025-07 conditional novelty 7.0 of 10

    Hamilton cycles span the full cycle space asymptotically almost surely in random regular graphs of sufficiently large constant degree, and in randomly perturbed dense graphs.

  7. Hamilton cycles in regular graphs perturbed by a random 2-factor

    math.CO 2025-06 conditional novelty 7.0 of 10

    For every integer d ≥ 2, the union of any d-regular graph on n vertices with a uniformly random 2-factor is Hamiltonian with high probability.

  8. Recent progress in graph theory using expansion

    math.CO 2026-07 accept novelty 3.0 of 10

    Sublinear expansion—weak neighbourhood growth in sparse graphs—has resolved many long-standing extremal graph theory conjectures, and this survey organizes that progress.

Pith tools