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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-06-21 Page: https://delphi.science/r/arxiv/2606.22661 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…