Tight Staircase Bounds for Cyclic Subsets below Dirac's Threshold

Hong Liu; Lanchao Wang; Mengyuan Niu; Zhifei Yan

Staircase Discovered for Hamiltonian Subsets Below Dirac's Threshold

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · glm-5.2

2026-07-08 01:56 UTC pith:VHPUZX44

load-bearing objection Solid paper. Sharp staircase bound for cyclic subsets below Dirac, with a clean trichotomy and correct proofs. Recommend serious referee.

arxiv 2607.06551 v1 pith:VHPUZX44 submitted 2026-07-07 math.CO

Tight Staircase Bounds for Cyclic Subsets below Dirac's Threshold

Hong Liu , Mengyuan Niu , Lanchao Wang , Zhifei Yan This is my paper

classification math.CO

keywords diracgraphsubsetscyclicoperatornameregularbelowbound

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper determines the exact asymptotic minimum number of cyclic subsets (vertex subsets that induce a Hamiltonian subgraph) in regular graphs with linear degree below the Dirac threshold. The central discovery is that the optimal exponential rate of this count does not vary smoothly with the graph's degree, but instead follows a discrete staircase governed by the integer $q = ⌊n/(d+1)⌋$. For an $n$-vertex $d$-regular graph with $d < n/2$, the number of cyclic subsets is at least $(q-o(1))2^{n/q}$. The proof proceeds by applying Szemerédi's Regularity Lemma to obtain a reduced graph and proving a structural trichotomy: either a large connected matching exists, the graph splits into $q$ balanced dense components, or it splits into $q+1$ near-critical components where regularity forces compensating edges. The bound is asymptotically tight, including the leading coefficient $q$, as witnessed by the disjoint union of $q$ equal cliques.

Core claim

The paper identifies a 'staircase' mechanism for the count of Hamiltonian-induced vertex subsets in $d$-regular graphs below the Dirac threshold. The minimum count is exactly $(q-o(1))2^{n/q}$ where $q=⌊n/(d+1)⌋$. The integer $q$ acts as a discrete parameter that controls the exponential rate, remaining constant across intervals of $d$ and jumping when $d$ crosses $n/k$ thresholds. The extremal configuration is the disjoint union of $q$ equal cliques. The proof establishes a reduced-graph trichotomy (connected matching, $q$ balanced components, or $q+1$ near-critical components) to show no other graph structure can produce fewer cyclic subsets.

What carries the argument

Reduced-graph trichotomy (Lemma 3.1) sorting graphs into three cases: (a) large connected matching, (b) $q$ balanced dense components, (c) $q+1$ near-critical components with forced cross-block matchings.

Load-bearing premise

The most delicate part of the argument is in the case of $q+1$ near-critical components, where the proof relies on a global edge-counting inequality to force a large matching between two blocks. If this edge-counting fails to guarantee a sufficiently large cross-block matching, the exponential surplus over the target bound in this case would not be secured.

What would settle it

A $d$-regular graph on $n$ vertices with $d=Ω(n)$ and $d<n/2$ where the number of cyclic subsets is asymptotically smaller than $(q-o(1))2^{n/q}$, or where the exponential rate varies smoothly with $d$ rather than jumping at $n/k$ thresholds.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

The staircase phenomenon depends on the global regularity assumption; under minimum-degree conditions alone, the extremal obstruction is not governed by $q$ equal pieces, suggesting a fundamentally different landscape for non-regular settings.
The exact boundary at $d=n/2$ reaches the maximum exponential rate $2^{(1-o(1))n}$, confirming that the transition to full-scale Hamiltonian subset density occurs precisely at the Dirac threshold.
The trichotomy proof technique—distinguishing genuinely extremal $q$-block configurations from near-critical $(q+1)$-block cases via forced matchings—may generalize to other enumerative problems in extremal graph theory where regularity constrains component structure.
Size-sensitive estimates counting cyclic subsets of each fixed cardinality could reveal finer distributional structure within the staircase levels.

Where Pith is reading between the lines

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

The discrete staircase implies that small changes in degree $d$ that do not cross an $n/k$ threshold have no effect on the asymptotic minimum of cyclic subsets—a form of phase rigidity in the enumerative behavior.
The sharpness of the leading coefficient $q$ at clique-union examples suggests these configurations are rigid minimizers, and the $o(1)$ gap might be closeable to an exact theorem for specific parameter families.
The forced cross-block matching in the $(q+1)$-component case reveals that global regularity creates hidden connectivity that produces an exponential surplus over the naive $q$-block bound, indicating the staircase is a robust structural phenomenon rather than an artifact of the proof method.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Solid paper. Sharp staircase bound for cyclic subsets below Dirac, with a clean trichotomy and correct proofs. Recommend serious referee.

read the letter

This paper determines the sharp asymptotic lower bound for cyclic subsets in regular graphs throughout the below-Dirac range, and the answer is clean: Cyc(G) ≥ (q−o(1))2^{n/q} where q = floor(n/(d+1)), tight at the clique-union examples. The staircase phenomenon — exponential rate jumping discretely at thresholds d = n/k — is the genuine new contribution here, as is the sharp leading coefficient q. The boundary result (Proposition 1.2, giving 2^{(1−o(1))n} at d = n/2) is a nice bonus, though it follows the same machinery and is less surprising once the main theorem is in place. The trichotomy (Lemma 3.1) is the structural heart. It is derived cleanly from Dirac's longest-path lemma and the minimum-degree condition δ(R) ≥ (1/(q+1) − o(1))|R| inherited from regularity. The three cases are handled with the right tools: Blow-up Lemma for connected matchings, Chvátal's theorem for the balanced case, and a forced-matching argument for the near-critical case. The proof organization is good — each section is self-contained and the constant hierarchies are consistent. On the soft spots: the reader flagged the edge-counting in Lemma 6.2 / Claim 6.4 as the most delicate part. I checked it carefully and it holds up. The identity e(B_i, V∖A_i) = |B_i|Δ_i + h_i is correct, the summation inequality Σ e(B_i, V∖A_i) ≤ Σ e(C_i, V∖A_i) is justified by the observation that cross-block edges from B_i land in C_j sets (since B_i–B_j edges don't exist), and the final contradiction (LHS > n/k, RHS < n/k) follows from the constant choices. The convexity argument in Case (b) is straightforward and loses nothing. One minor point: the paper could be more explicit about how the exceptional set V_0 is distributed in Case (b) and why the resulting blocks satisfy the hypotheses of Proposition 5.1 with the stated parameters — the argument is there but compressed. This is a presentation issue, not a mathematical one. This is for researchers in extremal graph theory working on enumerative aspects of Hamiltonicity. It deserves a serious referee. The result is new, the proof is correct, and the staircase phenomenon is worth recording.

Referee Report

0 major / 7 minor

Summary. This paper determines the sharp asymptotic lower bound on the number of cyclic subsets (subsets inducing a Hamiltonian subgraph) in regular graphs below the Dirac threshold. The main result (Theorem 1.1) states that for an n-vertex d-regular graph with εn ≤ d < n/2 and q = ⌊n/(d+1)⌋ ≥ 2, one has Cyc(G) ≥ (q − o(1))·2^{n/q}. This bound is tight, including the leading coefficient q, as witnessed by the disjoint union of q equal cliques. A boundary result (Proposition 1.2) gives the optimal exponential rate 2^{(1−o(1))n} at d = n/2. The proof proceeds via a trichotomy for the reduced graph obtained from Szemerédi's Regularity Lemma (Lemma 3.1), followed by three separate counting arguments for each case: large connected matchings (Section 4), q balanced dense components (Section 5), and q+1 near-critical components (Section 6).

Significance. The paper resolves a natural and well-motivated problem in the enumerative theory of Hamiltonicity, extending the recent work of Draganic, Keevash, and Muyesser from the Dirac regime to the entire linear below-Dirac range. The staircase phenomenon — discrete jumps in the optimal exponential rate — is a clean conceptual contribution. The proof is self-contained against external benchmarks: the lower bound is derived from standard tools (Regularity Lemma, Dirac's theorem, Chvatal's theorem, Blow-up Lemma, Chernoff bounds), and the upper bound is witnessed by the explicit construction qK_{n/q}. The sharpness of the leading coefficient q in Case (b), requiring careful handling of exceptional vertices, is a notable technical strength. The edge-counting argument in Lemma 6.2 / Claim 6.4 is intricate and verifies correctly upon careful checking.

minor comments (7)

Section 1, footnote 1: the term 'cyclic subset' is defined as a subset inducing a Hamiltonian subgraph, but the footnote extends this to include the empty set, singletons, and copies of K_2. This convention should be stated more prominently (e.g., in the definition of Cyc(G) itself) since it affects the counting in Proposition 5.1, where the empty set is explicitly excluded from the disjointness argument.
Lemma 4.5, proof: the claim states that (A,B) is (6ρ, μ/4)-super-regular with probability 1−o(1), but the minimum-degree verification shows every vertex of A has at least μ|B|/4 neighbours in B. The parameter in the super-regularity conclusion should be stated consistently (μ/4 vs μr/4 where r = |B|).
Proposition 6.1: the constant C in the statement is used both as a given positive constant and as the bound C·2^{n/(k−1)} for k ≥ 3. In the proof, C is set to q−ξ, but the hierarchy 1/n ≪ θ, ρ, λ ≪ 1/k, 1/C requires C to be fixed. This is fine since q and ξ are fixed, but a brief remark clarifying that C is a fixed constant (not depending on n) would improve readability.
Figure 1: the axis label 'n/log_2 Cyc(G)' is slightly ambiguous — it would be clearer to write 'n / log_2(Cyc(G))' or specify that this is the asymptotic exponential rate.
Section 9: the open problem about exact minimizers at clique points is natural. A reference to the exact results of Kim, Liu, Sharifzadeh, and Staden [9] for the minimum-degree setting would provide useful context for what 'exact' means here.
Proof of Proposition 7.1, Case (b): the bound d_G(z, A_i) ≥ (1/(q(q+1)) − ρ/q − o(1))n is shown to be at least 5α|A_i|. The verification relies on α being sufficiently small relative to 1/q, but the chain of inequalities is compressed; spelling out the final comparison (i.e., that 1/(q(q+1))n ≥ 5α·(1/q + 3qτ)n for the chosen hierarchy) would aid the reader.
Lemma 6.2: the assumption c ≤ k^{−9} is stronger than what the final contradiction requires (the bound k(k+1)^2 C^2 < n/k uses C < C(k,2)·c√n, so c ≤ k^{−9} is more than sufficient). A brief remark that this is not tight would prevent confusion.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for a careful reading and for the positive assessment. The report recommends minor revision but does not list any specific major or minor comments requiring changes. We address the report below.

Circularity Check

0 steps flagged

No circularity: the lower bound is a first-principles theorem and the upper bound is witnessed by an explicit external construction.

full rationale

The paper proves Theorem 1.1 (a lower bound on Cyc(G)) via a trichotomy on the reduced graph (Lemma 3.1), with each case handled by a self-contained proposition (4.1, 5.1, 6.1) using standard tools (Szemerédi's Regularity Lemma, Dirac's theorem, Chvátal's theorem, the Blow-up Lemma). No proposition's conclusion reduces by construction to its hypotheses. The tightness (upper bound) is witnessed by the explicit construction qK_{n/q}, an independent external benchmark. No fitted parameters are renamed as predictions, no self-citation chain is load-bearing for the central claim, and no ansatz is smuggled in. The derivation is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 0 invented entities

The paper is a pure mathematics proof. It introduces no new physical entities, particles, or forces. It introduces no free parameters fitted to data. The 'q' in the main theorem is not a free parameter but is uniquely determined by n and d (q = floor(n/(d+1))). All background results are standard mathematical theorems.

axioms (6)

standard math Szemerédi's Regularity Lemma (Degree form)
Invoked in Lemma 7.2 to partition the graph into regular pairs and obtain the reduced graph R.
standard math Dirac's theorem on longest paths
Invoked in Lemma 3.2 to guarantee long paths in connected components of the reduced graph, enabling the trichotomy.
standard math Chvátal's Hamiltonicity theorem
Invoked as Theorem 5.3 to guarantee Hamilton cycles in random subsets of dense blocks (Lemma 5.2).
standard math Blow-up Lemma by Komlós, Sárközy and Szemerédi
Invoked as Lemma 4.4 to embed Hamiltonian paths in super-regular pairs (Proposition 4.1).
standard math Chernoff bound for hypergeometric random variables
Used in Lemma 4.5 and Claim 5.4 to show that random subsets of regular pairs inherit super-regularity and degree conditions with high probability.
standard math Kőnig's theorem
Used in Lemma 6.2 to relate the maximum matching size between blocks to the minimum vertex cover.

pith-pipeline@v1.1.0-glm · 20456 in / 2492 out tokens · 219457 ms · 2026-07-08T01:56:41.449212+00:00 · methodology

0 comments

read the original abstract

Let $\operatorname{Cyc}(G)$ denote the number of cyclic subsets in a graph $G$, which are subsets that induce a Hamiltonian subgraph. Dragani\'{c}, Keevash and M\"{u}yesser recently proved that every regular Dirac graph has $\Omega(2^n)$ cyclic subsets, resolving a problem of Erd\H{o}s and Faudree. We determine the sharp asymptotic lower bound throughout the linear range below Dirac's threshold. Let $G$ be an $n$-vertex $d$-regular graph with $d=\Omega(n)$ and $d<n/2$, then $$ \operatorname{Cyc}(G)\ge (q-o(1))2^{n/q}, \quad \text{where } \quad q=\left\lfloor \frac{n}{d+1}\right\rfloor \ge 2. $$ This bound is asymptotically best possible, including the leading coefficient $q$, as witnessed at the staircase levels by the disjoint union of $q$ equal cliques. Consequently, the optimal exponential rate changes by discrete jumps as $d$ crosses the thresholds $n/k$, rather than varying smoothly with $d$. We also prove the optimal exponential rate at the Dirac boundary: every $n$-vertex $n/2$-regular graph satisfies $\operatorname{Cyc}(G)\ge 2^{(1-o(1))n},$ which is sharp up to a subexponential factor by $K_{n/2,n/2}$.

Figures

Figures reproduced from arXiv: 2607.06551 by Hong Liu, Lanchao Wang, Mengyuan Niu, Zhifei Yan.

**Figure 1.** Figure 1: The staircase behaviour of the exponential lower bound. As the regular degree d drops below the thresholds n/k (moving from right to left), the value of n/log2 Cyc(G) jumps discretely to the next integer. are q balanced dense components, where one must count almost all subsets inside each component and preserve the sharp leading coefficient q; or there are q + 1 near-critical components, where the regulari… view at source ↗

discussion (0)

Forward citations

Cited by 1 Pith paper

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

On the number of factorable induced subgraphs
math.CO 2026-07 accept novelty 8.0

Random induced subgraphs of dense graphs contain F-factors with asymptotically tight probability 1/(rq), where q is the order of a lattice coset group.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages · cited by 1 Pith paper

[1]

V. Chvátal. On Hamilton’s ideals.J. Combinatorial Theory Ser. B, 12:163–168, 1972

work page 1972
[2]

Csaba, D

B. Csaba, D. Kühn, A. Lo, D. Osthus, and A. Treglown. Proof of the 1-factorization and Hamilton decomposition conjectures.Memoirs of the American Mathematical Society, 244(1154):1–164, 2016

work page 2016
[3]

Cuckler and J

W. Cuckler and J. Kahn. Hamiltonian cycles in dirac graphs.Combinatorica, 29(3):299–326, 2009

work page 2009
[4]

G. A. Dirac. Some theorems on abstract graphs.Proceedings of the London Mathematical Society, 2:69–81, 1952

work page 1952
[5]

Draganić, P

N. Draganić, P. Keevash, and A. Müyesser. Cyclic subsets in regular Dirac graphs.International Mathematics Research Notices, 2025(14):rnaf215, 2025

work page 2025
[6]

Springer, Berlin, 1997

P.Erdős.Someofmyfavoriteproblemsandresults.InThe mathematics of Paul Erdős, I,volume13ofAlgorithms Combin., pages 47–67. Springer, Berlin, 1997

work page 1997
[7]

Frieze and M

A. Frieze and M. Krivelevich. On two Hamilton cycle problems in random graphs.Israel Journal of Mathematics, 166:221–234, 2008

work page 2008
[8]

Hunter, T

Z. Hunter, T. Liu, A. Milojević, and B. Sudakov. Cyclic subsets of tournaments.Random Structures&Algo- rithms, 2026

work page 2026
[9]

J. Kim, H. Liu, M. Sharifzadeh, and K. Staden. Proof of Komlós’s conjecture on Hamiltonian subsets.Proceedings of the London Mathematical Society, 115(5):974–1013, 2017

work page 2017
[10]

Komlós, G

J. Komlós, G. N. Sárközy, and E. Szemerédi. Blow-up lemma.Combinatorica, 17:109–123, 1997

work page 1997
[11]

Komlós and M

J. Komlós and M. Simonovits. Szemerédi’s regularity lemma and its applications in graph theory. InCombi- natorics, Paul Erdős is Eighty, Vol. 2, volume 2 ofBolyai Society Mathematical Studies, pages 295–352. János Bolyai Mathematical Society, Budapest, 1996

work page 1996
[12]

Krivelevich, C

M. Krivelevich, C. Lee, and B. Sudakov. Robust Hamiltonicity of Dirac graphs.Transactions of the American Mathematical Society, 366(6):3095–3130, 2014

work page 2014
[13]

D. Kühn, D. Osthus, and A. Treglown. Hamilton decompositions of regular tournaments.Proceedings of the London Mathematical Society, 101(1):303–335, 2010

work page 2010
[14]

Montgomery

R. Montgomery. Hamiltonicity in random graphs is born resilient.Journal of Combinatorial Theory, Series B, 139:316–341, 2019

work page 2019
[15]

G. N. Sárközy, S. M. Selkow, and E. Szemerédi. On the number of Hamiltonian cycles in Dirac graphs.Discrete Mathematics, 265(1–3):237–250, 2003

work page 2003
[16]

W. Sun, S. Wei, and D. Yang. Clique factors in random samplings of regular graphs.arXiv preprint arXiv:2512.20287, 2025. ECOPRO, Institute for Basic Science, 55 Expo-ro, Yuseong-gu, Daejeon, 34126, Korea Email address:hongliu@ibs.re.kr School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, China, and ECOPRO, Institute for Basic Science, 55...

work page arXiv 2025

[1] [1]

V. Chvátal. On Hamilton’s ideals.J. Combinatorial Theory Ser. B, 12:163–168, 1972

work page 1972

[2] [2]

Csaba, D

B. Csaba, D. Kühn, A. Lo, D. Osthus, and A. Treglown. Proof of the 1-factorization and Hamilton decomposition conjectures.Memoirs of the American Mathematical Society, 244(1154):1–164, 2016

work page 2016

[3] [3]

Cuckler and J

W. Cuckler and J. Kahn. Hamiltonian cycles in dirac graphs.Combinatorica, 29(3):299–326, 2009

work page 2009

[4] [4]

G. A. Dirac. Some theorems on abstract graphs.Proceedings of the London Mathematical Society, 2:69–81, 1952

work page 1952

[5] [5]

Draganić, P

N. Draganić, P. Keevash, and A. Müyesser. Cyclic subsets in regular Dirac graphs.International Mathematics Research Notices, 2025(14):rnaf215, 2025

work page 2025

[6] [6]

Springer, Berlin, 1997

P.Erdős.Someofmyfavoriteproblemsandresults.InThe mathematics of Paul Erdős, I,volume13ofAlgorithms Combin., pages 47–67. Springer, Berlin, 1997

work page 1997

[7] [7]

Frieze and M

A. Frieze and M. Krivelevich. On two Hamilton cycle problems in random graphs.Israel Journal of Mathematics, 166:221–234, 2008

work page 2008

[8] [8]

Hunter, T

Z. Hunter, T. Liu, A. Milojević, and B. Sudakov. Cyclic subsets of tournaments.Random Structures&Algo- rithms, 2026

work page 2026

[9] [9]

J. Kim, H. Liu, M. Sharifzadeh, and K. Staden. Proof of Komlós’s conjecture on Hamiltonian subsets.Proceedings of the London Mathematical Society, 115(5):974–1013, 2017

work page 2017

[10] [10]

Komlós, G

J. Komlós, G. N. Sárközy, and E. Szemerédi. Blow-up lemma.Combinatorica, 17:109–123, 1997

work page 1997

[11] [11]

Komlós and M

J. Komlós and M. Simonovits. Szemerédi’s regularity lemma and its applications in graph theory. InCombi- natorics, Paul Erdős is Eighty, Vol. 2, volume 2 ofBolyai Society Mathematical Studies, pages 295–352. János Bolyai Mathematical Society, Budapest, 1996

work page 1996

[12] [12]

Krivelevich, C

M. Krivelevich, C. Lee, and B. Sudakov. Robust Hamiltonicity of Dirac graphs.Transactions of the American Mathematical Society, 366(6):3095–3130, 2014

work page 2014

[13] [13]

D. Kühn, D. Osthus, and A. Treglown. Hamilton decompositions of regular tournaments.Proceedings of the London Mathematical Society, 101(1):303–335, 2010

work page 2010

[14] [14]

Montgomery

R. Montgomery. Hamiltonicity in random graphs is born resilient.Journal of Combinatorial Theory, Series B, 139:316–341, 2019

work page 2019

[15] [15]

G. N. Sárközy, S. M. Selkow, and E. Szemerédi. On the number of Hamiltonian cycles in Dirac graphs.Discrete Mathematics, 265(1–3):237–250, 2003

work page 2003

[16] [16]

W. Sun, S. Wei, and D. Yang. Clique factors in random samplings of regular graphs.arXiv preprint arXiv:2512.20287, 2025. ECOPRO, Institute for Basic Science, 55 Expo-ro, Yuseong-gu, Daejeon, 34126, Korea Email address:hongliu@ibs.re.kr School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, China, and ECOPRO, Institute for Basic Science, 55...

work page arXiv 2025