Back to Search Start Over

Weak saturation stability

Authors :
Kalinichenko, Olga
Zhukovskii, Maksim
Publication Year :
2021

Abstract

The paper studies wsat$(G,H)$ which is the minimum number of edges in a weakly $H$-saturated subgraph of $G$. We prove that wsat$(K_n,H)$ is `stable' - remains the same after independent removal of every edge of $K_n$ with constant probability - for all pattern graphs $H$ such that there exists a `local' set of edges percolating in $K_n$. This is true, for example, for cliques and complete bipartite graphs. We also find a threshold probability for the weak $K_{1,t}$-saturation stability.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2107.11138
Document Type :
Working Paper