2023/05/18 by Nikolay Terekhov, Terekhov, Nikolai, Maksim Zhukovskii +1 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.2305.11043
openalex publication_date 2023/05/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The weak saturation number wsat(n,F) is the minimum number of edges in a graph on n vertices such that all the missing edges can be activated sequentially so that each new edge creates a copy of F. A usual approach to prove a lower bound for the weak saturation number is algebraic: if it is possible to embed edges of Kn in a vector space in a certain way (depending on F), then the dimension of the subspace spanned by the images of the edges of Kn is a lower bound for the weak saturation number. In this paper, we present a new combinatorial approach to prove lower bounds for weak saturation numbers that allows to establish worst-case tight (up to constant additive terms) general lower bounds as well as to get exact values of the weak saturation numbers for certain graph families. It is known (Alon, 1985) that, for every F, there exists cF such that wsat(n,F)=cFn(1+o(1)). Our lower bounds imply that all values in the interval [\fracδ2-(1)/(δ+1),δ-1] with step size (1)/(δ+1) are achievable by cF (while any value outside this interval is not achievable).