{"id":"73a64b3b-9267-4d7f-b833-04eab3cc64ce","arxiv_id":"2508.19435","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"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.","lead":"A graph is weakly F-saturated if all missing edges can be added one by one, each creating a new copy of F. For complete bipartite graphs K_{s,t}, this paper determines the minimum starting size exactly when the vertex set has s+t+1 vertices and gcd(s,t)=1, and up to one edge otherwise, plus bounds for larger vertex sets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; Lemma 2.3 and the Q-excess case analysis appear sound.","rationale":"The reader correctly identifies Lemma 2.3 as the load-bearing technical step, and I agree that the lower bound would collapse if an unlisted transition existed. However, on careful review the lemma's classification is complete: edge deletion can increase components by at most one, vertex operations preserve component count and only add hyperedges, and the four listed vectors cover all splits of the hyperedge containing the erased edge. The subsequent case analysis in Proposition 3.2 is intricate but internally consistent, with size constraints preventing the impossible cases (e.g., f1=1,c1=2 for s>2). The paper is honest about its limitations and provides explicit constructions for upper bounds. I therefore have no concrete objection to the central claim; the only residual concern is the usual one for lengthy human case analyses, which a small computational check for s=3 would mitigate.","tokens_in":19243,"tokens_out":30868,"duration_ms":318137,"concrete_test":"For the smallest nontrivial case s=3 (n=7), exhaustively generate all graphs on 7 vertices (up to isomorphism), test which are erasable via the definition, confirm the maximum number of edges is 8 as claimed by Theorem 1.1, and for one maximal erasable graph simulate the hyperforest construction through a full erase process, checking at every step that (Δf,Δc) is one of the four Lemma 2.3 vectors plus (λ,0) and that the total excess Q is at least 3. If the script finds any step violating the lemma or a maximal erasable graph with 9 edges, the lower-bound method fails; otherwise it confirms the proof on the first open case.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central lower bound rests on Lemma 2.3: every erase step changes (f_i,c_i) by one of four vectors plus (λ,0), forcing s_i=f_i+2c_i to grow by at least 1 per step, and then on the case analysis in Proposition 3.2 showing total excess Q≥3 for s=t. I checked the logic of Lemma 2.3: removing one edge from a connected hyperedge can split it into at most two components, and each subsequent vertex-operation replaces a hyperedge containing the closed vertex by h new hyperedges all sharing that vertex, so h−1 hyperedges are added while the component count is unchanged. Thus the four listed edge-operation vectors, plus an arbitrary nonnegative (λ,0) from vertex-operations, exhaust the possibilities. The size constraints in Lemma 3.1 (parts of K_{s,t} both have size s>2) are essential and are used correctly: for example, in the case of two disjoint hyperedges, a split of a connected hyperedge would create a forbidden extra cross edge, forcing the erasable edge and closed vertex into different hyperedges. I did not find a missing transition or an unhandled configuration in Proposition 3.2. Since the proof is long and not machine-checked, the residual risk is a hidden subcase in the case analysis, not a demonstrated flaw.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":19561,"tokens_out":36492,"duration_ms":391872,"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":[{"comment":"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'","section":"Section 2.1, Claim 2.1"},{"comment":"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.","section":"Section 5.2, definition of j-erase"},{"comment":"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.","section":"Section 3.2, Lemma 3.1, case 1"}],"minor_comments":[{"comment":"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.","section":"Section 3.2, Proposition 3.2"},{"comment":"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.","section":"Section 4.2, Claim 4.1"},{"comment":"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.","section":"Section 5.1, Upper bound graph"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The core method and results appear sound, but the manuscript contains a false central equivalence (Claim 2.1) whose repair is short: one should prove the claim for maximum erasable graphs and then note that arbitrary erasable constructions can be augmented to maximum ones. The relaxed j-erase definition also needs a clearer logical framing. After these revisions, I expect the paper to be acceptable. The case analysis in Sections 3 and 4 is lengthy but coherent; the main residual risk is a hidden subcase, not a demonstrated flaw."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a solid paper and the first real progress on wsat(K_{s,t}) for s+t < n < 3t-3. The exact value for n = s+t+1 when gcd(s,t)=1 is new, and the hyperforest semi-invariant method is a genuine innovation—not a routine extension of Kalai's linear algebra. The complement/erasable graph equivalence is clean, and the construction of the auxiliary hyperforest is careful. I checked Lemma 2.3 and the case analysis in Proposition 3.2; they hold up. The paper also honestly flags where it defers technical details and where its bounds are not tight.\n\nThe main soft spot is that the proof rests on a long, intricate case analysis that is not machine-checked, so a hidden subcase is possible—but I did not find one. The j-erase definition for small graphs is ad hoc, and the lower bound for j >= 3 leans on Bernshteyn-Kostochka and Mader rather than the new method, so Theorem 1.3's lower bound (3) is an order-of-magnitude result, not tight. The gap of 1 in the gcd(s,t)>1 case is minor relative to the novelty. The upper bound constructions are somewhat ad hoc, but they are explicit and the erasing orders are described in enough detail to verify.\n\nThis is for extremal combinatorists working on saturation problems; the method deserves scrutiny and may be useful in other settings. A serious referee should engage with this paper, and I would support sending it to peer review. My own verdict is a cautious accept: the central argument appears sound, and the contribution is real.","headline":"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.","tokens_in":20030,"tokens_out":1475,"would_cite":true,"duration_ms":16541,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C65","05C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"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).","keywords":["weakly saturated graph","weak saturation number","complete bipartite graph","erase process","auxiliary hyperforest","semi-invariant","k-connected subgraph","extremal graph theory"],"falsifier":"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.","tokens_in":19162,"feed_emoji":"🧮","tokens_out":11323,"duration_ms":93976,"temperature":0.7,"pith_summary":"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.","feed_headline":"Exact weak-saturation value found at n = 2s+1","feed_subtitle":"New hyperforest invariant closes the open range between n=s+t and n=3t-3.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"introduced the weak saturation number that the paper studies.","marker":"[5]"},{"why":"established the large-n formula for balanced complete bipartite graphs which the new results complement.","marker":"[11]"},{"why":"provided the previous bounds at n ≥ 3t-3 and the upper-bound construction extended here.","marker":"[14]"},{"why":"supplied the extremal edge bound for graphs without (k+1)-connected subgraphs that motivates and supports the general lower bound.","marker":"[16]"},{"why":"gave the improved constant used in Theorem 5.3 for the j ≥ 3 lower bound.","marker":"[2]"},{"why":"determined the exact values for n=s+t and for K_{2,t}, marking the boundary of the previously known range.","marker":"[17]"},{"why":"analysed why linear-algebraic lower bounds fail for weak saturation, motivating the new combinatorial method.","marker":"[19]"}],"fun_headline_variants":["Weak saturation exact for K_{s,t} in the middle range","Complement invariant cracks weak saturation of K_{s,t}","New method solves weak saturation for bipartite middle ground","Exact weak saturation numbers beyond the linear-algebraic regime","Hypergraph invariant clinches weak saturation for K_{s,t}"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Weak saturation exact for K_{s,t} in the middle range","Complement invariant cracks weak saturation of K_{s,t}","New method solves weak saturation for bipartite middle ground","Exact weak saturation numbers beyond the linear-algebraic regime","Hypergraph invariant clinches weak saturation for K_{s,t}"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000252,"raw_usage":{"total_tokens":1428,"prompt_tokens":805,"completion_tokens":623,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":549,"completion_tokens_details":{"reasoning_tokens":539}},"tokens_in":549,"tokens_out":623,"duration_ms":6056,"temperature":1.0,"reasoning_tokens":539,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T15:48:30.159664+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Bollob´ as","cited_arxiv_id":null,"evidence_quote":"introduced the weak saturation number that the paper studies."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"established the large-n formula for balanced complete bipartite graphs which the new results complement."},{"cited_title":"Kronenberg, T","cited_arxiv_id":null,"evidence_quote":"provided the previous bounds at n ≥ 3t-3 and the upper-bound construction extended here."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplied the extremal edge bound for graphs without (k+1)-connected subgraphs that motivates and supports the general lower bound."},{"cited_title":"Bernshteyn and A","cited_arxiv_id":null,"evidence_quote":"gave the improved constant used in Theorem 5.3 for the j ≥ 3 lower bound."},{"cited_title":"Miralaei, A","cited_arxiv_id":null,"evidence_quote":"determined the exact values for n=s+t and for K_{2,t}, marking the boundary of the previously known range."},{"cited_title":"Terekhov and M","cited_arxiv_id":null,"evidence_quote":"analysed why linear-algebraic lower bounds fail for weak saturation, motivating the new combinatorial method."}],"review_version":1}