Pith. sign in

REVIEW 2 major objections 4 minor 41 references

Slow graph bootstrap percolation III: Chain constructions

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 ↗ Review JSON

Pith's one-line read Nearly every graph H makes its bootstrap percolation process run for a quadratic number of steps.

desk verdict A genuinely general chain framework that settles when maximum running times are quadratic for many graphs; the only load-bearing risk is the new Ruzsa-type set construction behind the dense bipartite lower bounds. read the letter →

arxiv 2508.03835 v1 pith:ICIYY5ZQ submitted 2025-08-05 math.CO

David Fabian , Patrick Morris , Tibor Szabó This is my paper · ORCID
classification math.CO MSC 05C8005C3505D40
keywords graphbootstrappercolationmaximumrunningtimechainconstructionsrandomgraphsadditivecombinatoricsRuzsa-Szemerédi(63)-theoreminseparablequadratic
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

This paper establishes that slow, quadratic maximum running times in graph bootstrap percolation are abundant, not a quirk of large cliques. It develops a general framework of chain constructions—sequences of overlapping copies of a fixed graph H that force an H-process to add one new edge per step—and applies it to random graphs, dense graphs, wheels, complete bipartite graphs, and inseparable graphs. In particular, a random k-vertex graph H = G(k,p) has M_H(n) = Ω(n²) once p = ω(log k/k), while below that threshold the running time is O(1); for any (⌈k/2⌉,1)-inseparable graph, M_H(n) = Ω(n²). Upper bounds, including the odd wheel's narrow subquadratic window M_{W_k}(n) = $n^{{2-o(1)}}$ and o(n²), connect the theory to extremal problems such as the Ruzsa–Szemerédi (6,3)-theorem.

What carries the argument

The central object is the proper H-chain, a sequence of copies of H where consecutive copies meet at exactly one edge and no stray copy of H−e appears where it could shortcut the process; Lemma 4.6 turns a proper chain of length τ into a starting graph with running time at least τ. A linking lemma (Lemma 5.5) concatenates many short chains into one long chain. Three concrete chain families implement the machinery: ladder chains (copies placed with slopes across two long vertex sequences), dilation chains (vertex indices multiplied by elements of a modulo-p solution-free set, in non-bipartite and bipartite variants), and line chains (chains laid on edges of a high-girth linear hypergraph). The additive ingredient is a family of solution-free sets—Behrend-type sets for almost-quadratic bounds, and a new Ruzsa-type four-variable construction (Theorem 7.3) for the $n^{{3/2-o(1)}}$ bipartite bounds.

What would settle it

Take a k-vertex graph H with δ(H) > 3k/4, such as the 5th power of a 40-cycle, build the ladder-chain starting graph from Section 6, and simulate the H-process for n around $10^{4}$; if the process stabilises in fewer than c·n² steps for an absolute constant c, then Theorem 6.6 fails. Alternatively, for a fixed prime p ≈ $10^{3}$, attempt to explicitly construct the solution-free set promised by Theorem 7.3; a failure there would signal a gap in the additive lemma behind the bipartite bounds.

Watch

Extended reading notes

Core claim

The paper argues that the maximum running time M_H(n) of H-bootstrap percolation—the longest an H-process on n vertices can keep adding one edge per step—is quadratic for many more graphs than previously believed. Its central results: for random H = G(k,p), M_H(n) = Ω(n²) with high probability as soon as p = ω(log k/k), while below that threshold M_H(n) = O(1); for any k-vertex (⌈k/2⌉,1)-inseparable graph, M_H(n) = Ω(n²); for dense bipartite H with both sides' degrees above half, M_H(n) ≥ $n^{{3/2-o(1)}}$; and the odd wheel W_k gives a genuine intermediate regime M_{W_k}(n) = $n^{{2-o(1)}}$ and M_{W_k}(n) = o(n²). The framework also yields superlinear bounds ($n^{{1+2/(3k-2)}}$) for all inseparable graphs and connects the upper bounds to extremal problems such as the Ruzsa–Szemerédi (6,3)-theorem.

Load-bearing premise

The $n^{{3/2-o(1)}}$ lower bounds for dense bipartite graphs rest on Theorem 7.3, a new additive-combinatorics construction of large sets avoiding non-trivial solutions to certain four-variable equations; the authors note they could not recover an earlier claimed K-fold Sidon construction and adapted Ruzsa's method instead, so if that adaptation contains a hidden gap, the bipartite bounds would not follow.

Editorial extensions

If this is right

  • Random graphs: for H = G(k,p), the maximum running time switches from O(1) to Ω(n²) at the connectivity threshold log k/k, so almost all graphs have quadratic maximum running time even when their average degree is near-logarithmic.
  • Quadratic running time is guaranteed for every k-vertex graph that cannot be disconnected by deleting any one edge plus up to ⌈k/2⌉ of its vertices—in particular, for all graphs with minimum degree greater than 3k/4, generalising the known clique lower bounds.
  • The odd wheel W_k is the first example with both M_{W_k}(n) = n^{2-o(1)} and M_{W_k}(n) = o(n²), showing the almost-quadratic window is a real phenomenon and leaving the exact status of K_5 as a sharp open question.
  • Dense bipartite graphs have running time at least n^{3/2-o(1)}, and complete bipartite graphs K_{r,s} interpolate between this and the n^{2-1/r} upper bound; the cube graph Q_3 matches the best known extremal-number bounds up to a polynomial factor.
  • Every (2,1)-inseparable graph—one that survives deletion of any edge and two vertices—has superlinear maximum running time n^{1+2/(3k-2)}.

Reading between the lines

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

  • If the additive construction in Theorem 7.3 can be replaced by a genuine K-fold Sidon set construction, the bipartite lower bounds would likely approach the n^{2-1/r} upper bound much more closely; the parity-and-shift devices in Construction 7.9 are a workaround for a missing result in additive combinatorics.
  • The wheel's upper bound via the (6,3)-theorem hints that upper bounds for graphs with a Behrendian obstruction may generally be governed by induced-matching-type extremal problems; extending that link could give new upper bounds for other graphs H.
  • For random H with p = c log k/k for a fixed c > 1, the paper's proof should probably extend to give Ω(n²), while the range log k/(2k) < p < log k/k may admit intermediate exponents—a concrete computational target for small k.
  • The umbrella of proper chains suggests that the list of possible running times—constant, logarithmic, linear, n^{3/2-o(1)}, n^{2-o(1)}, and quadratic—is not yet complete; the framework may produce new exponents for other graph classes.
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 develops a general framework of chain constructions for lower bounds on the maximum H-bootstrap percolation running time M_H(n), and applies it to a wide range of graphs H. The main results include: a phase transition for H = G(k,p) around p = log k/k, with M_H(n) = O(1) below threshold and M_H(n) = Ω(n^2) above it; quadratic running times for all (⌈k/2⌉,1)-inseparable k-vertex graphs; almost quadratic running times for dense graphs and graphs containing the square of a Hamilton cycle; subquadratic upper and lower bounds for odd wheels; n^{3/2-o(1)} lower bounds for dense bipartite graphs; improved exponents for complete bipartite graphs; and superlinear lower bounds for all (2,1)-inseparable and (1,1,1)-inseparable graphs. Upper bounds are also proved, connecting M_H(n) to extremal numbers and to the Ruzsa-Szemerédi (6,3)-theorem.

Significance. If the results are correct, the paper substantially advances the field: it shows that quadratic maximum running times are abundant rather than clique-specific, establishes a sharp random-graph phase transition, and provides a unifying toolbox (proper chains, linking lemmas, ladder/dilation/line chains) that recovers and extends earlier constructions for cliques. The paper is honest about its one delicate point: the authors state in Section 7.1 that they could not recover an earlier claimed K-fold Sidon construction and instead prove an original adaptation (Theorem 7.3). The headline results, in particular Theorems 1.1, 1.2 and 6.6, do not depend on that additive construction, which is an important structural strength of the paper.

major comments (2)
  1. [Appendix A, Lemma A.7] The inequality bounding |E*(b^(1), b^(2), b^(3), b^(4))| is not justified as written. For E*(x1,x2,x3,x4) = γ1x1 + γ2x2 + x3 − (γ1+γ2+1)x4, the sum of the absolute values of the coefficients is 2(γ1+γ2+1), so with only the stated bound γi ≤ k2 one obtains |E*(...)| ≤ 2(γ1+γ2+1)q ≤ (4k2+2)q. Since q is allowed to be as large as d/(4k2), this does not imply the claimed (2k2+1)q < d. This step is the one that converts a solution modulo d into an integer solution of an equation in E+, so Lemma A.7, and hence Theorem 7.3 and Theorem 1.8, rest on a statement that currently lacks a valid proof. The argument can likely be repaired by exploiting the parity and range restrictions on the αi to get stronger bounds on γ1 and γ2, or by choosing q slightly smaller, but the proof must be corrected. Given the authors' own remark in Section 7.1 that they could not recover the previously claimed K-fold Sidon construction, this point needs explicit verification.
  2. [Section 5, Lemma 5.5] The vertex count in the proof of Lemma 5.5 is incorrect: the linking procedure adds (s−1)(2k(k−2)−2) new vertices, not (τ−1)(2k(k−2)−2). The displayed inequality n + (τ−1)(2k(k−2)−2) ≤ 2k^2 n does not follow from τ ≤ n, and the proof does not state or use any bound on s = |A|. Since this lemma is used in every construction to turn a collection of chains into one proper chain on O(n) vertices, the statement needs to be repaired, for example by adding the assumption s ≤ n (which holds in all applications) and adjusting the constant, or by giving a separate bound on the number of chains.
minor comments (4)
  1. [Section 6.3] In the proof of Theorem 1.11, with m = ⌊n/150⌋ and |V| = 30m + 2, the assertion that 128|V| ≤ n is false (128·30m ≈ 25.6n). The Ω(n^{3/2}) lower bound is not affected because one can take m = cn for a sufficiently small absolute constant c, but the numerical inequality should be corrected.
  2. [Section 8, Theorem 8.3] The statement of Theorem 8.3 gives no lower bound on |E(L)|, but the proof of Theorem 8.4 uses |E(L)| ≥ N/2^{2g} to obtain the claimed chain length. The statement should include that lower bound, which follows from the cited construction, or the proof of Theorem 8.4 should be adjusted accordingly.
  3. [Section 7.6, equations (7.10)-(7.11)] In the sparsification argument for Theorem 1.9, the bound in (7.10) is for a fixed t, while (7.11) sums over roughly s values of t. The factor 1/(4r) should be replaced by 1/(4s), or the exponential decay of 2^{-r(s-1)} should be used explicitly, in order to justify the displayed lower bound on E|A'_q|.
  4. [Section 4, Lemma 4.6 proof] In the proof of Lemma 4.6, the references to 'property (1) of Definition 4.1' and 'property (2) of Definition 4.1' should refer to Definition 4.4, since the conditions used are the two conditions in the definition of a proper chain.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: lower bounds are constructed from external additive-combinatorial and extremal inputs, and self-citations are not load-bearing.

full rationale

The paper's derivation chain is self-contained against external benchmarks. Lower bounds in Theorems 1.1, 1.2, 1.4, 1.5, 1.8, 1.9, 1.11, 6.6, 7.8, 7.13 and 8.4 are obtained by constructing chains (Constructions 6.1, 7.4, 7.9 and 8.1), proving them proper via lemmas that verify containment of H-e copies, and then applying the internal Lemma 4.6. The additive ingredients are external: Behrend's construction (Lemma A.4), Singer Sidon sets (used in the proof of Theorem 1.11), Ruzsa's method (Appendix A), and Kővári-Sós-Turán or Ruzsa-Szemerédi for upper bounds. The only place where the paper flags an unverified prior construction is Section 7.1, where the authors explicitly say they could not recover a claimed K-fold Sidon construction and therefore prove Theorem 7.3 themselves by adapting Ruzsa; that is a possible correctness risk, not circularity, since no conclusion is assumed as an input. Self-citations to the authors' earlier papers [16] and [17] supply previously published lemmas (e.g., Observation 2.1, Lemma 9.3 and the H'_k example) that are used as black boxes and do not assume the theorems being proven here. No equation is defined in terms of the quantity it predicts, and no fitted parameter is renamed as a prediction.

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

All loads come from standard extremal and additive combinatorics results and from the paper's own new definitions. No free parameters are fitted to data and no new physical or combinatorial entities are postulated.

assumptions (8)
  • standard math Chernoff concentration inequalities for sums of independent Bernoulli variables.
    Used in Lemma 3.21 and elsewhere to control random graph degrees and edge counts.
  • domain assumption Behrend's construction gives subsets of [N] of size N^(1-o(1)) free of 3-term arithmetic progressions.
    Used through Corollary A.5 and Theorem 7.2 to produce large (K,3)-fold solution-free sets.
  • domain assumption Ruzsa-Szemeredi (6,3)-theorem: any n-vertex 3-uniform hypergraph with no 6 vertices spanning 3 or more edges has o(n^2) edges.
    Load-bearing for the wheel upper bound in Theorem 1.5, Section 9.2.
  • domain assumption Singer's construction gives Sidon sets of size N^(1/2)(1+o(1)) in [N].
    Used in the cube lower bound in Section 6.3.
  • domain assumption Lazebnik-Ustimenko-Woldar construction of L-uniform hypergraphs with N vertices, N edges, and girth g with L = Omega(N^(2/(3g-5))).
    Used in line chains, Theorem 8.3 and Theorem 8.4.
  • domain assumption Kovari-Sos-Turan theorem: ex(n,K_{r,s}) = O(n^(2-1/r)).
    Used to obtain the upper bound for bipartite H in Corollary 1.7.
  • domain assumption Kim-Sudakov-Vu asymmetry of random graphs: for min{p,1-p} = omega(log k/k), a.a.s. every nontrivial permutation has symmetric difference larger than 2.
    Used in Fact 3.20 to prove self-stability of G(k,p).
  • domain assumption Erdos-Simonovits bound ex(n,Q3) = O(n^(8/5)).
    Used in the upper bound of Theorem 1.11 for the cube graph.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Slow graph bootstrap percolation III: Chain constructions." pith.science (2026). https://pith.science/paper/ICIYY5ZQ

@misc{pith2026250803835,
  author       = {Pith},
  title        = {Pith review of: Slow graph bootstrap percolation III: Chain constructions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ICIYY5ZQ}},
  note         = {Machine review of arXiv:2508.03835}
}
abstract

For graphs $H$, we study the extremal function $M_H(n)$ which is the maximum running time (until stabilisation) of an $H$-bootstrap percolation process on $n$ vertices. Building on previous work in the clique case $H=K_k$, we develop a general framework of chain constructions. We demonstrate the flexibility of this framework by applying several variations of the method to give lower bounds on $M_H(n)$ for a wide variety of different graphs $H$ including dense graphs, random graphs and complete bipartite graphs. In particular, we focus on the question of whether $M_H(n)$ is (almost) quadratic or not and our lower bounds develop connections with additive combinatorics, utilising constructions of sets free of solutions to certain linear equations. Finally, our lower bounds are complemented by upper bounds which connect $M_H(n)$ to other problems in extremal graph theory such as the Ruzsa-Szemer\'edi (6,3)-Theorem.

Figures

Figures reproduced from arXiv: 2508.03835 by the authors.

Figure 1
Figure 1. An illustration of the graph H′ 7 . Example 1.3. Let k ≥ 3 and H′ k be the (2k − 2)-vertex graph composed by ‘gluing together’ two cliques of size k along a singular edge e and adding one more edge e ′ between two non-adjacent vertices. (An illustration of H′ 7 is given in [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. A simple K4-chain. Remark 4.3. Note that the definition of a simple chain requires H to have an ordering on its vertices and different orderings of V (H) may produce different chains. The existence of a pair of 2When the graph H is clear from context, we will simply refer to a chain [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗
Figure 3
Figure 3. The graph F = Q − 3 . y4 ∈ R. So we have that {x1, x2, y1, y2} = Lj for some j ∈ {0, . . . , 5m − 1}. Considering that each vertex in Z := {x3, x4, y3, y4} ⊂ R has a neighbour in Lj and the vertices in Z form a path in G, the neighbourhood condition (6.4) leads us to conclude that there must be some j ′ ∈ {0, . . . , 5m − 1} with Z = Rj ′. So we have that V (F) = Lj∪Rj ′ and by Lemma 6.5, we must in fact have that j… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 37 canonical work pages

  1. [1]

    Balogh, B

    J. Balogh, B. Bollob´ as, and R. Morris,Graph bootstrap percolation, Random Structures & Algorithms 41 (2012), no. 4, 413–440. ↑ 1

    work page 2012

  2. [2]

    Balogh, B

    J. Balogh, B. Bollob´ as, R. Morris, and O. Riordan, Linear algebra and bootstrap percolation , Journal of Combi- natorial Theory, Series A 119 (2012), no. 6, 1328–1335. ↑1

    work page 2012

  3. [3]

    Balogh, G

    J. Balogh, G. Kronenberg, A. Pokrovskiy, and T. Szab´ o,The maximum length of Kr-Bootstrap Percolation, arXiv preprint arXiv:1907.04559 (2019), To appear in Proceedings of the American Mathematical Society. ↑1.1, 1.3, 1.3, 1.4, 1.7, 3.2, 4, 5, 6, 7, 10.4

    arXiv 2019

  4. [4]

    Bartha and B

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

    work page 2024

  5. [5]

    F. A Behrend, On sets of integers which contain no three terms in arithmeti cal progression, Proceedings of the National Academy of Sciences of the United States of America 32 (1946), no. 12, 331. ↑1.1, 2.3, A, A.4

    work page 1946

  6. [6]

    F Bloom and O

    T. F Bloom and O. Sisask, An improvement to the Kelley-Meka bounds on three-term arit hmetic progressions, arXiv preprint arXiv:2309.02353 (2023). ↑2.3

    arXiv 2023

  7. [7]

    Bollob´ as, M

    B. Bollob´ as, M. Przykucki, O. Riordan, and J. Sahasrabudhe, On the maximum running time in graph bootstrap percolation, Electronic Journal of Combinatorics 24 (2017), no. 2, P2.16. ↑1.1, 1.4, 1.7, 4, 10.4

    work page 2017

  8. [8]

    Bollob´ as,Weakly k-saturated graphs, Beitr¨ age zur Graphentheorie (Kolloquium, Manebach, 1967), 1968, pp

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

    work page 1967

Show all 41 references
  1. [9]

    Bollob´ as,Random Graphs, 2nd ed., Cambridge University Press, 2001

    B. Bollob´ as,Random Graphs, 2nd ed., Cambridge University Press, 2001. ↑3.4, 3.4, 10.1

    2001

  2. [10]

    Erd˝ os, and V

    W Brown, P. Erd˝ os, and V. S´ os,Some extremal problems on r-graphs, New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann arbor, Mic h, 1971), 1973, pp. 53–63. ↑9.2

    1971

  3. [11]

    Cilleruelo and C

    J. Cilleruelo and C. Timmons, k-Fold Sidon Sets , The Electronic Journal of Combinatorics 21 (Oct. 2014), no. 4, P4.12. ↑7.1

    2014

  4. [12]

    P Erd˝ os and M Simonovits,Some extremal problems in graph theory , Combinatorial Theory and its Applications I, 1970, pp. 378–392. ↑1.5

    1970

  5. [13]

    Erd˝ os and A

    P. Erd˝ os and A. R´ enyi,Asymmetric graphs, Acta Mathematica Hungarica 14 (1963), no. 3-4, 295–315. ↑3.4

    1963

  6. [14]

    Erd˝ os and P

    P. Erd˝ os and P. Tur´ an,On a problem of Sidon in additive number theory, and on some re lated problems, J. London Math. Soc 16 (1941), no. 4, 212–215. ↑2.3

    1941

  7. [15]

    Espuny D´ ıaz, B

    A. Espuny D´ ıaz, B. Janzer, G. Kronenberg, and J. Lada,Long running time for hypergraph bootstrap percolation , European Journal of Combinatorics 115 (2024), 103783. ↑1.7, 4, 10.4

    2024

  8. [16]

    Fabian, P

    D. Fabian, P. Morris, and T. Szab´ o,Slow graph bootstrap percolation I: Cycles , arXiv preprint arXiv:2308.00498 (2023). ↑1.2, 2.2, 9.2

    2023 arXiv

  9. [17]

    ↑1.2, 1.3, 1.3, 1.6, 1.6, 10.1

    , Slow graph bootstrap percolation II: Accelerating propert ies, Journal of Combinatorial Theory, Series B 172 (2025), 44–79. ↑1.2, 1.3, 1.3, 1.6, 1.6, 10.1

    2025

  10. [18]

    G. Fan, H. Lai, R. Xu, C.-Q. Zhang, and C. Zhou, Nowhere-zero 3-flows in triangularly connected graphs , Journal of Combinatorial Theory, Series B 98 (2008), no. 6, 1325–1336. ↑3.3

    2008

  11. [19]

    F¨ uredi and M

    Z. F¨ uredi and M. Simonovits, The history of degenerate (bipartite) extremal graph probl ems, Erd˝ os centennial, 2013, pp. 169–264. ↑1.5, 1.5

    2013

  12. [20]

    Hartarsky and L

    I. Hartarsky and L. Lichev, The maximal running time of hypergraph bootstrap percolati on, SIAM Journal on Discrete Mathematics 38 (2024), no. 2, 1462–1471. ↑1.7, 4, 10.4

    2024

  13. [21]

    Hou, H.-J

    X. Hou, H.-J. Lai, M. Zhan, T. Zhang, and J. Zhou, Z3-connectivity of 4-edge-connected 2-triangular graphs , European Journal of Combinatorics 33 (2012), no. 2, 182–188. ↑3.3

    2012

  14. [22]

    Janson, T

    S. Janson, T. /suppress Luczak, and A. Ruci´ nski,Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. ↑2.4

    2000

  15. [23]

    Kelley and R

    Z. Kelley and R. Meka, Strong bounds for 3-progressions , 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2023, pp. 933–973. ↑2.3

    2023

  16. [24]

    T S´ os, and P

    P K˝ ov´ ari, V. T S´ os, and P. Tur´ an,On a problem of Zarankiewicz , Colloquium Mathematicum, 1954, pp. 50–57. ↑1.5

    1954

  17. [25]

    J. H. Kim, B. Sudakov, and V. H Vu, On the asymmetry of random regular graphs and random graphs , Random Structures & Algorithms 21 (2002), no. 3-4, 216–224. ↑3.4, 10.1 SLOW GRAPH BOOTSTRAP PERCOLATION III 51

    2002

  18. [26]

    Koml´ os and M

    J. Koml´ os and M. Simonovits, Szemer´ edi’s regularity lemma and its applications in grap h theory , Center for Discrete Mathematics & Theoretical Computer Science, 1995 . ↑9.2

    1995

  19. [27]

    Lazebnik, V

    F. Lazebnik, V. A Ustimenko, and A. J Woldar, A new series of dense graphs of high girth , Bulletin of the American mathematical society 32 (1995), no. 1, 73–79. ↑8

    1995

  20. [28]

    1-3, 271–283

    , A characterization of the components of the graphs D(k, q), Discrete Mathematics 157 (1996), no. 1-3, 271–283. ↑8

    1996

  21. [29]

    Lazebnik and J

    F. Lazebnik and J. Verstra¨ ete,On hypergraphs of girth five , Electronic Journal of Combinatorics 10 (2003), no. 1, R25. ↑7.1

    2003

  22. [30]

    Lazebnik and R

    F. Lazebnik and R. Viglione, On the connectivity of certain graphs of high girth , Discrete Mathematics 277 (Feb. 2004), no. 1-3, 309–319 (en). ↑8

    2004

  23. [31]

    L. Li, C. Li, R. Luo, and C.-Q. Zhang, Integer flows on triangularly connected signed graphs , Journal of Graph Theory 106 (2024), no. 2, 257–272. ↑3.3

    2024

  24. [32]

    Matzke, The saturation time of graph bootstrap percolation , arXiv preprint arXiv:1510.06156 (2015)

    K. Matzke, The saturation time of graph bootstrap percolation , arXiv preprint arXiv:1510.06156 (2015). ↑1.1

    2015 arXiv

  25. [33]

    McDiarmid and N

    C. McDiarmid and N. Yolov, Hamilton cycles, minimum degree, and bipartite holes , Journal of Graph Theory 86 (2017), no. 3, 277–285. ↑3.2

    2017

  26. [34]

    J. A. Noel and A. Ranganathan, On the Running Time of Hypergraph Bootstrap Percolation , Electronic Journal of Combinatorics 30 (2023), no. 2, P2.46. ↑1.7, 4, 10.4

    2023

  27. [35]

    Ruzsa, Solving a linear equation in a set of integers I , Acta Arithmetica 65 (1993), no

    I. Ruzsa, Solving a linear equation in a set of integers I , Acta Arithmetica 65 (1993), no. 3, 259–282 (en). ↑1.7, 2.3, 7.1, A, A.3, A.3

    1993

  28. [36]

    Z Ruzsa and E

    I. Z Ruzsa and E. Szemer´ edi,Triple systems with no six points carrying three triangles , Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai 18 (1978), no. 939-945, 2. ↑9.2

    1978

  29. [37]

    Shapira, Behrend-type constructions for sets of linear equations , Acta Arithmetica 122 (2006), no

    A. Shapira, Behrend-type constructions for sets of linear equations , Acta Arithmetica 122 (2006), no. 1, 17–33. ↑7.1

    2006

  30. [38]

    Singer, A theorem in finite projective geometry and some application s to number theory , Transactions of the American Mathematical Society 43 (1938), no

    J. Singer, A theorem in finite projective geometry and some application s to number theory , Transactions of the American Mathematical Society 43 (1938), no. 3, 377–385. ↑2.3, 6.3

    1938

  31. [39]

    D. B. West, Introduction to graph theory , Vol. 2, Prentice hall Upper Saddle River, 2001. ↑3.1.2 Appendix A. Additive constructions In this appendix, we prove Theorems 7.2 and 7.3 giving large sets avoiding non-trivial solutions to several equations. In order to do so, we ada...

    2001

  32. [40]

    Taking ( A.5) modulo (2 k1 + 1)q, we get that D = α1(b1 − b3) + α2(b2 − b4) is congruent to 0 modulo (2k1 + 1)q

    + α2(b′ 2 − b′ 4) ) = 0. Taking ( A.5) modulo (2 k1 + 1)q, we get that D = α1(b1 − b3) + α2(b2 − b4) is congruent to 0 modulo (2k1 + 1)q. However we also have that |D| ≤ 2k1q and so we must in fact have that D = 0 in the non-modular setting, that is (A.6) α1(b1 − b3) = α2(b4 −...

  33. [41]

    If b1 = b3 or b2 = b4 then both equalities must hold and ( a1, a2, a3, a4) is a trivial solution

    mod q. If b1 = b3 or b2 = b4 then both equalities must hold and ( a1, a2, a3, a4) is a trivial solution. Therefore we can divide the left and right hand side of ( A.7) by α1(b1 − b3) = α2(b4 − b2) ̸= 0 to obtain that b1 + b3 = b4 + b2 mod q. Using this and adding α1(b1 + b3) t...

Pith tools

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