REVIEW 2 major objections 5 minor 22 references
Exact threshold and limiting distribution for non-linear Hamilton cycles
T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read Random hypergraphs gain non-linear Hamilton cycles exactly once the expected count diverges, and the limiting count is lognormal at overlap 2.
desk verdict Good paper, probably right, but the lognormal case needs a real proof of the planted CLT. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument runs through a refined second-moment calculation combined with small subgraph conditioning, a technique that removes the random fluctuation contributed by small subgraphs. The paper introduces the variable $X = \frac{Z(C^{(r)}_{n,\ell})}{E[Z(C^{(r)}_{n,\ell})]}e^{-Y}$, where $Y=\sum_{k\ge1} t_k Y(P_k)$ is a weighted sum of normalized counts of short $\ell$-paths $P_k$ in the random hypergraph, with $t_k=\sqrt{A_k c^{-k}e^{-k(r-\ell)}}/(r-\ell)$. These short paths are precisely the small subgraphs whose random fluctuations inflate the ordinary second moment by a constant factor; multiplying by $e^{-Y}$ cancels that inflation and makes the second moment sharp. Under the original measure, the measure with one planted cycle, and the measure with two planted cycles of a given overlap, the vector of path counts is shown to be jointly Gaussian, which lets the paper evaluate the cancellation factor explicitly. For $\ell\ge3$ the corrected second moment is $1+o(1)$; for $\ell=2$ it fails by a factor that the Gaussian structure turns into the lognormal law.
What would settle it
Compute the third and fourth moments of the normalized short-path count $Y(P_1)$ under the planted measure for a concrete parameter pair such as $r=3,\ell=2$ and moderately large $n$; a deviation from the Gaussian values (third moment 0, fourth moment 3) beyond $o(1)$ would refute Lemma 3.2 and the lognormal limit it implies.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that the first-moment threshold is exact for Hamilton $\ell$-cycles in the random $r$-uniform hypergraph $G_r(n,p)$ for all $r>\ell>1$: whenever $E[Z(C^{(r)}_{n,\ell})]\to\infty$, the probability of finding a copy of $C^{(r)}_{n,\ell}$ tends to 1. More precisely, the normalized count $Z/E[Z]$ is $1+o(1)$ with high probability when $\ell\ge3$, and for $\ell=2$ it converges in distribution to a lognormal random variable with explicit parameters built from the constants $A_k$ (the numbers of automorphisms of length-$k$ $\ell$-paths). In the complementary regime where $E[Z]=m$ stays bounded, the count converges to a Poisson$(m)$ law for $\ell\ge3$ and to a Poisson mixture whose random rate is lognormal for $\ell=2$. Together these statements characterize the limiting behaviour of the cycle count in every parameter regime.
Load-bearing premise
The lognormal conclusion for overlap size $\ell=2$ depends on the claim that, even after planting one cycle or two overlapping cycles in the random hypergraph, the normalized counts of short paths still converge jointly to a normal distribution; the proof verifies only the first two moments of this limiting distribution.
Editorial extensions
If this is right
- The conjectured sharp threshold is confirmed: if $E[Z(C^{(r)}_{n,\ell})]\to\infty$ then a Hamilton $\ell$-cycle exists with probability tending to 1, with no extra logarithmic or constant factor.
- For $\ell\ge3$ the cycle count is asymptotically deterministic relative to its mean whenever the mean diverges; at bounded expectation it is Poisson$(m)$, so the full distribution is now known.
- For $\ell=2$ the count is lognormal with explicit series parameters when the expectation diverges, and a Poisson mixture with lognormal rate when the expectation is constant; the lognormal occurrence is a direct consequence of the small subgraph conditioning correction.
- The constants $A_k$ are explicit and uniformly bounded, so the lognormal variance and mixture rate can be evaluated numerically for any fixed $r$ and $\ell$.
Reading between the lines
- This suggests that other spanning structures whose ordinary second moment is inflated by a family of small connected subgraphs may also have lognormal counts, and that the same $e^{-Y}$ correction could be used to expose them.
- One testable extension is to check whether the lognormal behaviour at $\ell=2$ persists for $\ell=1$ (loose cycles), where the paper's assumptions exclude the case; the mechanism here is tied to the 'thick' two-edge overlap, so a different limit, perhaps a Poissonian one, is plausible.
- The paper's method also yields a Poisson mixture at constant expectation, which suggests that in the $\ell=2$ case the conditional law of the cycle count given the short-path fluctuations $Y$ is approximately Poisson, with the lognormal randomness entering only through $Y$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the number Z of Hamilton ℓ-cycles in the r-uniform Erdős–Rényi hypergraph G_r(n,p), for integers r > ℓ > 1 with (r − ℓ) | n, at densities p = (c + o(1))p*(r,ℓ). The main results are: for ℓ ≥ 3, Z/E[Z] → 1 in probability whenever E[Z] → ∞; for ℓ = 2, Z/E[Z] converges to an explicit lognormal distribution; and in the constant-expectation regime, Z converges to a Poisson law for ℓ ≥ 3 and to a lognormal mixture of Poissons for ℓ = 2. This confirms the conjecture of Narayanan and Schacht. The proof combines a refined second-moment computation (Section 2) with small-subgraph conditioning (Sections 3–4) and a subsampling argument for the constant-expectation case (Section 5).
Significance. If the proof is completed, the paper resolves a conjecture and gives the first sharp distributional characterization for non-linear Hamilton cycles at the threshold. The second-moment case analysis is detailed, the dichotomy ℓ ≥ 3 versus ℓ = 2 is clean, and the constants A_k entering the lognormal parameters are derived from automorphism counts rather than fitted to data; the choice of coefficients t_k is a standard variance-cancellation step, not a circular definition of the answer. The central unresolved point is the planted and double-planted central limit theorem asserted in Lemma 3.2, which is load-bearing for the ℓ = 2 results.
major comments (2)
- [§3, Lemma 3.2] The planted and double-planted joint Gaussianity assertions are not proved. The proof verifies only the first two moments under P* and P*2_t and then states that 'the convergence follows once we check that the dominant contribution comes from connected subgraphs.' First- and second-moment computations do not imply joint asymptotic normality for a polynomial functional of independent edge indicators; higher-order cumulants or a genuine multivariate normal approximation theorem are required. Lemma 3.3 subsequently evaluates the moment generating functions by Gaussian integration, including the identity covariance and means μ and 2μ, and the cancellation of the extra constant in Proposition 2.5 depends on these exact exponential factors. Without a complete proof of Lemma 3.2, the lognormal limit in Theorem 1.2(2) and the mixed-Poisson limit in Theorem 1.4(2) are not established. The gap appears localized and plausibly fillable, for instance by showing that under P* the vector equals its null counterpart on the complement plus a deterministic shift plus o_p(1), or by a full adaptation of Janson's orthogonal decomposition to the planted measures, but it must be supplied.
- [§4, Lemma 4.1] The application of Lemma 3.3 to the truncated variables ~Y_N is justified only by the sentence that truncation 'changes the first and second moments by o(1) factors.' Since the entire small-subgraph conditioning cancellation requires the exponential factors to be correct to within 1 + o(1), this step needs a quantitative tail estimate. The needed estimate is standard for a Gaussian variable with bounded variance at truncation level M = min{log log E[Z], log log n}, but it should be written out so that the reader can verify that the error is o(1) uniformly in the subsequent sums.
minor comments (5)
- [Throughout] The provided text contains numerous typographical and OCR artifacts, such as 'Ham ilton', 'Hamil ton', and a missing word in the abstract; these should be corrected in the final version.
- [§1.3, Eq. (1.1)] The sentence that A_k is 'constant' for sufficiently large k is not immediate from the definition A_k = Aut(P_k)/(t!(s−t)!)^k; only boundedness is needed for the argument. Please clarify the intended statement.
- [§4, Lemma 4.1, Case 2] The summation in Case 2 is written with the condition v(F) ≤ log n, although the case under discussion is log n < v(F) < n; this should be corrected to avoid confusion.
- [§4, Lemma 4.1] The proof says 'Choose N = N0(ε, δ)' but then uses N in the subsequent estimates; the notation should be aligned.
- [§5, Lemma 5.1] The notation |C1 ∩ C2| should be defined explicitly as the number of common edges, since for hypergraphs vertex overlap and edge overlap are both meaningful.
Circularity Check
No circularity: the small subgraph conditioning constants are derived, not fitted, and the cited null CLT is external; the sole weakness is an unproved planted CLT, which is a rigor gap, not circularity.
full rationale
The paper's central derivation is self-contained. The correction coefficients t_k in (1.1) are explicit combinatorial quantities, t_k = sqrt(A_k c^{-k} e^{-k(r-\ell)})/(r-\ell) with A_k = Aut(P_k)/(t!(s-t)!)^k, and are not fitted to the target distribution. The lognormal parameters in Theorem 1.2 are the sums of squares of these derived coefficients, obtained by combining Proposition 2.5 with the Gaussian moment computations in Lemma 3.3. The null-model CLT in Lemma 3.2 is cited to Janson [12], an independent external result; the planted and double-planted cases are asserted after first- and second-moment checks, which is a possible gap in proof detail but not circularity, since the asserted Gaussian limits are not assumed in the definition of Y or t_k and the variance cancellation in Lemma 3.3 is an algebraic identity conditional on Lemma 3.2. There are no self-citations, no uniqueness theorems imported from the author's own prior work, and no ansatz smuggled in via citation. Corollary 1.3 deduces Conjecture 1.1 from Theorem 1.2 rather than using it as an input. The only identified issue is the unproved joint CLT under planted measures, which concerns rigor and correctness, not circularity.
Assumptions & free parameters
assumptions (3)
- standard math Janson's orthogonal decomposition central limit theorem for subgraph counts in G^r(n,p) applies to the null model and yields joint Gaussianity of the Y(P_k).
- domain assumption Under planted and double-planted models, the normalized path counts Y(P_k) remain jointly Gaussian despite the planted cycle breaking the homogeneous orthogonal decomposition.
- domain assumption The density parameter c is treated as a fixed bounded constant with p = (c+o(1))p*; the lognormal parameters and all asymptotics are computed with c fixed.
Cite this review
Pith. "Pith review of Exact threshold and limiting distribution for non-linear Hamilton cycles." pith.science (2026). https://pith.science/paper/NVUVCGWA
@misc{pith2026241113452,
author = {Pith},
title = {Pith review of: Exact threshold and limiting distribution for non-linear Hamilton cycles},
year = {2026},
howpublished = {\url{https://pith.science/paper/NVUVCGWA}},
note = {Machine review of arXiv:2411.13452}
}
abstract
For positive integers $r > \ell \geq 1$, an $\ell$-cycle in an $r$-uniform hypergraph is a cycle where each edge consists of $r$ vertices and each pair of consecutive edges intersect in $\ell$ vertices. For $\ell \geq 2$, we determine the limiting distribution of the number of Hamilton $\ell$-cycles in an Erd\H{o}s--R\'enyi random hypergraph. The behavior is distinguished in two cases: -When $\ell \geq 3$, the number of cycles concentrates when the expectation diverges and converges to a Poisson distribution when the expectation is constant. -When $\ell = 2$, the normalized number of cycles converges to a lognormal distribution when the expectation diverges and converges to a lognormal mixture of Poisson distributions when the expectation is constant. As a result we pin down the exact threshold for the appearance of non-linear Hamilton cycles in random hypergraphs, confirming a conjecture of Narayanan and Schacht.
Reference graph
Works this paper leans on
-
[1]
Emmanuel Abbe, Shuangping Li, and Allan Sly, Proof of the contiguity conjecture and lognormal limit for t he symmetric perceptron, 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science—FOCS 2021, IEEE Computer Soc., Los Alamitos, CA, [2022] ©2022, pp. 327– 338. 4
work page 2021
- [2]
-
[3]
Debapratim Banerjee, Contiguity and non-reconstruction results for planted par tition models: the dense case , Electron. J. Probab. 23 (2018), Paper No. 18, 28. 4
work page 2018
-
[4]
Béla Bollobás, Threshold functions for small subgraphs , Math. Proc. Cambridge Philos. Soc. 90 (1981), 197–206. 1
work page 1981
-
[5]
Amin Coja-Oghlan, Charilaos Efthymiou, and Samuel Hett erich, On the chromatic number of random regular graphs, J. Combin. Theory Ser. B 116 (2016), 367–439. 4
work page 2016
-
[6]
Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari, Mi hyun Kang, and Tobias Kapetanopoulos, Charting the replica symmetric phase , Comm. Math. Phys. 359 (2018), 603–698. 4
work page 2018
-
[7]
Andrzej Dudek and Alan Frieze, Loose Hamilton cycles in random uniform hypergraphs , Electron. J. Combin. 18 (2011), Paper 48, 14. 1
work page 2011
-
[8]
Andrzej Dudek and Alan Frieze, Tight Hamilton cycles in random uniform hypergraphs , Random Structures Algorithms 42 (2013), 374–385. 1
work page 2013
Show all 22 references
-
[9]
Erdős and A
P. Erdős and A. Rényi, On the existence of a factor of degree one of a connected rando m graph , Acta Math. Acad. Sci. Hungar. 17 (1966), 359–368. 1
1966
-
[10]
Ehud Friedgut, Sharp thresholds of graph properties, and the k-sat problem , J. Amer. Math. Soc. 12 (1999), 1017–1054, With an appendix by Jean Bourgain. 2, 3
1999
-
[11]
Andreas Galanis, Daniel Štefankovič, and Eric Vigoda, Inapproximability of the partition function for the anti- ferromagnetic Ising and hard-core models , Combin. Probab. Comput. 25 (2016), 500–559. 4
2016
-
[12]
Svante Janson, Orthogonal decompositions and functional limit theorems f or random graph statistics, Mem. Amer. Math. Soc. 111 (1994), vi+78. 10
1994
-
[13]
Svante Janson, Random regular graphs: asymptotic distributions and conti guity, Combin. Probab. Comput. 4 (1995), 369–405. 4
1995
-
[14]
Anders Johansson, Jeff Kahn, and Van Vu, Factors in random graphs , Random Structures Algorithms 33 (2008), 1–28. 1
2008
-
[15]
43 (1983), 55–63
János Komlós and Endre Szemerédi, Limit distribution for the existence of Hamiltonian cycles in a random graph, Discrete Math. 43 (1983), 55–63. 1
1983
-
[16]
Theory Related Fields 162 (2015), 431–461
Elchanan Mossel, Joe Neeman, and Allan Sly, Reconstruction and estimation in the planted partition mod el, Probab. Theory Related Fields 162 (2015), 431–461. 4
2015
-
[17]
Theory Related Fields 143 (2009), 401–439
Elchanan Mossel, Dror Weitz, and Nicholas Wormald, On the hardness of sampling independent sets beyond the tree threshold, Probab. Theory Related Fields 143 (2009), 401–439. 4
2009
-
[18]
1, 2, 3, 5
Bhargav Narayanan and Mathias Schacht, Sharp thresholds for nonlinear Hamiltonian cycles in hyper graphs, Random Structures Algorithms 57 (2020), 244–255. 1, 2, 3, 5
2020
-
[19]
Jinyoung Park and Huy Tuan Pham, A proof of the Kahn-Kalai conjecture , J. Amer. Math. Soc. 37 (2024), 235–243. 1
2024
-
[20]
Pósa, Hamiltonian circuits in random graphs , Discrete Math
L. Pósa, Hamiltonian circuits in random graphs , Discrete Math. 14 (1976), 359–364. 1
1976
-
[21]
Oliver Riordan, Spanning subgraphs of random graphs , Combin. Probab. Comput. 9 (2000), 125–148. 1
2000
-
[22]
R. W. Robinson and N. C. Wormald, Almost all regular graphs are Hamiltonian , Random Structures Algorithms 5 (1994), 363–374. 4
1994
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.