{"id":"6184c713-1536-45a2-ad3c-3b26959ff4b7","arxiv_id":"2507.05697","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The critical probability for the existence of a K3-activating spanning tree in G(n,p) is p = n^{-1/3-o(1)}.","lead":"This paper finds the probability p at which a random graph almost surely contains a spanning tree that can gradually activate all other edges, each new edge completing a triangle. It ties this activation problem to the topology of random clique complexes and pins the threshold at p = n^{-1/3}.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the central threshold proof is internally sound, and its only external dependency (Theorem 1.5) is cited in its valid range.","rationale":"The Reader identified the dependency on Theorem 1.5 as the weakest assumption, and I agree that this is the least self-contained step in proving the central threshold. However, a dependency on a correctly cited published theorem is not a correctness objection. I examined the constructive upper-bound proof for hidden assumptions and found no fatal gap; the few delicate points (e.g., the choice of c in Claim 3.1 and the counting in Lemma 5.10) are either repairable with standard constants or absorbable in the stated bounds. The 0-statement of Theorem 1.3 and the Linial-Meshulam extensions are more involved, but they are not load-bearing for Theorem 1.2. Therefore the Reader's ACCEPT verdict stands unchanged.","tokens_in":40393,"tokens_out":44900,"duration_ms":514346,"concrete_test":"As a worthwhile verification, independently check the exact statement in Babson (arXiv:1207.5028) and Costa-Farber-Horak (Trans. LMS 2015) to confirm Theorem 1.5 indeed gives non-simple connectivity for every p ≤ n^{-1/3-ε}, and then re-derive the contrapositive use: if X^(2)(G) is not simply connected, no spanning tree can activate G. If the cited range matches the paper's application, the lower-bound exponent n^{-1/3-o(1)} is established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After reading the paper in good faith, I do not find an internal flaw that threatens the central claim. The upper bound in Theorem 1.2 is constructive and self-contained; the lower bound is the only non-self-contained part, combining Lemma 4.1 with the cited Babson/Costa-Farber-Horak theorem on non-simple connectivity of X^(2)(G(n,p)) for p ≤ n^{-1/3-ε}. This is a legitimate use of a published external result, and the contrapositive is valid. The intricate counting machinery for Theorem 1.3 is internally consistent, and the constants align with the stated bound c < 2^{-7/3}. The paper's own remarks about limitations and the diameter barrier are consistent with the proof. Thus, no load-bearing concern lands; the main risk is inherited from an external theorem, but that is not an identified error.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the threshold probability for a spanning tree of G(n,p) to weakly saturate the graph in K3-bootstrap percolation. It proves Theorem 1.2, that this threshold is n^{-1/3-o(1)}, and Theorem 1.3, which determines the threshold up to a constant factor for trees of diameter at most n^{1/18-ε}. The main new ingredient is a topological bridge: an activating tree implies the 2-dimensional clique complex X^{(2)}(G) is simply connected (Lemma 4.1), which combines with known results on simple connectivity of random clique complexes. The 0-statement of Theorem 1.3 rests on a new local-to-global counting argument over 'activation diagrams' (Section 5), and the paper also derives an improved simple-connectivity threshold as Corollary 1.6.","tokens_in":40469,"tokens_out":47974,"duration_ms":502517,"significance":"The results resolve a question of Korándi and Sudakov up to subpolynomial factors, and the topological connection between bootstrap percolation and clique-complex simple connectivity is a novel and promising idea. The 1-statement is constructive, and the local-to-global activation-principle (Proposition 5.18) is an original technical contribution. If the proofs are correct, the paper opens a new route to weak-saturation thresholds in sparse random graphs. The paper also honestly discusses its limitations: the diameter restriction in Theorem 1.3 and the reliance on the external theorem of Babson, Costa, Farber, and Horak for the n^{-1/3} lower bound.","major_comments":[{"comment":"The equality E[Z^ℓ_{v,w}] = Σ_{D∈P_{v,w}} p^{|E(D)|} is not justified. Activation diagrams are labelled complexes in which distinct vertices may carry the same label (see the remark in Lemma 5.9 that 'vertices with equal labels are considered as different vertices here'). Consequently two distinct 1-faces of D can map to the same edge of G, and the event D ⊆ X^{(2)}(G) only requires that edge once. The probability is p^{m(D)}, where m(D) is the number of distinct edge labels, and m(D) can be strictly smaller than |E(D)|. Since p < 1, the expression p^{|E(D)|} underestimates the true probability. A concrete example is a star activation: let H be a star on vertices x,a,b,c,d and let C be the 4-cycle a-b-c-d-a, activating each cycle edge through triangles using x. The activation diagram has four triangles with |E(D)| = 12, but the distinct edge labels are only the eight edges of H and C, so the probability is p^8, not p^{12}. This affects the first-moment estimates in Lemmas 5.12 and 5.13 and hence the proof of the 0-statement of Theorem 1.3.","section":"5.2, Lemma 5.11"},{"comment":"The proof of Claim 3.1 shows that the giant component of G[U_i] has neighbours of z and w, but the claim requires z and w themselves to lie in the giant component C(u_i) of H(u_i). The connecting step is missing: one must argue that, for a sufficiently small constant c, any component of size at least c n^{1/3} inside U_i is the unique giant component of H(u_i), so the exhibited edges place z and w in C(u_i). As written, the displayed probability estimates only show that the giant component of G[U_i] contains some neighbours of z and w, not that z and w belong to C(u_i). This is a load-bearing step for the constructive proof of the 1-statement.","section":"3, Claim 3.1"}],"minor_comments":[{"comment":"The word 'initialasing' in the first step of Definition 5.8 should be 'initialising'.","section":"5.1, Definition 5.8"},{"comment":"The notation 'H G− →C' appears garbled; it should be 'H → C'.","section":"5.2, Lemma 5.12"},{"comment":"The proof restricts to p ≥ n^{-1/3-ε'} without explaining that the complementary range p < n^{-1/3-ε'} is already covered by the 0-statement of Theorem 1.2.","section":"5.4, proof of Theorem 1.3 part 2"},{"comment":"The construction of the Hamilton path that activates G' relies on a 'standard multiple-exposure technique' that is not described or referenced; since this is an extension of the main witness, a brief derivation or a precise reference would be helpful.","section":"6.2"}],"recommendation":"major_revision","confidential_remarks":"The reader's report and the stress-test note accept the paper, but the first-moment issue in Lemma 5.11 appears to be a genuine gap. The example of a star activation of a 4-cycle shows that p^{|E(D)|} can be strictly smaller than the actual probability. If the authors can fix the counting argument (for example, by counting distinct edge labels or by proving that nice activation diagrams can be assumed to have no repeated labels), the paper would be a strong contribution. I recommend major revision so that this load-bearing point is addressed before publication; the rest of the paper, including the constructive 1-statement and the topological connection, appears sound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Top marks from me. This paper resolves the threshold exponent for the existence of a K3-activating spanning tree in G(n,p), proving p_{K3} = n^{-1/3-o(1)}. The breakthrough is a genuinely new bridge between weak saturation and topology: Lemma 1.4 states that if a spanning tree activates G, then the 2-dimensional clique complex X^(2)(G) is simply connected. The proof is short and convincing — run the activation backwards until the cycle contracts to a tree walk. This lemma both gives the lower bound for the exponent (via the known non-simple-connectivity threshold of Babson–Costa–Farber–Horak) and yields a new upper bound on simple connectivity, improving Kahle's bound from (3 ln n/n)^{1/3} to (1+ε)n^{-1/3}.\n\nThe 1-statement is constructive: for p ≥ (1+ε)n^{-1/3}, a diameter-4 tree activates w.h.p., using the giant components in common neighborhoods. The 0-statement for Theorem 1.3 is the heavy part, bounding activation of short cycles through the new activation-diagram counting. I didn't find a gap; the counting lemma (Lemma 5.10) is intricate but the double-counting and the walk-on-tree structural lemma check out. The local-to-global principle for activation processes is a nice adaptation of Gromov's, and the contradiction argument in Proposition 5.18 is sound.\n\nThe soft spots are proportionate. The lower bound for the exponent inherits the external topology theorem; that's valid use of a published theorem, though it does mean the central exponent is only as solid as that theorem. The paper is honest about its own barriers: the diameter bound n^{1/18-ε} and the constant gap — they only rule out p < (2^{-7/3}-ε)n^{-1/3} for bounded-diameter trees, and they suspect the true constant for activation may differ from their own upper bound. The Hamilton path and Linial–Meshulam sections are sketched, but they're clearly peripheral.\n\nWho should read it: anyone working on weak saturation, random graph thresholds, or random clique topology. It deserves a careful referee — the length and technical density mean a single referee would struggle. My recommendation: accept, with high confidence, and let the authors expand the peripheral proofs if the venue wants self-containment.","headline":"This paper resolves the Korándi–Sudakov threshold exponent for K3-activating trees, and the new topology–weak-saturation connection is the real deal.","tokens_in":41150,"tokens_out":2803,"would_cite":true,"duration_ms":31702,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C35","55U10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A topological bridge pins the tree-activation threshold at n^{-1/3}.","keywords":["bootstrap percolation","weak saturation","random graphs","clique complexes","simple connectivity","fundamental group","local-to-global principle"],"falsifier":"Construct, for some fixed ε>0 and p = $n^{{-1/3-ε}}$, an infinite family of instances with high probability in which a spanning tree activates G(n,p) while $X^{{(2)}}$(G) is not simply connected; this would refute Lemma 1.4. Alternatively, exhibit for p slightly below $n^{{-1/3}}$ a specific activating tree whose existence contradicts the topological non-simple-connectivity theorem, thereby exposing a gap in the cited lower bound.","tokens_in":40145,"feed_emoji":"🌳","tokens_out":1720,"duration_ms":20487,"temperature":0.7,"pith_summary":"The paper asks when a random graph contains a spanning tree that can 'activate' all of the graph's edges by repeated triangle completion. The authors establish that the critical probability for this property is sharply $n^{{-1/3-o(1)}}$: above (1+ε)$n^{{-1/3}}$ a suitable tree almost surely exists, and below $n^{{-1/3-ε}}$ almost surely none exists. The proof works by connecting activation processes to the fundamental group of the 2-dimensional clique complex, showing that an activating tree forces simple connectivity, and then using a local-to-global principle in the style of Gromov to rule out activation when the complex is not simply connected. This improves on the previous known bounds by a polynomial factor and also yields a sharpened upper bound on the threshold for simple connectivity of the clique complex itself.","feed_headline":"One tree organizes a random graph once p passes n^{-1/3}","feed_subtitle":"The paper nails the sharp threshold for triangle-saturating trees and improves the clique-complex connectivity bound.","key_machinery":"The central object is the 2-dimensional clique complex $X^{{(2)}}$(G) of the random graph, whose triangles are the triangles of G. The key identity is Lemma 1.4: if a spanning tree T activates G, then $X^{{(2)}}$(G) is simply connected. The new machinery for the 0-statement of Theorem 1.3 is a local-to-global principle for activation processes, inspired by Gromov's principle for hyperbolic groups. It formalizes the idea that if every short cycle can be activated quickly (with few vertices) and some short cycle cannot be activated fast, then no bounded-diameter tree can activate the whole graph. The counting backbone is the notion of an activation diagram, a compressed van Kampen-like diagram where each triangle appears at most once; counting such diagrams via pairs of trees and walks yields the probabilistic bounds that make the local-to-global argument work.","core_discovery":"The paper's central claim is that the threshold probability for the existence of a spanning tree that activates G(n,p) via K3-bootstrap percolation satisfies p_{K3} = $n^{{-1/3-o(1)}}$. Specifically, Theorem 1.2 states that for any ε>0: if p ≥ (1+ε)$n^{{-1/3}}$, then with high probability there exists a spanning tree T ⊆ G with T → G; while if p < $n^{{-1/3-ε}}$, then with high probability no spanning tree activates G. The 1-statement is proved constructively via a tree of diameter 4 built from a carefully chosen neighborhood structure. The 0-statement follows from combining the observation Lemma 1.4 (an activating tree implies the 2-dimensional clique complex is simply connected) with the known theorem that this complex is not simply connected w.h.p. for p ≤ $n^{{-1/3-ε}}$ (Theorem 1.5, due to Babson and to Costa-Farber-Horak). The paper also proves Theorem 1.3, an up-to-constant-factor threshold for trees of diameter at most $n^{{1/18-ε}}$, and derives Corollary 1.6 improving the known upper bound for simple connectivity of the clique complex to p ≥ (1+ε)$n^{{-1/3}}$.","pith_inferences":["The paper suggests that the 'true' threshold for the existence of any activating tree may be exactly n^{-1/3}, while the threshold for the existence of a triangulated filling for every cycle may be slightly higher (3/4^{4/3} · n^{-1/3}); the authors explicitly leave this gap open.","The activation-diagram counting technique could plausibly be extended to other graphs F beyond triangles, particularly cycles, where there is no known sharp threshold for weak saturation stability.","If the conjecture that any activating tree can be 'reduced' to a bounded-diameter tree holds, then the constant-factor gap in Theorem 1.3 would collapse and the full exponent threshold would persist for all trees, not just those of small diameter.","The paper's improvement of the simple-connectivity threshold may be a stepping stone toward a fully matching lower bound for the clique complex, since the two thresholds are conjecturally distinct."],"forward_implications":["The threshold for the existence of a K3-saturating tree in G(n,p) is now known to be n^{-1/3-o(1)}, settling a question of Korándi and Sudakov up to subpolynomial factors.","The same mechanism gives an improved upper bound on the threshold for simple connectivity of the 2-dimensional clique complex of G(n,p): w.h.p. it is simply connected whenever p ≥ (1+ε)n^{-1/3}.","For trees of diameter at most n^{1/18-ε}, the paper determines the activation threshold up to a constant factor, providing a sharp (in order) counterpart to the diameter-4 construction.","The local-to-global argument applies analogously to Linial-Meshulam random 2-complexes, where it yields an up-to-constant-factor activation threshold for bounded-diameter trees, complementing the known star case."],"supporting_citations":[{"why":"Supplies the prior bounds on p_{K3} that Theorem 1.2 improves, plus the baseline BFS-tree construction used in Section 3.","marker":"[13]"},{"why":"Provides the lower bound on simple connectivity of X^{(2)}(G_{n,p}) used to derive the 0-statement of Theorem 1.2.","marker":"[6]"},{"why":"Provides the lower bound on simple connectivity of X^{(2)}(G_{n,p}) used to derive the 0-statement of Theorem 1.2.","marker":"[21]"},{"why":"Gives the best previous upper bound on simple connectivity that Corollary 1.6 improves.","marker":"[39]"},{"why":"Supplies the polluted-environment bootstrap percolation result for fixed trees that the paper contrasts with its flexible-tree result.","marker":"[33]"},{"why":"Provides the giant-component tail bound used in the construction of the diameter-4 activating tree.","marker":"[55]"},{"why":"Supplies the rooted-extension counting theorem used in Claim 3.2 to activate edges between non-neighbors of the root.","marker":"[60]"},{"why":"Provides enumeration results for planar triangulations that motivate and are compared with the activation-diagram counting.","marker":"[12]"},{"why":"Provides enumeration results for planar triangulations that motivate and are compared with the activation-diagram counting.","marker":"[64]"}],"fun_headline_variants":["Sharp threshold for tree-activated random graphs: p ~ n^{-1/3}","Tree activates random graph precisely at p = n^{-1/3-o(1)}","Critical p for weak K3-saturation by a tree: n^{-1/3}","Random graph becomes tree-activatable at p = n^{-1/3-o(1)}","Topological proof pins tree activation threshold at n^{-1/3}"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire lower-bound exponent $n^{{-1/3-o(1)}}$ rests on the cited topological theorem that, for p ≤ $n^{{-1/3-ε}}$, the 2-dimensional clique complex of G(n,p) is not simply connected; the paper does not re-prove that theorem.","fun_headline_variants_meta":{"raw":{"variants":["Sharp threshold for tree-activated random graphs: p ~ n^{-1/3}","Tree activates random graph precisely at p = n^{-1/3-o(1)}","Critical p for weak K3-saturation by a tree: n^{-1/3}","Random graph becomes tree-activatable at p = n^{-1/3-o(1)}","Topological proof pins tree activation threshold at n^{-1/3}"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000977,"raw_usage":{"total_tokens":4278,"prompt_tokens":1199,"completion_tokens":3079,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":815,"completion_tokens_details":{"reasoning_tokens":2970}},"tokens_in":815,"tokens_out":3079,"duration_ms":23110,"temperature":1.0,"reasoning_tokens":2970,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:22:28.048427+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct, for some fixed ε>0 and p = $n^{{-1/3-ε}}$, an infinite family of instances with high probability in which a spanning tree activates G(n,p) while $X^{{(2)}}$(G) is not simply connected; this would refute Lemma 1.4. Alternatively, exhibit for p slightly below $n^{{-1/3}}$ a specific activating tree whose existence contradicts the topological non-simple-connectivity theorem, thereby exposing a gap in the cited lower bound.","supporting_citations":[{"cited_title":"Bidgoli, A","cited_arxiv_id":null,"evidence_quote":"Supplies the prior bounds on p_{K3} that Theorem 1.2 improves, plus the baseline BFS-tree construction used in Section 3."},{"cited_title":"Fundamental Groups of Random Clique Complexes","cited_arxiv_id":"1207.5028","evidence_quote":"Provides the lower bound on simple connectivity of X^{(2)}(G_{n,p}) used to derive the 0-statement of Theorem 1.2."},{"cited_title":"Costa, M","cited_arxiv_id":null,"evidence_quote":"Provides the lower bound on simple connectivity of X^{(2)}(G_{n,p}) used to derive the 0-statement of Theorem 1.2."},{"cited_title":"Kahle, Topology of random clique complexes , Discrete Math., 309:6 (2009) 1658–1671","cited_arxiv_id":null,"evidence_quote":"Gives the best previous upper bound on simple connectivity that Corollary 1.6 improves."},{"cited_title":"Gravner, B","cited_arxiv_id":null,"evidence_quote":"Supplies the polluted-environment bootstrap percolation result for fixed trees that the paper contrasts with its flexible-tree result."},{"cited_title":"O’Connell, Some large deviation results for sparse random graphs , Probab","cited_arxiv_id":null,"evidence_quote":"Provides the giant-component tail bound used in the construction of the diameter-4 activating tree."},{"cited_title":"Spencer, Counting extensions, Journal of Combinatorial Theory, Series A, 55:2 (1990) 247– 255","cited_arxiv_id":null,"evidence_quote":"Supplies the rooted-extension counting theorem used in Claim 3.2 to activate edges between non-neighbors of the root."},{"cited_title":"Bernardi, ´E","cited_arxiv_id":null,"evidence_quote":"Provides enumeration results for planar triangulations that motivate and are compared with the activation-diagram counting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides enumeration results for planar triangulations that motivate and are compared with the activation-diagram counting."}],"review_version":1}