REVIEW 8 minor 15 references
On the thresholds of degenerate hypergraphs
T0 review · 0 major / 8 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read Every bounded-degree $(d,\alpha)$-degenerate $k$-uniform hypergraph appears in the random hypergraph $G^{(k)}(n,p)$ once $p$ is a large constant times $n^{-1/d}$, removing a logarithmic factor from earlier threshold bounds.
desk verdict Proves threshold n^{-1/d} for bounded-degree (d,α)-degenerate hypergraphs, removing the log factor from KMP; solid proof, minor example errors. 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 central object is the $(d,\alpha)$-degenerate $k$-uniform hypergraph: one with $m_1(G)\le d$ and a fixed positive $\alpha$ such that every subset $U$ of size at most $\varepsilon n$ spans at most $d(|U|-1)-\alpha$ edges. The proof machinery is layered spreadness (Definition 2.5): a probability measure on copies of $G$ is controlled scale by scale, from large edge sets down to singletons. The key estimate is inequality (3), which bounds the probability that a random copy meets a given $t$-edge set by $n^{-0.1\alpha/d}$ times $(C/n^{1/d})^t$ for small $t$. This decay follows from counting subgraphs through Lemma 3.2 and using the vertex lower bound $v\ge t/d+1+\alpha/d$ for connected subgraphs of $G$.
What would settle it
Construct a sequence of $n$-vertex $(d,\alpha)$-degenerate $k$-uniform hypergraphs with fixed $\alpha>0$ and bounded maximum degree whose threshold is $\Theta(n^{-1/d}\log n)$; the paper's own examples show $\alpha=0$ gives $\log n/n$, so such a family would directly contradict Theorem 1.4. A more targeted check is to verify inequality (3) on a concrete family whose small subgraphs have edge count $d(|U|-1)-\beta$ for $\beta$ much smaller than $\alpha$; if the decay $n^{-0.1\alpha/d}$ fails, the spreadness claim collapses.
Extended reading notes
Core claim
The central discovery is that the spread distribution produced for copies of $G$ satisfies a layered spreadness condition with a constant number of scales, provided $G$ is $(d,\alpha)$-degenerate and has bounded maximum degree. The fixed deficit $\alpha>0$ forces every small connected subgraph with $t$ edges to have at least $t/d+1+\alpha/d$ vertices; this vertex lower bound drives a geometric scale sequence $r_i=r_{i-1}/n^{9\alpha/(10d)}$ that lets the logarithmic factor in the threshold vanish. Consequently the main theorem, Theorem 2.7, gives $\operatorname{th}(G)\le n^{-1/d}$, and the refinement in Section 4, Theorem 4.3, turns this into a semi-sharp threshold with failure probability $o(1)$ once $p\ge C^* n^{-1/d}$.
Load-bearing premise
The argument requires the deficit $\alpha$ in Definition 1.2 to be a fixed positive constant; if $\alpha=0$, as for Hamilton cycles or spanning trees, the threshold can be $\log n/n$, so the removal of the logarithmic factor rests entirely on this positivity.
Editorial extensions
If this is right
- If a sequence of graphs is $(d,\varepsilon)$-locally sparse and $d$-regular, then its threshold is exactly $n^{-2/d}$ (Corollary 1.5).
- The boundary condition in local sparseness is tight: there exist $d$-regular graphs with minimum edge boundary exactly $d$ whose threshold is $\gg n^{-2/d}$, so the condition $|\partial U|\ge d+1$ cannot be weakened to $|\partial U|\ge d$.
- For $(d,\alpha)$-degenerate hypergraphs with $e(G)\ge dn-O(1)$, the threshold ratio $\operatorname{th}(G)/p_E(G)$ is bounded by a constant, so the conjectured logarithmic gap between threshold and expectation threshold vanishes for this class.
- The upper bound $n^{-1/d}$ is best possible for asymptotically maximal $(d,\alpha)$-degenerate graphs, since then $p_E(G)\ge n^{-1/d}$ by the expected number of copies.
- With the semi-sharp version (Theorem 4.3), every nearly maximally $(d,\alpha)$-degenerate hypergraph has a sharp threshold: the probability of containing $G$ jumps from $o(1)$ to $1-o(1)$ at $p=\Theta(n^{-1/d})$.
Reading between the lines
- One could test whether the fixed-$\alpha$ requirement can be relaxed to a slowly decaying deficit $\alpha(n)=\omega(1/\log n)$; the proof's scale sequence would then have length growing with $n$, and the conclusion may become a polylog factor rather than no factor.
- The same geometric-scale mechanism may apply to other families that satisfy a uniform vertex surplus $v\ge t/d+1+\delta$ on all small connected subgraphs, even without an obvious degeneracy parameter; this suggests a general 'small-subgraph surplus' criterion for log-free thresholds.
- Because the counting bounds are polynomial in the maximum degree $\Delta$, one might push the argument to graphs with $\Delta=n^{o(1)}$ or $\Delta=n^{\delta}$ for small $\delta$, obtaining thresholds $n^{-1/d+o(1)}$; this is an extension the paper does not claim.
- The tightness construction for locally sparse graphs suggests that the edge-boundary threshold $d+1$ is exactly what separates log-free thresholds from thresholds with a $\log^{1/(d-1)}n$ factor; an analogous construction for $k$-uniform hypergraphs with $k\ge 3$ would test whether the same boundary condition remains sharp.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies the threshold for the appearance of an n-vertex (d,alpha)-degenerate k-uniform hypergraph G with maximum degree at most Delta in the binomial random k-uniform hypergraph G^(k)(n,p). The main result, Theorem 1.4 (via the stronger Theorem 2.7), states that every such G is found w.h.p. once p is a sufficiently large constant times n^{-1/d}; this removes the logarithmic factor from the previous bound th(G) <= n^{-1/d} log n of Kelly-Muyesser-Pokrovskiy. The proof transfers a vertex-spread distribution on embeddings into an edge-spread distribution on copies using Proposition 2.4, then verifies Spiro's refined (q;r_0,...,r_l)-spreadness. The new mechanism is the fixed deficit alpha>0 in Definition 1.2, which yields the vertex lower bound v >= t/d + 1 + alpha/d for every small connected subgraph with t edges; this extra alpha c/d in the exponent dominates the combinatorial factors at all geometric scales and eliminates the log factor. The paper also contains a construction showing that the local-sparsity condition in Corollary 1.5 is tight, and an additional section using Kelly's refinement to obtain semi-sharp thresholds.
Significance. If correct, the main theorem is a substantial and clean improvement: it gives an n^{-1/d} threshold for a broad class of degenerate hypergraphs, strictly improving the earlier n^{-1/d} log n bound whenever alpha>0, and it is best possible for asymptotically extremal (d,alpha)-degenerate graphs. The proof is modular and the reliance on external results (KMP's Proposition 2.4 and Spiro's Theorem 2.6) is transparent. The paper is also honest about the boundary of the method: it explains that alpha=0 (Hamilton cycles, spanning trees) restores the log n/n threshold, so the positivity of alpha is not an artifact. The derivation contains no free parameters or fitted constants; all constants are explicit and depend only on k, Delta, d, alpha. The examples in Section 1 contain incorrect alpha-values, but these are easily corrected and do not affect the validity of the main theorem.
minor comments (8)
- [Section 1, Example 1.3(2)] The claim that planar graphs are (3,3)-degenerate fails for a 2-vertex induced subgraph U, since e(G[U]) can be 1 but 3(|U|-1)-3 = 0. The correct statement is that planar graphs are (3,2)-degenerate, and Theorem 1.4 still applies with that value.
- [Section 1, Example 1.3(1)] The stated (d,d/2)-degeneracy does not match the displayed computation e(G) <= d(n-d) + C(d,2) = d(n-1) - C(d,2); the computation gives alpha = C(d,2) = d(d-1)/2, not alpha = d/2.
- [Section 1, Example 1.3(3)] The stated values alpha = 2 - 1/r for the r-th power of a cycle and alpha = 1 - 1/k for the r-th power of a tight cycle appear incorrect; for example, for r=2 the square of a cycle is not (2,3/2)-degenerate because a 3-vertex consecutive set has 3 edges while 2(3-1)-3/2 = 5/2. The natural edge count for C_n^r gives alpha = C(r,2), so the examples need correction, though any positive alpha suffices for Theorem 1.4.
- [Theorem 2.7 statement] The parameter l is used in the definition of the sequence r_0,...,r_l but is not defined in the statement; it is defined only later in the proof as l = max{2, ceil(10d/(9 alpha))}. This definition should appear in the theorem statement, and similarly in Theorem 4.3.
- [Proof of Theorem 2.7, inequalities (2)-(3)] The displayed chain from the line after (2) to the line beginning with t* is not literally correct: substituting the bound (k|S| choose c) <= 2^t n^{alpha c/d} into the preceding sum yields an extra factor (k Delta C_2)^{alpha c/d}, which is not retained. Since c <= t, this extra factor is at most a constant to the power t and can be absorbed into the constant C-tilde; the claimed spreadness still follows after this adjustment, but the proof should be corrected.
- [Section 1, definition of p_E(G)] The displayed definition of p_E(G) omits the factor (n)_{v(F)} (or n^{v(F)}) in the expected number of copies of F in G(n,p); as written, the inequality has the wrong dependence on n.
- [Proposition 2.4] The notation k Delta C^2/n uses an undefined C^2; it should be k Delta C_{2.4}/n or the constant C_{2.4} should be explicitly named in that display.
- [Section 4, Theorem 4.2 attribution] The sentence 'slightly stronger version of the result of Spiro [14, Theorem 2.7]' should refer to Theorem 2.6 of the present paper, which is Spiro's theorem; as written the numbering is confusing.
Circularity Check
No significant circularity: Theorem 1.4 derives from external spreadness theorems and the (d,alpha)-degeneracy hypothesis, with no fitted parameters or load-bearing self-citations.
full rationale
The paper's central result Theorem 1.4 follows from Theorem 2.7, whose proof uses independent external results: Proposition 2.4 from Kelly-Muyesser-Pokrovskiy, Theorem 2.6 from Spiro, and elementary counting Lemmas 3.1 and 3.2. The only property of (d,alpha)-degenerate hypergraphs used is v >= t/d + 1 + alpha/d for connected subgraphs with t <= epsilon n/k, which follows directly from Definition 1.2; it is a hypothesis, not a restatement of the threshold. The parameter alpha appears in the geometric scale r_i = r_{i-1}/n^{9alpha/(10d)} but is not fitted from any data. No self-citations by the authors are load-bearing. The paper explicitly notes that for alpha=0 the bound fails (Hamilton cycles and spanning trees have threshold log n/n), confirming alpha>0 is doing real work rather than being a disguised form of the conclusion. Although Example 1.3(2) misstates planar graphs as (3,3)-degenerate, this is a correctness issue in a motivating example and does not affect the proof of Theorem 2.7. Thus the derivation is self-contained relative to its external inputs and no circularity is present.
Assumptions & free parameters
assumptions (3)
- domain assumption Proposition 2.4 (Kelly, Müyesser, Pokrovskiy): a (C/n)-vertex spread distribution on embeddings yields a spread distribution on copies with the stated componentwise bounds.
- domain assumption Theorem 2.6 (Spiro): a (q;r0,...,rl)-spread distribution implies a random set of size C l q |V| contains an edge with probability close to 1.
- domain assumption Lemma 3.1 (Kelly, Müyesser, Pokrovskiy): bound on the number of embeddings G[X] into H[V(F)] for F with v vertices and c components.
Cite this review
Pith. "Pith review of On the thresholds of degenerate hypergraphs." pith.science (2026). https://pith.science/paper/FDEUPU3J
@misc{pith2026241118596,
author = {Pith},
title = {Pith review of: On the thresholds of degenerate hypergraphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/FDEUPU3J}},
note = {Machine review of arXiv:2411.18596}
}
abstract
An $n$-vertex $k$-uniform hypergraph $G$ is $(d,\alpha)$-degenerate if $m_1(G)\le{d}$ and there exists a constant $\varepsilon >0$ such that for every subset $U\subseteq{V(G)}$ with size $2\le|U|\le{\varepsilon n}$, we have $e\left(G[U]\right)\le{d\left(|U|-1\right)-\alpha}$. These hypergraphs include many natural graph classes, such as the degenerate hypergraphs, the planar graphs, and the power of cycles. In this paper, we consider the threshold of the emergence of a $(d,\alpha)$-degenerate hypergraph with bounded maximum degree in the Erd\H{o}s-R\'enyi model. We show that its threshold is at most $n^{-1/d}$, improving previous results of Riordan and Kelly-M\"uyesser-Pokrovskiy.
Reference graph
Works this paper leans on
- [1]
-
[2]
P. Erdős and A. Rényi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. , 5:17–61, 1960
work page 1960
-
[3]
A. Espuny Díaz and Y. Person. Spanning F -cycles in random graphs. Combin. Probab. Comput. , 32(5):833– 850, 2023. 7
work page 2023
- [4]
-
[5]
K. Frankston, J. Kahn, B. Narayanan, and J. Park. Thresho lds versus fractional expectation-thresholds. Ann. of Math. , 194(2):475–495, 2021
work page 2021
-
[6]
A. Johansson, J. Kahn, and V. Vu. Factors in random graphs . Random Structures & Algorithms , 33(1):1–28, 2008
work page 2008
-
[7]
F. Joos, R. Lang, and N. Sanhueza-Matamala. Robust Hamil tonicity. arXiv:2312.15262, 2023
arXiv 2023
-
[8]
J. Kahn and G. Kalai. Thresholds and expectation thresho lds. Combin. Probab. Comput. , 16(3):495–502, 2007
work page 2007
Show all 15 references
-
[9]
T. Kelly. A spread blow-up lemma and robust versions of th e Pósa–Seymour conjecture and the bandwidth theorem. manuscript
-
[10]
Kelly, A
T. Kelly, A. Müyesser, and A. Pokrovskiy. Optimal sprea d for spanning subgraphs of Dirac hypergraphs. J. Combin. Theory Ser. B , 169:507–541, 2024
2024
-
[11]
Park and H
J. Park and H. T. Pham. A proof of the Kahn-Kalai conjectu re. J. Amer. Math. Soc. , 37(1):235–243, 2024
2024
-
[12]
H. T. Pham, A. Sah, M. Sawhney, and M. Simkin. A toolkit fo r robust thresholds. arXiv:2210.03064, 2022
2022 arXiv
-
[13]
O. Riordan. Spanning subgraphs of random graphs. Combin. Probab. Comput. , 9(2):125–148, 2000
2000
-
[14]
S. Spiro. A smoother notion of spread hypergraphs. Combin. Probab. Comput. , 32(5):809–818, 2023
2023
-
[15]
Talagrand
M. Talagrand. Are many small sets explicitly small? In STOC’10—Proceedings of the 2010 ACM Interna- tional Symposium on Theory of Computing , pages 13–35. ACM, New York, 2010. School of Ma thema tics and Sta tistics, Beijing Institute of Technology, Beijing, China Email addres...
2010
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.