Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Weak saturation numbers of large complete bipartite graphs

T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read The paper proves exact weak saturation numbers of complete bipartite graphs in the previously open range just above n = s+t, led by wsat(2s+1,K_{s,s}) = C(2s+1,2) - (4s-4).

desk verdict Genuinely new method and first exact values in a previously open range, with a long case analysis that looks right but is not machine-checked. read the letter →

arxiv 2508.19435 v1 pith:UBG4CA3X submitted 2025-08-26 math.CO

Margarita Akhmejanova , Ilya Vorobyev , Maksim Zhukovskii This is my paper
classification math.CO MSC 05C3505C6505C40
keywords weaklysaturatedgraphweaksaturationnumbercompletebipartiteeraseprocessauxiliaryhyperforestsemi-invariantk-connectedsubgraphextremaltheory
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

Every graph on n vertices that is weakly saturated for a complete bipartite graph K_{s,t} must contain at least wsat(n,K_{s,t}) edges. Until now, this number was known only for n = s+t and for n at least 3t-3, leaving the intermediate range open. The paper fills this gap for the first few values of n: it proves the exact value for n = 2s+1 in the balanced case, an exact or one-off value for n = s+t+1 in general, and bounds of matching order for all n = s+t+j. The engine is a new counting method based on an erase process in the complement graph and an auxiliary hyperforest whose semi-invariant increases at every step.

What carries the argument

The load-bearing object is the auxiliary hyperforest H_i assigned to the i-th graph in the erase process: a hypergraph with no cycles whose hyperedges cover the remaining edges and induce connected subgraphs. Each erase step applies an edge-operation to the unique hyperedge containing the erased edge, then vertex-operations to every hyperedge containing the closed witness vertex. Lemma 2.3 shows the pair (f_i,c_i) changes by one of (1,0), (1,1), (0,1), (-1,1) plus (λ,0), so the semi-invariant s_i = f_i + 2c_i satisfies s_i ≥ s_{i-1} + 1. Summing this inequality over the whole process bounds the number of edges in the complement, i.e. gives the lower bound on wsat; the paper then analyzes the

What would settle it

For one fixed s > 2, exhaustively enumerate all graphs on 2s+1 vertices and check weak K_{s,s}-saturation: if any has fewer than C(2s+1,2) - (4s-4) edges, the formula fails; equivalently, if any erasable complement has more than 4s-4 edges, the upper-bound side fails. The s = 3 case on 7 vertices is a finite, currently feasible search.

Watch

Extended reading notes

Core claim

The paper's central claim is that in the range s+t < n < 3t-3 the weak saturation number of a complete bipartite graph K_{s,t} is controlled by a structural invariant of the complement, not by the linear-algebraic bounds used for larger n. The main exact results are wsat(2s+1,K_{s,s}) = C(2s+1,2) - (4s-4) for every s > 2, and for t > s > 2, wsat(s+t+1,K_{s,t}) = C(s+t+1,2) - (2s+2t-2) when gcd(s,t) = 1, with the non-coprime value lying within one edge. The general bound for all small excesses is wsat(s+t+j,K_{s,t}) = C(s+t+j,2) - Θ(j(s+t)) for 2 ≤ j < t-2. The new proof framework defines an erase process on the complement graph: edges are deleted in reverse saturation order, and an auxiliary

Load-bearing premise

The proof assumes that every split of a hyperedge in the erase process falls into one of the four enumerated transition types, so that the semi-invariant always grows by at least one per erased edge.

Editorial extensions

If this is right

  • For every s > 2, the exact count wsat(2s+1,K_{s,s}) = C(2s+1,2) - (4s-4) holds, closing the balanced case at n = 2s+1.
  • For s < t with gcd(s,t) = 1, the exact value at n = s+t+1 is C(n,2) - (2s+2t-2); in the non-coprime case the value is within one edge of this bound.
  • For every small excess j ≥ 2, wsat(s+t+j,K_{s,t}) = C(s+t+j,2) - Θ(j(s+t)), giving the order of the second-order term throughout the previously unaddressed range.
  • The complement of any weakly K_{s,t}-saturated graph on s+t+j vertices has no (j+2)-connected subgraph, linking weak saturation lower bounds to extremal bounds for k-connected subgraphs.

Reading between the lines

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

  • The hyperforest invariant is not obviously limited to K_{s,t}: the same erase-process analysis may yield exact weak saturation numbers for other bipartite forbidden graphs near the critical n = s+t.
  • The Θ(j(s+t)) gap between upper and lower bounds suggests a general asymptotic principle: when n exceeds the part-sum by a fixed j, wsat(n,K_{s,t}) = C(n,2) - cn for an explicit constant c that the erase process could, in principle, compute.
  • For non-coprime pairs where the paper's computer search found exact constructions, the one-edge gap may be an artifact of the proof rather than the true value; testing more pairs would clarify whether the exact formula extends.
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

3 major / 4 minor

Summary. The paper studies weak saturation numbers wsat(n, K_{s,t}) in the previously open range s+t < n < 3t-3, focusing on n = s+t+j with small j. For n = 2s+1 and s=t>2, it claims the exact value wsat(2s+1, K_{s,s}) = binom(2s+1,2) - (4s-4). For n = s+t+1, s<t, it gives exact values when gcd(s,t)=1 and bounds differing by one otherwise. For general 2 ≤ j < t-2, it provides upper and lower bounds, including a lower bound based on the Bernshteyn–Kostochka theorem on graphs without highly connected subgraphs. The main novelty is an auxiliary hyperforest associated to an erase process in the complement, equipped with a semi-invariant f_i + 2c_i that increases by at least one per step; upper bounds come from explicit erasable graph constructions, lower bounds from a case analysis of the hyperforest evolution.

Significance. If the results are correct, this is a substantial advance: it gives the first exact values in the intermediate regime and introduces a new combinatorial method (hyperforests and semi-invariants) that is genuinely different from the linear-algebraic approach that had dominated the area. The paper is honest about its limitations, explicitly deferring some technicalities for future work and stating where it relies on published results. The lower-bound machinery is intricate, and the case analysis, while not machine-checked, is coherent and self-contained. The construction methods for the upper bounds and the reduction to known results for k-connected subgraphs are also of independent interest.

major comments (3)
  1. [Section 2.1, Claim 2.1] The claimed equivalence 'G is erasable iff its complement is weakly K_{s,t}-saturated' is false as stated, because weak saturation by definition requires the initial graph to be F-free. An erasable graph's complement need not be F-free: on 7 vertices, the one-edge graph is erasable for K_{3,3} (any edge is unique between suitable 3+3 parts), but its complement contains a K_{3,3}, e.g. on parts {a,b,c} and {d,e,f} when the only missing edge is ab. The proof couples the two processes but never checks the F-free condition. This is load-bearing for the upper bounds in Theorems 1.1 and 1.2, which construct erasable graphs and invoke Claim 2.1. The fix is to prove the claim only for maximum erasable graphs: if such a G had a K_{s,t} in its complement, adding any missing cross edge and erasing it first would give a strictly larger erasable graph, a contradiction; hence a maximum erasable graph'
  2. [Section 5.2, definition of j-erase] The j-erase procedure is defined without requiring |V_1|=s and |V_2|=t, only |V(G)|-|V_1|-|V_2|=j. This is a relaxation of the actual K_{s,t}-erase condition, and the paper says 'similarly to Claim 2.1' to connect it to wsat. The relaxed class is larger, so bounding it from above does give a valid lower bound for wsat, but this monotonicity should be stated explicitly. More importantly, the phrase 'similarly to Claim 2.1' inherits the problem of Claim 2.1: the process correspondence only works for the relaxed weak-saturation notion and needs the maximum-graph augmentation argument before it yields a lower bound for the strict wsat. Please rewrite this passage to make the logical direction clear.
  3. [Section 3.2, Lemma 3.1, case 1] The proof states that 'e and v must belong to different hyperedges' because otherwise Erase(e,G) is not possible. This is not generally true for the erase process defined in Section 2 (e.g. the transition (f_0,c_0)=(1,1) to (f_1,c_1)=(2,1) has the erased edge and the closed vertex in the same initial hyperedge). In the specific situation of Lemma 3.1 the statement is plausible and follows from the combined size constraints |V_1|=|V_2|=s together with the connectedness of the two disjoint hyperedges, but this counting argument is omitted. Since Lemma 3.1 is used in the lower-bound proofs, please supply the missing argument or restate the lemma with the necessary hypotheses and proof.
minor comments (4)
  1. [Section 3.2, Proposition 3.2] The sentence 'if G is erasable, then every spanning subgraph of G is also erasable' is used to justify arbitrary choices of the erased edge, but no proof is given. This is true (it follows from the reverse weak-saturation ordering), but a short justification should be added.
  2. [Section 4.2, Claim 4.1] The proof contains the phrase 'It is easy to see by induction that all subsequent erase procedures preserve this structure.' Since this claim is load-bearing for the s≠t case, please expand this induction and in particular state what invariant is preserved at each step.
  3. [Section 5.1, Upper bound graph] The construction of the weakly K_{s,t}-saturated graph should explicitly verify that the initial graph is K_{s,t}-free, not just that the listed additions create copies of K_{s,t}. This is part of the definition of weak saturation.
  4. [Throughout] There are a few small typos and notational inconsistencies, e.g. 'auxuliary hyperforests' in the Section 2 heading, and the indices in Figures 1 and 5 are sometimes off by one. These do not affect the mathematics.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: derivation is self-contained.

full rationale

The paper's central claims are derived from an explicitly constructed erase-process/hyperforest machinery (Sections 2–5), not from the target values. The upper bounds are explicit erasable/weakly saturated constructions with edge counts; the lower bounds follow from Lemma 2.3's local change analysis, Corollary 2.4, Lemma 3.1, Proposition 3.2, Claim 4.1, and for j ≥ 3 from the external theorem of Bernshteyn and Kostochka. Claim 2.1 is an equivalence between weak saturation and erasability, a translation that is not a circular use of the target result. Self-citations [18] and [19] are contextual (background, conjectured failure of linear algebra) and are not load-bearing for the proofs. No parameter is fitted to a subset of data and then renamed as a prediction; the target values never enter as inputs. The residual risk is a hidden subcase in the case analysis, which is a correctness concern, not circularity.

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

No free parameters are introduced. The paper relies on standard external theorems for the large-j lower bounds and on one explicit ad hoc extension of the j-erase definition for small graphs. The auxiliary hyperforest is a defined proof object with no independent evidence requirement.

assumptions (4)
  • domain assumption Every spanning subgraph of an erasable graph is erasable
    Stated in Proposition 3.2 without proof; follows from the observation that erase witnesses remain valid in subgraphs.
  • ad hoc to paper For technical reasons, the j-erase procedure can be applied to any edge of any graph on j+1 vertices
    Section 5.2 extends the definition to make the base cases of the induction work; without this extension the f_j(k) recurrence would not be initialized.
  • standard math Bernshteyn-Kostochka theorem: every graph with at least 5k/2 vertices and at least (19k/12)(|V|-k) edges has a (k+1)-connected subgraph
    Used as Theorem 5.3 to derive lower bound (3) for j>=3.
  • standard math Mader's bound on maximum edges without (k+1)-connected subgraphs
    Used in Remark 1.4 and the discussion of the j=1 case to compare bounds.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Weak saturation numbers of large complete bipartite graphs." pith.science (2026). https://pith.science/paper/UBG4CA3X

@misc{pith2026250819435,
  author       = {Pith},
  title        = {Pith review of: Weak saturation numbers of large complete bipartite graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UBG4CA3X}},
  note         = {Machine review of arXiv:2508.19435}
}
abstract

An $n$-vertex graph $G$ is weakly $F$-saturated if $G$ contains no copy of $F$ and there exists an ordering of all edges in $E(K_n) \setminus E(G)$ such that, when added one at a time, each edge creates a new copy of $F$. The minimum size of a weakly $F$-saturated graph $G$ is called the weak saturation number $\mathrm{wsat}(n, F)$. We obtain exact values and new bounds for $\mathrm{wsat}(n, K_{s,t})$ in the previously unaddressed range $s+t < n < 3t-3$, where $3\leq s\leq t$. To prove lower bounds, we introduce a new method that takes into account connectivity properties of subgraphs of a complement $G'$ to a weakly saturated graph $G$. We construct an auxiliary hypergraph and show that a linear combination of its parameters always increases in the process of the deletion of edges of $G'$. This gives a lower bound which is tight, up to an additive constant.

Figures

Figures reproduced from arXiv: 2508.19435 by the authors.

Figure 1
Figure 1. Erasing process for the graph obtained from a disjoint ( [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Therefore, Q2 = (f2 − f1) + 2(c2 − c1) − 1 ≥ 3 implying Q ≥ 3 due to Corollary 2.4, as needed. e v1 |F1| = s + 1 |F2| = s + 1 v1 v2 [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 5
Figure 5. This graph consists of two disjoint paths [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
Figures from the paper (2 more)
Figure 6
Figure 6. Figure 6: The example of an erasable graph with 2s + 2t − 3 edges and s + t + 1 vertices and its erasing process for the case gcd(s, t) ̸= 1. Let us show that this graph is erasable, see [PITH_FULL_IMAGE:figures/full_fig_p018_6.png]
Figure 7
Figure 7. Figure 7: The weakly Ks,t-saturated graph G: A and the subset {bj+3, . . . , bt} of B induce cliques, all edges between sets A, B and between sets B, C are drawn except for the edges represented by dashed lines, the edge {b1, bj+3} is represented by a solid line. It is easy to s…

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. Full citation record

  1. The Complexity of Weak Saturation for Complete Graphs and Balanced Complete Bipartite Graphs

    math.CO 2026-07 accept novelty 7.0 of 10

    For every fixed r≥3, deciding wsat(F,H)≤k is NP-complete when H is Kr or Kr,r.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages · cited by 1 Pith paper

  1. [1]

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

    work page 1985

  2. [2]

    Bernshteyn and A

    A. Bernshteyn and A. Kostochka. On the number of edges in a graph with no ( k + 1)- connected subgraphs. Discrete Mathematics, 339:682–688, 2016

    work page 2016

  3. [3]

    Bidgoli, A

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

    work page 2024

  4. [4]

    Bollob´ as

    B. Bollob´ as. On generalized graphs. Acta Mathematica Academiae Scientiarum Hun- garica, 16:447–452, 1965

    work page 1965

  5. [5]

    Bollob´ as

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

    work page 1967

  6. [6]

    Borowiecki and E

    M. Borowiecki and E. Sidorowicz. Weakly p-saturated graphs. Discuss. Math. Graph Theory, 22:17–29, 2002

    work page 2002

  7. [7]

    When does a tree activate the random graph?

    A. Cohen Antonir, Y. Peled, A. Shapira, M. Tyomkyn, and M. Zhukovskii. When does a tree activate the random graph? arXiv preprint, arXiv:2507.05697, 2025

    work page Pith review arXiv 2025

  8. [8]

    Erd˝ os, A

    P. Erd˝ os, A. Hajnal, and J. W. Moon. A problem in graph theory. The American Mathematical Monthly, 71(10):1107–1110, 1964

    work page 1964

Show all 20 references
  1. [9]

    R. J. Faudree, R. J. Gould, and M. S. Jacobson. Weak saturation numbers for sparse graphs. Discuss. Math. Graph Theory, 33:677–693, 2013

    2013

  2. [10]

    P. Frankl. An extremal problem for two families of sets. European Journal of Combi- natorics, 3(2):125–127, 1982

    1982

  3. [11]

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

    1985

  4. [12]

    Kalinichenko and M

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

    2023

  5. [13]

    Kor´ andi and B

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

    2017

  6. [14]

    Kronenberg, T

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

    2021

  7. [15]

    Lov´ asz

    L. Lov´ asz. Flats in matroids and geometric graphs. In Combinatorial Surveys. 1977

    1977

  8. [16]

    W. Mader. Connectivity and edge-connectivity in finite graphs. In Surveys in Combi- natorics, pages 66–95. London, Cambridge University Press, 1979

    1979

  9. [17]

    Miralaei, A

    M. Miralaei, A. Mohammadian, and B. Tayfeh-Rezaie. Weak saturation numbers of k2,t. Discrete Applied Mathematics, 325:146–152, 2023

    2023

  10. [18]

    Terekhov and M

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

    2025

  11. [19]

    Terekhov and M

    N. Terekhov and M. Zhukovskii. Weak saturation rank: a failure of linear algebraic approach to weak saturation. Combinatorica, 2025

    2025

  12. [20]

    R. Yuster. A note on graphs without k-connected subgraphs. Ars Combin., 67:231–235, 2003. A Examples of erasable graphs • s = 4, t = 6. An erasable graph on 11 vertices and 18 edges is defined as follows. Let Pa = (a1a2a3a4) and Pb = (b1b2b3b4) be two vertex-disjoint paths and...

    2003

Pith tools

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