pith. sign in

arxiv: 2606.07471 · v1 · pith:GWQSO6NTnew · submitted 2026-06-05 · 🧮 math.CO

Dirac subgraphs of powers of cycles are Hamiltonian

Richard Lang , Alp M\"uyesser , Mathias Schacht , Carl Schildkraut This is my paper

Pith reviewed 2026-06-27 21:35 UTC · model grok-4.3

classification 🧮 math.CO
keywords Hamiltonian cyclescycle powersminimum degree conditionsDirac-type theoremsspanning subgraphsconjecturesgraph theory
0
0 comments X

The pith

Spanning subgraphs of cycle powers with min degree (1+ε)k contain a Hamilton cycle for large k

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

The paper proves that for every ε>0 and all sufficiently large k, any spanning subgraph of the kth power of a cycle with minimum degree at least (1+ε)k contains a Hamilton cycle. A Hamilton cycle is a closed path visiting every vertex exactly once. This gives an asymptotic resolution to a conjecture on the minimum degree needed to force Hamiltonicity in these subgraphs. The result shows the degree bound works without extra assumptions once k exceeds a threshold depending on ε.

Core claim

We show that, for every ε>0 and all sufficiently large k, any spanning subgraph of the kth power of a cycle with minimum degree at least (1+ε)k contains a Hamilton cycle. This asymptotically settles a conjecture of Espuny Díaz, Lichev, and Wesolek.

What carries the argument

The minimum degree condition δ(G) ≥ (1+ε)k applied to any spanning subgraph G of the kth power of a cycle C_n^k

If this is right

  • The conjecture holds asymptotically as k grows large.
  • The degree condition alone suffices for Hamiltonicity in this family without further structural assumptions for large k.
  • This yields a Dirac-type theorem specific to spanning subgraphs of cycle powers.

Where Pith is reading between the lines

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

  • The exact conjecture may hold for all k above some finite bound rather than only asymptotically.
  • Analogous minimum-degree thresholds could apply to powers of other base graphs such as paths or trees.
  • The result may connect to algorithmic questions about detecting Hamilton cycles in circulant graphs under degree constraints.

Load-bearing premise

The minimum degree bound of (1+ε)k by itself forces a Hamilton cycle in any such spanning subgraph once k is large enough.

What would settle it

A counterexample for some large k and ε>0: a spanning subgraph of C_n^k with minimum degree at least (1+ε)k that has no Hamilton cycle.

Figures

Figures reproduced from arXiv: 2606.07471 by Alp M\"uyesser, Carl Schildkraut, Mathias Schacht, Richard Lang.

Figure 1
Figure 1. Figure 1: Stitching nearly-spanning matchings into a spanning linear forest with few paths. Lemma 2.8 (Path connection). Let S be an ε-distributed set. Let T be an ε 1 -locally sparse multiset, disjoint from S, of some even size 2t. Suppose that T can be enumerated as v1, w1, . . . , vt , wt in such a way that the clockwise intervals Ii :“ rvi , wis in total cover each point of Cn at most M times. Suppose that M ă α… view at source ↗
Figure 2
Figure 2. Figure 2: A chain of beehive absorbers of height ℓ “ 2. Within each beehive, a path from the x-vertex (on the bottom left) to the y-vertex (on the top right) is drawn. The vertices of the leftmost beehive are labeled in accordance with Definition 5.1. Lemma 5.2 (Beehives are absorbers). Every ps, x, yq-beehive is an px, y; tsuq-absorber. Proof. Let O be an ps, x, yq-beehive; we must show that both O and OrV pOq ∖ ts… view at source ↗
Figure 3
Figure 3. Figure 3: The set X is shaded in light gray and the set T∖X is shaded in dark gray. A circle of radius r “ 0.7 is centered at the point x “ p0.45, 0.1q P T ∖X. Lemma A.2. Set a “ 0.37 and r “ 0.7. Let Λ be the triangular lattice Zp1, 0q`Zp1{2, ? 3{2q, and let X “ ğ vPΛ Bpv, aq be a union of circles of radius a. For any x R X, the area of the intersection X X Bpx, rq is at least 0.501pπr2 q. Proof. Let f : R2 Ñ r0, 1… view at source ↗
Figure 4
Figure 4. Figure 4: The circles centered at points s P S of radii πr 2 pfpsq´0.501q, which cover T ∖ X, and the corresponding values of fpsq, rounded to four decimal places. in [PITH_FULL_IMAGE:figures/full_fig_p031_4.png] view at source ↗
read the original abstract

We show that, for every $\varepsilon>0$ and all sufficiently large $k$, any spanning subgraph of the $k$th power of a cycle with minimum degree at least $(1+\varepsilon)k$ contains a Hamilton cycle. This asymptotically settles a conjecture of Espuny D\'iaz, Lichev, and Wesolek.

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

0 major / 0 minor

Summary. The manuscript proves that for every ε > 0 and all sufficiently large k, any spanning subgraph of the kth power of a cycle C_n with minimum degree at least (1 + ε)k contains a Hamilton cycle. This asymptotically settles a conjecture of Espuny Díaz, Lichev, and Wesolek.

Significance. If correct, the result is a meaningful contribution to Dirac-type theorems for graph powers. It confirms that a linear degree condition with coefficient strictly above 1 suffices asymptotically in this structured setting, providing a natural relaxation of the full conjecture without requiring additional structural assumptions beyond the degree bound.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive report and recommendation to accept the manuscript. The referee's summary accurately captures the main result.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper states a new asymptotic theorem settling an external conjecture of Espuny Díaz, Lichev, and Wesolek. No equations, self-citations, or steps reduce the central Hamiltonicity claim to a fit, self-definition, or prior author result by construction. The min-degree condition is an independent hypothesis applied to the cycle-power host graph; the proof is framed as a standard extremal argument without renaming known patterns or smuggling ansatzes via self-citation. This is the expected honest non-finding for a self-contained existence theorem.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review is based solely on the abstract; no specific free parameters, ad hoc axioms, or invented entities are identifiable from the provided text. The result rests on standard definitions of graph powers, spanning subgraphs, minimum degree, and Hamilton cycles.

axioms (1)
  • standard math Standard axioms and definitions of graph theory including cycles, graph powers, spanning subgraphs, and Hamilton cycles
    The theorem statement invokes these foundational concepts without introducing new ones.

pith-pipeline@v0.9.1-grok · 5572 in / 1089 out tokens · 27727 ms · 2026-06-27T21:35:08.539945+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

18 extracted references · 2 linked inside Pith

  1. [1]

    Alon and J

    N. Alon and J. Spencer.The probabilistic method. John Wiley & Sons, 2016

    2016

  2. [2]

    Alon and R

    N. Alon and R. Yuster. On a hypergraph matching problem.Graphs and Combinatorics, 21(4):377–384, 2005

    2005

  3. [3]

    Antoniuk and Chr

    S. Antoniuk and Chr. Reiher. Sets and partitions minimising small differences.arxiv:2410.23868, 2024

    arXiv 2024

  4. [4]

    Bedert, N

    B. Bedert, N. Draganić, A. Müyesser, and M. Pavez-Signé. The Lovász conjecture holds for moderately dense Cayley graphs.arXiv:2603.08675, 2026

    Pith/arXiv arXiv 2026

  5. [5]

    Christoph, N

    M. Christoph, N. Draganić, A. Girão, E. Hurley, L. Michel, and A. Müyesser. New bounds for linear arboricity and related problems.arXiv:2507.20500, 2025

    arXiv 2025

  6. [6]

    Draganić, J

    N. Draganić, J. Kim, H. Lee, D. M. Correia, M. Pavez-Signé, and B. Sudakov. Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions.arXiv:2507.22807, 2025

    arXiv 2025

  7. [7]

    Ehard, S

    S. Ehard, S. Glock, and F. Joos. Pseudorandom hypergraph matchings.Combinatorics, Probability and Computing, 29(6):868–885, 2020

    2020

  8. [8]

    Espuny Díaz, P

    A. Espuny Díaz, P. Gupta, D. M. Cecchelli, O. Parczyk, and A. Sgueglia. Dirac’s theorem for graphs of bounded bandwidth.Electronic Journal of Combinatorics, 33(1):P1.21, 2026

    2026

  9. [9]

    Espuny Díaz, L

    A. Espuny Díaz, L. Lichev, and A. Wesolek. On the local resilience of random geometric graphs with respect to connectivity and long cycles.arXiv:2406.09921, 2024

    arXiv 2024

  10. [10]

    A. Frieze. Hamilton cycles in random graphs: a bibliography.arXiv:1901.07139, 2019

    arXiv 1901

  11. [11]

    Hajnal and E

    A. Hajnal and E. Szemerédi. Proof of a conjecture of P. Erdős. InCombinatorial theory and its applica- tions, II (Proc. Colloq., Balatonfüred, 1969), pages 601–623, 1970

    1969

  12. [12]

    Komlós, G

    J. Komlós, G. N. Sárközy, and E. Szemerédi. Proof of the Seymour conjecture for large graphs.Annals of Combinatorics, 2(1):43–60, 1998

    1998

  13. [13]

    R. Lang. Tiling dense hypergraphs.arXiv:2308.12281, 2023

    Pith/arXiv arXiv 2023

  14. [14]

    Lang and N

    R. Lang and N. Sanhueza-Matamala. A hypergraph bandwidth theorem.arXiv:2412.14891, 2024

    arXiv 2024

  15. [15]

    Lee and B

    C. Lee and B. Sudakov. Dirac’s theorem for random graphs.Random Structures & Algorithms, 41(3):293– 305, 2012

    2012

  16. [16]

    Montgomery, A

    R. Montgomery, A. Müyesser, A. Pokrovskiy, and B. Sudakov. Approximate path decompositions of regular graphs.Journal of the London Mathematical Society, 112(2):e70269, 2025. DIRAC SUBGRAPHS OF POWERS OF CYCLES ARE HAMILTONIAN 29

    2025

  17. [17]

    Moon and L

    J. Moon and L. Moser. On Hamiltonian bipartite graphs.Israel Journal of Mathematics, 1(3):163–165, 1963

    1963

  18. [18]

    proof by picture:

    B. Sudakov and V. H. Vu. Local resilience of graphs.Random Structures & Algorithms, 33(4):409–433, 2008. AppendixA.A counterexample to Conjecture 1.3 whend“2 We begin with the following geometric result. Proposition A.1.For small enoughrą0, there exists a measurable subsetXof the unit toruspR{Zq 2 satisfying the following two properties: (1)µpXq ă0.499. (...

    2008