Threshold for weak saturation stability

Authors Mohammadreza Bidgoli, A. Mohammadian, B. Tayfeh-Rezaie, M. E. Zhukovskii

Publication date 11 June 2020

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We study the weak

K_{s}

-saturation number of the ErdH{o}s--R'{e}nyi random graph

m a t h b b m s l G (n, p)

, denoted by

m a t h r m w s a t (m a t h b b m s l G (n, p), K_{s})

, where

K_{s}

is the complete graph on

s

vertices. Kor'{a}ndi and Sudakov in 2017 proved that the weak

K_{s}

-saturation number of

K_{n}

is stable, in the sense that it remains the same after removing edges with constant probability. In this paper, we prove that there exists a threshold for this stability property and give upper and lower bounds on the threshold. This generalizes the result of Kor'{a}ndi and Sudakov. A general upper bound for

m a t h r m w s a t (m a t h b b m s l G (n, p), K_{s})

is also provided.

This page was built for publication: Threshold for weak saturation stability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6342711)