{"id":"arxiv/2606.22661","url":"https://arxiv.org/abs/2606.22661","tags":["math.CO"],"score":0,"title":"Excluding an induced star in dense random graphs","domain":"math.CO","source":"arxiv","authors":["Sam van der Poel"],"reviews":0,"subject":"math.CO","summary":"For fixed $k\\geq3$, we study the asymptotic number and typical structure of dense graphs with no induced copy of the star $K_{1,k}$. We solve the associated graphon variational problems both at fixed constant edge density $γ$ and for the conditioned Erdős--Rényi random graph $G(n,p)$ for constant $p$. As consequences, we obtain explicit formulas for the entropy density of induced-$K_{1,k}$-free graphs with $Θ(n^2)$ edges and for the large deviation rate function for the event that $G(n,p)$ is induced-$K_{1,k}$-free. The entropy density exhibits a second-order phase transition at an explicit…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-21","reactions":{}}