2025/08/26 by Akhmejanova, Margarita, Vorobyev, Ilya, Zhukovskii, Maksim
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.19435
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(Kn) ∖ 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 wsat(n, F). We obtain exact values and new bounds for wsat(n, Ks,t) in the previously unaddressed range s+t < n < 3t-3, where 3≤ s≤ 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.