{"id":"dd246dea-4870-431a-9092-8f88b597f0f9","arxiv_id":"2411.18596","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The threshold for a (d, α)-degenerate bounded-degree k-uniform hypergraph to appear in the random k-uniform hypergraph is at most n^{-1/d}, removing the logarithmic factor from prior bounds.","lead":"A new proof shows that a broad class of sparse hypergraphs, called (d, α)-degenerate, appear in random hypergraphs once the edge probability reaches about n^{-1/d}, removing a logarithmic factor from earlier bounds. The result sharpens the threshold for locally sparse regular graphs and improves known thresholds for degenerate hypergraphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the α>0 spreadness argument is internally consistent; only the α-values in the motivating examples need small corrections.","rationale":"I reviewed the central argument in good faith. Theorem 1.4 is an upper bound on the threshold for (d,α)-degenerate hypergraphs, and its proof goes through Proposition 2.4 plus Spiro's spreadness criterion. The key innovation is using the α-deficit to obtain a vertex lower bound for small connected subgraphs, and then choosing a geometric scale sequence to control all intermediate edge-set sizes. I checked the three main inequalities: the top interval t∈[εn/k,dn] uses only the q-spread property from Proposition 2.4; the lower intervals use the component bound from Proposition 2.4 together with the degeneracy lower bound; and the count of t-edge, c-component subgraphs is handled by Lemma 3.2. The α-slack cancels the n^{αc/d} factor coming from the binomial count, leaving the required (C/n^{1/d})^t rate. The constants and rounding of the r_i sequence are informal but standard and do not affect the existence of a suitable C. The reader's weakest assumption—that α>0 be a fixed positive constant—is indeed the crucial hypothesis: without it the vertex lower bound loses its slack and the log n factor genuinely reappears. However, this is exactly the hypothesis of the theorem, so it is not a flaw. The only real defect I found is in the motivating examples: the claimed (3,3)-degeneracy of planar graphs is false for 2-vertex subsets containing an edge, and the stated α for cycle powers is likewise too large for small subsets. These are presentation/scope errors, not counterexamples to Theorem 1.4, since the corrected α-values still satisfy Definition 1.2 and the same proof applies. For that reason I do not ask for a change in verdict beyond the already conditional status.","tokens_in":9141,"tokens_out":39022,"duration_ms":339181,"concrete_test":"Recompute Example 1.3 for planar graphs with |U|=2 and verify that Definition 1.2 forces α≤d−1 whenever G contains an edge; then confirm that replacing the claimed (3,3)-degeneracy by (3,2)-degeneracy leaves the proof of Theorem 1.4 unchanged. Independently, re-derive inequality (3) in the proof of Theorem 2.7 for the boundary case t=1, |S|=1, k=2, d=3, α=2 to check that the claimed n^{-α/(10d)} saving is not needed for the small-set bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No load-bearing gap found in the central claim. Theorem 1.4 follows from Theorem 2.7, and the proof's key step—verifying Spiro spreadness via the α-deficit—is internally coherent: the lower bound v ≥ t/d + 1 + α/d for every connected subgraph with t ≤ εn/k follows from Definition 1.2, and the geometric scale n^{-9α/(10d)} is chosen so that the binomial factor (k|S| choose c) is dominated by n^{αc/d} (or by 2^t), leaving the desired (C/n^{1/d})^t bound. The α>0 assumption is genuinely essential—α=0 restores the log n thresholds—but it is part of the theorem's hypothesis, not an objection to it. The one concrete error is in the advertised scope: Example 1.3(2) says planar graphs are (3,3)-degenerate, but for a 2-vertex edge subset e(G[U])=1 > 3(2−1)−3=0, so the definition fails; planar graphs are (3,2)-degenerate, and Theorem 1.4 still applies. Similar slack corrections are needed for some cycle-power examples, but the central claim and its proof are unaffected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":9398,"tokens_out":20906,"duration_ms":182173,"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.","major_comments":[],"minor_comments":[{"comment":"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":"Section 1, Example 1.3(2)"},{"comment":"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":"Section 1, Example 1.3(1)"},{"comment":"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.","section":"Section 1, Example 1.3(3)"},{"comment":"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.","section":"Theorem 2.7 statement"},{"comment":"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":"Proof of Theorem 2.7, inequalities (2)-(3)"},{"comment":"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.","section":"Section 1, definition of p_E(G)"},{"comment":"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":"Proposition 2.4"},{"comment":"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.","section":"Section 4, Theorem 4.2 attribution"}],"recommendation":"minor_revision","confidential_remarks":"The main theorem appears correct and the proof is repairable. The errors in Example 1.3 and the omitted constant factor in the proof of Theorem 2.7 are local and do not threaten the central result. A careful revision that fixes the examples, defines l in the statements, and makes the constant absorption explicit would make the paper fully convincing."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this paper proves th(G) ≤ n^{-1/d} for bounded-degree (d,α)-degenerate hypergraphs, removing the log factor from the Kelly–Müyesser–Pokrovskiy bound. The proof is a legitimate extension of the KMP machinery: the α-deficit forces every small connected subgraph to have v ≥ t/d + 1 + α/d, and that extra vertex slack lets the authors run Spiro's multiscale spreadness with a geometric scale sequence. The main theorem is new and the argument checks out.\n\nThe paper is honest about the limits: α>0 is essential, and they say so (Hamilton cycles and spanning trees are (1,0)-degenerate with threshold log n/n). The corollary on locally sparse regular graphs is a nice byproduct, and the last section, using Kelly's strengthening to upgrade the error probability to 1-o(1), is a sensible addition.\n\nSoft spots are minor. The advertised examples have real errors: planar graphs are claimed (3,3)-degenerate, but for a 2-vertex set e(G[U])=1 > 3(2-1)-3=0, so the definition fails; (3,2) works. Some cycle-power slack values also need adjustment, e.g., r=2 fails for 2-vertex sets. These do not touch the main theorem, since the corrected α values are still positive. There are also small typos: the p_E definition in the introduction is missing the n^{v(F)} factor, and l in Theorem 2.7 is not defined until later in the proof. A referee should ask for these fixes, not for any change in the argument.\n\nThe lower-bound construction for Corollary 1.5 is sketched tersely but seems fine. Citation patterns are clean; the load-bearing external results are KMP's Proposition 2.4 and Spiro's Theorem 2.6, both independent prior work.\n\nWho benefits: people working on thresholds for spanning subgraphs, the Kahn–Kalai conjecture, and spreadness methods. It deserves a serious referee. I would send it to review and recommend minor revision.","headline":"Proves threshold n^{-1/d} for bounded-degree (d,α)-degenerate hypergraphs, removing the log factor from KMP; solid proof, minor example errors.","tokens_in":9916,"tokens_out":2442,"would_cite":true,"duration_ms":21567,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C65","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["thresholds","degenerate hypergraphs","random hypergraphs","spreadness","vertex spread","locally sparse graphs","binomial random graphs","expectation thresholds"],"falsifier":"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.","tokens_in":8967,"feed_emoji":"🎲","tokens_out":11387,"duration_ms":91923,"temperature":0.7,"pith_summary":"The paper establishes an upper bound on the threshold for finding a fixed bounded-degree hypergraph in the binomial random $k$-uniform hypergraph $G^{(k)}(n,p)$. For any $n$-vertex $(d,\\alpha)$-degenerate $k$-uniform hypergraph with bounded maximum degree, a copy of $G$ appears with high probability once $p$ is at least a sufficiently large constant times $n^{-1/d}$. Earlier results gave only $n^{-1/d}\\log n$. The improvement removes the logarithmic factor by combining a vertex-spread distribution on embeddings with a scale-by-scale spreadness estimate that exploits the fixed deficit $\\alpha>0$ in the edge counts of small subgraphs. If the argument is correct, the threshold matches the natural expectation-threshold lower bound for hypergraphs with nearly $dn$ edges.","feed_headline":"Sparse hypergraphs appear once p is a constant times n^{-1/d}","feed_subtitle":"It removes the log factor from earlier bounds and matches the expectation threshold for sparse spanning hypergraphs.","key_machinery":"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$.","core_discovery":"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}$.","pith_inferences":["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."],"forward_implications":["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})$."],"supporting_citations":[{"why":"Supplies Proposition 2.4, the vertex-spread to spread conversion and the previous $n^{-1/m_1(G)}\\log n$ threshold that the paper improves.","marker":"[10]"},{"why":"Provides Theorem 2.6, the layered spreadness condition and the random-set hitting bound that turns spreadness into a threshold.","marker":"[14]"},{"why":"Provides Theorem 4.2, the refined spreadness theorem used to obtain the semi-sharp threshold in Section 4.","marker":"[9]"},{"why":"Gives the earlier $n^{-1/d}$ threshold for $(d,d)$-degenerate graphs via the second moment; the paper improves it by allowing any fixed $\\alpha>0$.","marker":"[13]"}],"fun_headline_variants":["Sparse hypergraph threshold drops to n^{-1/d}","Log factor vanishes for degenerate hypergraphs","New bound: degenerate hypergraphs emerge at n^{-1/d}","Semi-sharp threshold for degenerate hypergraphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Sparse hypergraph threshold drops to n^{-1/d}","Log factor vanishes for degenerate hypergraphs","New bound: degenerate hypergraphs emerge at n^{-1/d}","Semi-sharp threshold for degenerate hypergraphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000301,"raw_usage":{"total_tokens":1702,"prompt_tokens":881,"completion_tokens":821,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":497,"completion_tokens_details":{"reasoning_tokens":757}},"tokens_in":497,"tokens_out":821,"duration_ms":7879,"temperature":1.0,"reasoning_tokens":757,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:05:06.357328+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Kelly, A","cited_arxiv_id":null,"evidence_quote":"Supplies Proposition 2.4, the vertex-spread to spread conversion and the previous $n^{-1/m_1(G)}\\log n$ threshold that the paper improves."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides Theorem 2.6, the layered spreadness condition and the random-set hitting bound that turns spreadness into a threshold."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides Theorem 4.2, the refined spreadness theorem used to obtain the semi-sharp threshold in Section 4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the earlier $n^{-1/d}$ threshold for $(d,d)$-degenerate graphs via the second moment; the paper improves it by allowing any fixed $\\alpha>0$."}],"review_version":1}