{"id":"c22d0d5b-d166-4ba9-b322-c7338e653b32","arxiv_id":"2607.06551","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Every n-vertex d-regular graph with d < n/2 has at least (q-o(1))2^{n/q} cyclic subsets, where q = floor(n/(d+1)), and this bound is asymptotically tight.","lead":"This paper determines the exact minimum number of 'cyclic subsets' (subsets inducing a Hamiltonian subgraph) in regular graphs with degree below the Dirac threshold. It shows the minimum follows a discrete 'staircase' function of the degree, rather than varying smoothly, which precisely characterizes the extremal behavior.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified. The edge-counting in Lemma 6.2 (Claim 6.4) is intricate but verifies upon careful checking, and the convexity argument in Case (b) correctly handles non-exact block sizes.","rationale":"The reader correctly identified the most intricate part of the proof (Lemma 6.2 / Claim 6.4) as the weakest link, and this was the right place to look. However, upon careful verification, the edge-counting is sound: the identity for e(B_i, V(G)∖A_i), the inequality bounding missing B_i–C_i edges by h_i, the summation argument using edge-symmetry, and the final algebraic contradiction all check out. The constant c ≤ k^{-9} provides ample margin. I also verified that the convexity argument in Case (b) correctly handles the fact that block sizes are only approximately n/q (not exactly), ensuring the sharp leading coefficient q is preserved. The trichotomy is exhaustive, and all constant hierarchies in Proposition 7.1 are consistent. The proof is well-structured and appears correct. The reader's verdict of ACCEPT with HIGH confidence is appropriate; no adjustment is needed.","tokens_in":18269,"tokens_out":6423,"duration_ms":216240,"concrete_test":"Independently verify the algebraic rearrangement in Lemma 6.2 from Claim 6.4's inequality to the final contradiction. Specifically, starting from Σ(d+1-Δ_i-|C_i|)Δ_i ≤ Σ|C_i|(Δ_i+|C_i|-1), expand and rearrange to obtain (d+1)ΣΔ_i ≤ Σ(|Δ_i|+|C_i|)², then substitute the bounds |Δ_i| ≤ kC, C < C(k,2)·c√n, ΣΔ_i ≥ 1, d+1 > n/k to confirm LHS > n/k > RHS. If any coefficient in the rearrangement is off by a factor of k, the contradiction may fail for small k (especially k=3, i.e., q=2).","verdict_should_be":"UNCHANGED","load_bearing_attack":"I carefully examined the reader's flagged concern: the edge-counting in Lemma 6.2 / Claim 6.4 in Case (c). The argument proceeds by contradiction: assuming all cross-block matchings have size < c√n, König's theorem gives small vertex covers D_{ij}, leading to sets C_i (covered vertices) and B_i (uncovered vertices) with no edges between any B_i, B_j. The key identity e(B_i, V(G)∖A_i) = |B_i|Δ_i + h_i is correct, where h_i counts missing incidences from B_i into A_i. The inequality |B_i||C_i| - e(C_i, B_i) ≤ h_i holds because missing B_i–C_i edges are a subset of missing B_i–A_i edges. The summation inequality Σ e(B_i, V(G)∖A_i) ≤ Σ e(C_i, V(G)∖A_i) is justified: edges from B_i to other blocks land in ∪_{j≠i} C_j (since B_i–B_j edges don't exist), and by edge-symmetry these equal edges from C_j to B_i, which are a subset of e(C_j, V(G)∖A_j). The final contradiction (LHS > n/k, RHS < n/k) follows from |Δ_i| ≤ kC, C < C(k,2)·c√n, and c ≤ k^{-9}, which is more than sufficient. I also checked the convexity argument in Case (b): Σ 2^{|B_i|} ≥ q·2^{n/q} by convexity of 2^x with Σ|B_i| = n, so non-exact block sizes do not lose the leading coefficient. The trichotomy (Lemma 3.1) is exhaustive: s ≤ q-1 → Case (a), s = q → (a) or (b), s = q+1 → (c). All applications of Propositions 4.1, 5.1, 6.1 in Proposition 7.1 have their hypotheses verified with consistent constant hierarchies. I do not identify a load-bearing concern.","agreement_with_reader":"partial"},"referee_report":{"model":"glm-5.2","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).","tokens_in":18716,"tokens_out":1202,"duration_ms":243231,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":null},{"comment":"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|).","section":null},{"comment":"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.","section":null},{"comment":"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":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper is a strong contribution suitable for a serious combinatorics journal. The mathematical content is correct and the proof structure is clean. The minor comments are all presentation issues that do not affect the validity of the arguments. I recommend acceptance after light revision. The authors may also wish to verify that the constant hierarchies are stated consistently throughout (some are given in the notation paragraph, others inline), but this is a stylistic matter."},"author_rebuttal":{"model":"glm-5.2","summary":"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.","responses":[],"tokens_in":17754,"tokens_out":97,"duration_ms":9064,"standing_objections":[]},"desk_editor":{"model":"glm-5.2","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.","headline":"Solid paper. Sharp staircase bound for cyclic subsets below Dirac, with a clean trichotomy and correct proofs. Recommend serious referee.","tokens_in":19163,"tokens_out":1327,"would_cite":true,"duration_ms":30132,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"Staircase Discovered for Hamiltonian Subsets Below Dirac's Threshold","keywords":[],"falsifier":"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.","tokens_in":18440,"feed_emoji":"🪜","tokens_out":990,"duration_ms":161696,"temperature":0.7,"pith_summary":"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.","feed_headline":"Staircase bounds found for Hamiltonian subsets below Dirac threshold","feed_subtitle":"The minimum count of cyclic subsets in regular graphs jumps in discrete steps, not smoothly, as degree changes.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Counting Hamiltonian subsets: Sharp staircase bounds below Dirac threshold","Cyclic subset counts in regular graphs follow discrete staircase bounds","Staircase bounds pin down Hamiltonian subsets below Dirac threshold","Hamiltonian subset minimums jump in discrete steps below Dirac threshold","Exact staircase bounds for cyclic subsets below Dirac's threshold"],"cache_read_input_tokens":0,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Counting Hamiltonian subsets: Sharp staircase bounds below Dirac threshold","Cyclic subset counts in regular graphs follow discrete staircase bounds","Staircase bounds pin down Hamiltonian subsets below Dirac threshold","Hamiltonian subset minimums jump in discrete steps below Dirac threshold","Exact staircase bounds for cyclic subsets below Dirac's threshold","Discrete staircase bounds for Hamiltonian subsets in regular graphs"]},"model":"glm-5.2","effort":"high","cost_usd":0.0,"raw_usage":{"total_tokens":1119,"prompt_tokens":643,"completion_tokens":476,"prompt_tokens_details":null},"tokens_in":643,"tokens_out":476,"duration_ms":34303,"temperature":1.0,"reasoning_tokens":444,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-08T01:56:41.449212+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"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.","supporting_citations":[],"review_version":1}