Tight concentration of star saturation number in random graphs

Autor:	Demyanov, Sergej, Zhukovskii, Maksim
Rok vydání:	2022
Předmět:	Mathematics - Combinatorics Mathematics - Probability
Druh dokumentu:	Working Paper
Popis:	For given graphs $F$ and $G$, the minimum number of edges in an inclusion-maximal $F$-free subgraph of $G$ is called the $F$-saturation number and denoted $\mathrm{sat}(G, F)$. For the star $F=K_{1,r}$, the asymptotics of $\mathrm{sat}(G(n,p),F)$ is known. We prove a sharper result: whp $\mathrm{sat}(G(n,p), K_{1,r})$ is concentrated in a set of 2 consecutive points.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2212.06101 Zobrazit plný text záznamu View this record from Arxiv