Rational values of the weak saturation limit

2025/01/26 by Ruben Ascoli, Xiaoyu He, Ascoli, Ruben +1 · 1 citation
Decision Sciences · Economics, Econometrics and Finance · #05C35 #Combinatorics (math.CO) #FOS: Mathematics #Probability and Risk Models #Risk and Portfolio Optimization #Stochastic processes and financial applications

paper · pdf · doi:10.48550/arxiv.2501.15686

openalex publication_date 2025/01/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a graph F, a graph G is weakly F-saturated if all non-edges of G can be added in some order so that each new edge introduces a copy of F. The weak saturation number wsat(n, F) is the minimum number of edges in a weakly F-saturated graph on n vertices. Bollobás initiated the study of weak saturation in 1968 to study percolation processes, which originated in biology and have applications in physics and computer science. It was shown by Alon that for each F, there is a constant w_F such that wsat(n, F) = w_Fn + o(n). We characterize all possible rational values of w_F, proving in particular that w_F can equal any rational number at least \frac 32.

Cited by

• When does a tree activate the random graph?

Related

• Weak saturation in graphs: a combinatorial approach
• Weak saturation rank: a failure of linear algebraic approach to weak saturation
• Weak saturation numbers of large complete bipartite graphs
• The weak saturation number of \boldsymbolK_{2, t}
• Weak saturation numbers in random graphs