Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

When does a tree activate the random graph?

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A topological bridge pins the tree-activation threshold at n^{-1/3}.

desk verdict This paper resolves the Korándi–Sudakov threshold exponent for K3-activating trees, and the new topology–weak-saturation connection is the real deal. read the letter →

arxiv 2507.05697 v1 pith:PBEU6A7E submitted 2025-07-08 math.CO math.ATmath.PR

Asaf Cohen Antonir , Yuval Peled , Asaf Shapira , Mykhaylo Tyomkyn , Maksim Zhukovskii This is my paper
classification math.COmath.ATmath.PR MSC 05C8005C3555U10
keywords bootstrappercolationweaksaturationrandomgraphscliquecomplexessimpleconnectivityfundamentalgrouplocal-to-globalprinciple
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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}}$.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

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.

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 (2)
  1. [5.2, Lemma 5.11] 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.
  2. [3, Claim 3.1] 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.
minor comments (4)
  1. [5.1, Definition 5.8] The word 'initialasing' in the first step of Definition 5.8 should be 'initialising'.
  2. [5.2, Lemma 5.12] The notation 'H G− →C' appears garbled; it should be 'H → C'.
  3. [5.4, proof of Theorem 1.3 part 2] 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.
  4. [6.2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central threshold proof is self-contained or rests on independent external results.

full rationale

The paper's main claim, Theorem 1.2, is derived without circular reasoning. The 1-statement is proved constructively in Section 3 by explicitly building a depth-2 tree that activates G when p >= (1+eps)n^{-1/3}. The 0-statement is obtained by contrapositive: Lemma 4.1 (proved in Section 4) shows that an activating spanning tree would force simple connectivity of X^(2)(G), and Theorem 1.5, a cited result of Babson, Costa, Farber, and Horak, supplies the independent fact that X^(2)(G) is not simply connected when p < n^{-1/3-eps}. That cited theorem is external to the present authors and is used in its stated range, so it is genuine evidence rather than a self-citation chain. The improved upper bound for Kahle's simple-connectivity threshold in Corollary 1.6 is a forward implication of the proved 1-statement, not an input. Theorem 1.3 is proved by internal first-moment counting of activation diagrams (Lemmas 5.10-5.13) and a local-to-global proposition (Proposition 5.18); no parameter is fitted to the claimed threshold and no 'prediction' is renamed from a fit. Self-citations such as [13] are used only as baselines that the paper improves upon, and [45] appears in the Linial-Meshulam analogue rather than in the main theorem. Thus no load-bearing step reduces, by definition or by self-citation, to its own inputs.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claim rests on standard concentration inequalities, two external random graph theorems (O'Connell, Spencer), and two external topology theorems (simple connectivity lower bounds for clique complexes and Linial-Meshulam complexes). These are all prior published results, not ad hoc postulates. The proof introduces internal definitions (activation diagrams, nice processes) that are derived and used within the paper, so they are not free parameters or invented entities.

assumptions (6)
  • domain assumption For p ≤ n^{-1/3-ε}, the 2-dimensional clique complex X^(2)(G_{n,p}) is not simply connected with high probability (Theorem 1.5).
    Cited from Babson [6] and Costa-Farber-Horak [21]; used in Section 4 with Lemma 1.4 to derive the 0-statement of Theorem 1.2.
  • domain assumption O'Connell's giant component theorem: for m p ≥ 1+ε, G(m,p) has a unique linear-size component with probability 1-exp(-Ω(m)) (Theorem 2.6).
    Used in Section 3 to guarantee a giant component in common neighbourhoods H(u) of size Θ(n^{1/3}).
  • domain assumption Spencer's theorem on strictly balanced rooted graph extensions (Theorem 2.7).
    Used in Claim 3.2 to guarantee a specific 6-vertex configuration appears with high probability.
  • standard math Chernoff bounds for binomial random variables (Claim 2.4, Claim 2.5).
    Standard concentration inequalities used throughout Section 3 and Appendices.
  • standard math Catalan-number enumeration: the number of triangulations of an (n+2)-gon is C_n, and the convolution identity for Catalan numbers (refs [12,19,64]).
    Used in Lemma 5.10 to bound the number of isomorphism types of activation diagrams.
  • domain assumption For Linial-Meshulam random 2-complexes, p < n^{-1/2-ε} implies not simply connected (Babson-Hoffman-Kahle, Theorem 6.3).
    Used in Section 6.1 for the analogue of Theorem 1.3 in Linial-Meshulam complexes.

how reviews work

0 comments
Cite this review

Pith. "Pith review of When does a tree activate the random graph?." pith.science (2026). https://pith.science/paper/PBEU6A7E

@misc{pith2026250705697,
  author       = {Pith},
  title        = {Pith review of: When does a tree activate the random graph?},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PBEU6A7E}},
  note         = {Machine review of arXiv:2507.05697}
}
abstract

Let $F$ and $G$ be two graphs. A spanning subgraph $H$ of $G$ is called weakly $F$-saturated if one can add to $H$ the edges of $G \setminus H$ in some order, so that whenever a new edge is added, a new copy of $F$ is formed. Obtaining lower bounds for the minimum size $\mathrm{wsat}(G,F)$ of such an $H$ is a classical problem in extremal combinatorics. In particular, in the past 40 years, various algebraic tools have been developed to prove lower bounds on the weak saturation number $\mathrm{wsat}(G,F)$. Our paper uncovers a new connection of weak saturation to topology of clique complexes, that allows to prove tight lower bounds in some cases when the algebraic tools are not efficient. It is easy to see that the smallest $K_3$-saturating graphs in $K_n$ are trees, thus $\mathrm{wsat}(K_n,K_3)=n-1$. In 2017, Kor\'andi and Sudakov proved that this is also the case in dense random graphs $G\sim G_{n,p}$, $p=\mathrm{const}\in(0,1)$, and posed the question of determining the smallest $p$ for which $G_{n,p}$ contains a $K_3$-saturating tree with high probability. Using the new topological connection, we show that this critical $p$ is of order $n^{-1/3-o(1)}$. Inspired by Gromov's local-to-global principle for hyperbolic groups, we further develop our topological approach and determine the critical probability up to a constant factor, for trees with diameter at most $n^{c}$, for some $c>0$. The new connection also enables us to improve the best known upper bound on the threshold probability for simple connectivity of the 2-dimensional clique complex of $G_{n,p}$, due to Kahle.

Figures

Figures reproduced from arXiv: 2507.05697 by the authors.

Figure 1
Figure 1. A Van-Kampen diagram for a closed walk, presented in red. [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Activation of the blue edge {u, w}. Red edges participate in the activation process. Black edges show the entire neighbourhood of u in N(v). Claim 3.2. W.h.p., for every pair of vertices u, u / ˜ ∈ N(v) ∪ {v}, there exist vertices w, w˜ in N(v) and a vertex x ∈ [n] \ N(v) such that the pairs {u, w}, {u, ˜ w˜}, {w, x}, {w, x ˜ }, {u, x}, {u, x ˜ } are adjacent in G. Proof. The assertion follows from Theorem 2.7 and t… view at source ↗
Figure 3
Figure 3. The graph present in Gn,p due to Claim 3.2 Let us complete the proof of the first part of Theorem 1.3. Let {u, u˜} be an edge of G in [n] \ (N(v)∪ {v}) that we want to activate and assume that the vertices w, w, x ˜ from the assertion of Claim 3.2 exist. Then the edge {u, u˜} can be activated in the following way: We may assume that the edges {u, w}, {u, ˜ w˜}, {x, w}, {x, ˜ w˜} are already activated. Then we may ac… view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Different types of diagrams 5 Proof of Theorem 1.3, part 2 In this section, we prove the second part of Theorem 1.3, which is done in the following four subsec￾tions. We start from a short sketch, disclosing the structure of this section. In Subsection 5.1, we count ac…
Figure 5
Figure 5. Figure 5: Three walks W1, W2, and W3, covering each edge of T3 once or twice, and E(F2) ∩ E(W3) are highlighted. Proof. Fix 1 ≤ i ≤ k−1. First, we prove that the graph H consisting of the edges of E(Fi)∩E(Wi+1) has maximum degree 2. Second, we show that H is connected, concludin…
Figure 6
Figure 6. Figure 6: An example of an activation scheme Let X be the set of all activation schemes. We claim that |Pv,w| ≤ |X|, and hence it suffices to bound |X|. Indeed, it is easy to map Pv,w into X injectively. First of all, for every labelled connected graph H, let TH be the canonical…
Figure 7
Figure 7. Figure 7: The rainbow triangles are preimages of ∆ [PITH_FULL_IMAGE:figures/full_fig_p028_7.png]
Figure 8
Figure 8. Figure 8: Replacing e with e ′ in the highlighted triangle ∆i . The desired sequence of nested processes is constructed. Since for every k ≥ 1, we have K(Ak−1) ⊋ K(Ak), and since K(A0) is a finite complex, the iterative process terminates. The resulting subpro￾cess of A is then …
Figure 9
Figure 9. Figure 9: The case |V (e ′ ∩ C)| = |V (e ′′ ∩ C)| = 2 e e ′′ e C1 ′ C2 [PITH_FULL_IMAGE:figures/full_fig_p031_9.png]
Figure 11
Figure 11. Figure 11: The three cycles C1, C2, and ∆s which admit fast activation processes 6 Concluding remarks In this section, we discuss several generalisations of our result as well as remaining challenges. First, in Section 6.1, we show that our method is robust enough to tackle a si…

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Weak saturation numbers of large complete bipartite graphs

    math.CO 2025-08 accept novelty 6.0 of 10

    Exact weak saturation number of K_{s,t} is found on s+t+1 vertices when gcd(s,t)=1, and new bounds are given for up to s+t+j vertices.

Reference graph

Works this paper leans on

67 extracted references · 65 canonical work pages · cited by 1 Pith paper

  1. [1]

    Adler, U

    J. Adler, U. Lev, Bootstrap percolation: visualizations and applications , Braz. J. Phys., 33 (2003) 641–644

    work page 2003

  2. [2]

    Aizenman, J.L

    M. Aizenman, J.L. Lebowitz, Metastability effects in bootstrap percolation , J. Phys. A, 21:19 (1988) 3801–3813

    work page 1988

  3. [3]

    Ajtai, J

    M. Ajtai, J. Koml´ os, E. Szemer´ edi,The first occurrence of Hamilton cycles in random graphs , Annals of Discrete Mathematics 27 (1985) 173–178

    work page 1985

  4. [4]

    Alon, An extremal problem for sets with applications to graph theory , Journal of Combina- torial Theory, Series A, 40 (1985) 82–89

    N. Alon, An extremal problem for sets with applications to graph theory , Journal of Combina- torial Theory, Series A, 40 (1985) 82–89

    work page 1985

  5. [5]

    Ascoli, X

    R. Ascoli, X. He, Rational values of the weak saturation limit , arXiv preprint (2025) arXiv:2501.15686

    arXiv 2025

  6. [6]

    Fundamental Groups of Random Clique Complexes

    E. Babson, Fundamental groups of random clique complexes , arXiv preprint (2012) arXiv:1207.5028

    work page Pith review arXiv 2012

  7. [7]

    Babson, C

    E. Babson, C. Hoffman, M. Kahle, The fundamental group of random 2-complexes , Journal of the American Mathematical Society, 24:1 (2011) 1–28. 37

    work page 2011

  8. [8]

    Balogh, B

    J. Balogh, B. Bollob´ as, R. Morris, O. Riordan,Linear algebra and bootstrap percolation, Journal of Combinatorial Theory, Series A, 119: (2012) 1328–1335

    work page 2012

Show all 67 references
  1. [9]

    Balogh, B

    J. Balogh, B. Bollob´ as, R. Morris, Graph bootstrap percolation, Random Structures & Algo- rithms, 41:4 (2012) 413–440

    2012

  2. [10]

    Baron, J

    J.D. Baron, J. Kahn, On the cycle space of a random graph , Random Structures & Algorithms, 54:1 (2019) 39–68

    2019

  3. [11]

    Bartha, B

    Z. Bartha, B. Kolesnik, Weakly saturated random graphs , Random Structures & Algorithms, 65:1 (2024) 131–148

    2024

  4. [12]

    Bernardi, ´E

    O. Bernardi, ´E. Fusy, A bijection for triangulations, quadrangulations, pentagulations, etc. Journal of Combinatorial Theory, Series A, 119:1 (2012) 218–244

    2012

  5. [13]

    Bidgoli, A

    M. Bidgoli, A. Mohammadian, B. Tayfeh-Rezaie, M. Zhukovskii, Threshold for stability of weak saturation, Journal of Graph Theory, 106:3 (2024) 474–495

    2024

  6. [14]

    Bollob´ as,Random graphs, second edition, Cambridge University Press, 2001

    B. Bollob´ as,Random graphs, second edition, Cambridge University Press, 2001

    2001

  7. [15]

    Bollob´ as, The evolution of sparse graphs , Graph theory and combinatorics (Cambridge, 1983), Academic Press, London, (1984) 35–57

    B. Bollob´ as, The evolution of sparse graphs , Graph theory and combinatorics (Cambridge, 1983), Academic Press, London, (1984) 35–57

    1984

  8. [16]

    Bollob´ as,Weakly k-saturated graphs, Beitr¨ age zur Graphentheorie (Kolloquium, Manebach, 1967), Teubner, Leipzig (1968) 25–31

    B. Bollob´ as,Weakly k-saturated graphs, Beitr¨ age zur Graphentheorie (Kolloquium, Manebach, 1967), Teubner, Leipzig (1968) 25–31

    1968

  9. [17]

    Brightwell, K

    G. Brightwell, K. Panagiotou, A. Steger, Extremal subgraphs of random graphs, Random Struc- tures & Algorithms, 41 (2012) 147–178

    2012

  10. [18]

    Bulavka, M

    D. Bulavka, M. Tancer, M. Tyomkyn, Weak saturation of multipartite hypergraphs , Combina- torica, 43 (2023) 1081–1102

    2023

  11. [19]

    M. E. Catalan, Sur les nombres de Segner , Rendiconti del Circolo Matematico di Palermo, 1:1 (1887) 190–201

  12. [20]

    Conlon, W

    D. Conlon, W. T. Gowers, Combinatorial theorems in sparse random sets , Annals of Mathe- matics, 184 (2016) 367–454

    2016

  13. [21]

    Costa, M

    A. Costa, M. Farber, D. Horak, Fundamental groups of clique complexes of random graphs , Transactions of the London Mathematical Society 2:1 (2015) 1–32

    2015

  14. [22]

    B. L. Currie, J. R. Faudree, R. J. Faudree, J. R. Schmitt, A survey of minimum saturated graphs, The Electronic Journal of Combinatorics, in Dynamic Surveys, Second Edition (2021) #DS19

    2021

  15. [23]

    DeMarco, A

    B. DeMarco, A. Hamm, J. Kahn, On the triangle space of a random graph , arXiv preprint arXiv:1207.6717 (2012)

    2012 arXiv

  16. [24]

    DeMarco, J

    B. DeMarco, J. Kahn, Mantel’s theorem for random graphs, Random Structures & Algorithms, 47 (2015) 59–72

    2015

  17. [25]

    Dubroff, J

    Q. Dubroff, J. Kahn, On the H-space of a random graph , arXiv preprint arXiv:2410.06421 (2024). 38

    2024 arXiv

  18. [26]

    Erd˝ os, Z

    P. Erd˝ os, Z. F¨ uredi, Z. Tuza,Saturated r-uniform hypergraphs, Discrete Mathematics, 98:2 (1991) 95–104

    1991

  19. [27]

    Faudree, R.J

    R.J. Faudree, R.J. Gould, M.S. Jacobson, Weak saturation numbers of sparse random graphs , Discussiones Mathematicae. Graph Theory, 33 (2013) 677–693

    2013

  20. [28]

    Fontes, R.H

    L.R. Fontes, R.H. Schonmann, V. Sidoravicius, Stretched exponential fixation in stochastic Ising models at zero temperature, Comm. Math. Phys. 228 (2002) 495–518

    2002

  21. [29]

    Frankl, An extremal problem for two families of sets, European J

    P. Frankl, An extremal problem for two families of sets, European J. Combin. 3 (1982) 125–127

    1982

  22. [30]

    Frieze, M

    A. Frieze, M. Karo´ nski, Introduction to random graphs , Cambridge University Press (2015)

    2015

  23. [31]

    Gravner, A.E

    J. Gravner, A.E. Holroyd, Polluted bootstrap percolation with threshold two in all dimensions , Probability Theory and Related Fields, 175 (2019) 467–486

    2019

  24. [32]

    Gravner, A.E

    J. Gravner, A.E. Holroyd, D. Sivakoff, Polluted bootstrap percolation in three dimensions, The Annals of Applied Probability, 31:1 (2021) 218–246

    2021

  25. [33]

    Gravner, B

    J. Gravner, B. Kolesnik, Transitive closure in a polluted environment , Ann. Appl. Probab., 33:1 (2023) 107–126

    2023

  26. [34]

    Gravner, E

    J. Gravner, E. McDonald, Bootstrap percolation in a polluted environment , J. Stat. Phys., 87 (1997) 915–927

    1997

  27. [35]

    Gromov, Hyperbolic groups, in Essays in group theory, ed

    M. Gromov, Hyperbolic groups, in Essays in group theory, ed. S. M. Gersten, Springer (1987) 75–265

    1987

  28. [36]

    Hoshen, W

    I. Hoshen, W. Samotij, Simonovits’s theorem in random graphs , arXiv preprint (2023) arXiv:2308.13455

    2023 arXiv

  29. [37]

    Hoshen, W

    I. Hoshen, W. Samotij, M. Zhukovskii, Stability of large cuts in random graphs , arXiv prerpint (2024) arXiv:2402.14620

    2024 arXiv

  30. [38]

    Janson, T

    S. Janson, T. Luczak, A. Ruci´ nski,Random Graphs, J. Wiley & Sons, 2000

    2000

  31. [39]

    Kahle, Topology of random clique complexes , Discrete Math., 309:6 (2009) 1658–1671

    M. Kahle, Topology of random clique complexes , Discrete Math., 309:6 (2009) 1658–1671

    2009

  32. [40]

    Kalai, Hyperconnectivity of graphs, Graphs Combin., 1 (1985) 65–79

    G. Kalai, Hyperconnectivity of graphs, Graphs Combin., 1 (1985) 65–79

    1985

  33. [41]

    Kalai, Weakly saturated graphs are rigid, in: Convexity and graph theory (Jerusalem, 1981), North-Holland Math

    G. Kalai, Weakly saturated graphs are rigid, in: Convexity and graph theory (Jerusalem, 1981), North-Holland Math. Stud., 87, Ann. Discrete Math., 20, North-Holland, Amsterdam (1984) 189–190

    1984

  34. [42]

    Kalinichenko, M

    O. Kalinichenko, M. Miralaei, A. Mohammadian, B. Tayfeh-Rezaie, Weak saturation numbers in random graphs , arXiv preprint (2023) arXiv:2306.10375

    2023 arXiv

  35. [43]

    Kalinichenko, M

    O. Kalinichenko, M. Zhukovskii, Weak saturation stability, European Journal of Combinatorics, 114 (2023) 103777

    2023

  36. [44]

    Koml´ os, E

    J. Koml´ os, E. Szemer´ edi,Limit distributions for the existence of Hamilton circuits in a random graph, Discrete Mathematics 43 (1983) 55–63. 39

    1983

  37. [45]

    Kor´ andi, Y

    D. Kor´ andi, Y. Peled, B. Sudakov,A random triadic process, SIAM Journal on Discrete Math- ematics, 30:1 (2016) 1–19

    2016

  38. [46]

    Kor´ andi, B

    D. Kor´ andi, B. Sudakov,Saturation in random graphs, Random Structures & Algorithms, 51:1 (2017) 169–181

    2017

  39. [47]

    A. D. Korshunov, Solution of a problem of Erd˝ os and R´ enyi on hamiltonian cycles in nonori- ented graphs, Soviet Math. Doklady 17 (1976) 760–764

    1976

  40. [48]

    Krivelevich, G

    M. Krivelevich, G. Kronenberg, A. Mond, Tur´ an-type problems for long cycles in random and pseudo-random graphs, Journal of the London Mathematical Society, 107 (2023) 1519–1551

    2023

  41. [49]

    Kronenberg, T

    G. Kronenberg, T. Martins, N. Morrison, Weak saturation numbers of complete bipartite graphs in the clique , Journal of Combinatorial Theory, Series A, 178 (2021) 105357

    2021

  42. [50]

    Morris, Bootstrap percolation, and other automata, European Journal of Combinatorics, 66 (2017) 250–263

    R. Morris, Bootstrap percolation, and other automata, European Journal of Combinatorics, 66 (2017) 250–263

    2017

  43. [51]

    Morris, Zero-temperature Glauber dynamics on Zd, Probab

    R. Morris, Zero-temperature Glauber dynamics on Zd, Probab. Theory Related Fields, 149 (2011) 417–434

    2011

  44. [52]

    Morrison, J

    N. Morrison, J. A. Noel, Extremal bounds for bootstrap percolation in the hypercube, Journal of Combinatorial Theory, Series A, 156 (2018) 61–84

    2018

  45. [53]

    Morrison, J

    N. Morrison, J. A. Noel, A. Scott, Saturation in the hypercube and bootstrap percolation, Com- binatorics, Probability & Computing, 26 (2017) 78–98

    2017

  46. [54]

    Moshkovitz, A

    G. Moshkovitz, A. Shapira, Exact bounds for some hypergraph saturation problems , Journal of Combinatorial Theory, Series B, 111 (2015) 242–248

    2015

  47. [55]

    O’Connell, Some large deviation results for sparse random graphs , Probab

    N. O’Connell, Some large deviation results for sparse random graphs , Probab. Theory Relat. Fields, 110 (1998) 277–285

    1998

  48. [56]

    Pikhurko, Extremal hypergraphs, PhD thesis, University of Cambridge, 1999

    O. Pikhurko, Extremal hypergraphs, PhD thesis, University of Cambridge, 1999

    1999

  49. [57]

    Pikhurko, Weakly saturated hypergraphs and exterior algebra , Combin

    O. Pikhurko, Weakly saturated hypergraphs and exterior algebra , Combin. Probab. Comput., 10:5 (2001) 435–451

    2001

  50. [58]

    Schacht, Extremal results for random discrete structures , Annals of Mathematics, 184:2 (2016) 333–365

    M. Schacht, Extremal results for random discrete structures , Annals of Mathematics, 184:2 (2016) 333–365

    2016

  51. [59]

    Shapira, M

    A. Shapira, M. Tyomkyn, Weakly saturated hypergraphs and a conjecture of Tuza, Proceedings of the American Mathematical Society, 151 (2023) 2795–2805

    2023

  52. [60]

    Spencer, Counting extensions, Journal of Combinatorial Theory, Series A, 55:2 (1990) 247– 255

    J. Spencer, Counting extensions, Journal of Combinatorial Theory, Series A, 55:2 (1990) 247– 255

    1990

  53. [61]

    Terekhov, A short proof of Tuza’s conjecture for weak saturation in hypergraphs , arXiv preprint (2025) arXiv:2504.03816

    N. Terekhov, A short proof of Tuza’s conjecture for weak saturation in hypergraphs , arXiv preprint (2025) arXiv:2504.03816

    2025 arXiv

  54. [62]

    Terekhov, M

    N. Terekhov, M. Zhukovskii, Weak saturation in graphs: a combinatorial approach , Journal of Combinatorial Theory, Series B, 172 (2025) 146–167. 40

    2025

  55. [63]

    Terekhov, M

    N. Terekhov, M. Zhukovskii, Weak saturation rank: a failure of linear algebraic approach to weak saturation, arXiv preprint (2024) arXiv:2405.17857

    2024 arXiv

  56. [64]

    W. T. Tutte, A census of planar triangulations , Canad. J. Math 14:1 (1962) 21–38

    1962

  57. [65]

    von Neumann, Theory of Self-Reproducing Automata , Univ

    J. von Neumann, Theory of Self-Reproducing Automata , Univ. Illinois Press, Urbana, 1966

    1966

  58. [66]

    Tuza, Asymptotic growth of sparse saturated structures is locally determined, Discrete Math- ematics, 108:1-3 (1992) 397–402

    Z. Tuza, Asymptotic growth of sparse saturated structures is locally determined, Discrete Math- ematics, 108:1-3 (1992) 397–402

    1992

  59. [67]

    Ulam, Random processes and transformations, Proc

    S. Ulam, Random processes and transformations, Proc. Internat. Congr. Math. (1950) 264–275. A Proofs of Lemma 6.4 and Lemma 6.5 Here we prove both Lemma 6.4 and Lemma 6.5. Let us start with the following analogue of Lemma (5.11). Lemma A.1. Suppose that 3 ≤ ℓ = ℓ(n), v = v(n),...

    1950

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.