Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.15686 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911432578170880 |
|---|---|
| author | Ascoli, Ruben He, Xiaoyu |
| author_facet | Ascoli, Ruben He, Xiaoyu |
| contents | 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 $\operatorname{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 $\operatorname{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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_15686 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Rational values of the weak saturation limit Ascoli, Ruben He, Xiaoyu Combinatorics 05C35 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 $\operatorname{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 $\operatorname{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$. |
| title | Rational values of the weak saturation limit |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2501.15686 |