The \(t\)-stability number of a random graph (Q976708)

Summary: Given a graph \(G = (V, E)\), a vertex subset \(S \subseteq V\) is called \(t\)-stable (or \(t\)-dependent) if the subgraph \(G[S]\) induced on S has maximum degree at most \(t\). The \(t\)-stability number \(\alpha t(G)\) of \(G\) is the maximum order of a \(t\)-stable set in \(G\). The theme of this paper is the typical values that this parameter takes on a random graph on \(n\) vertices and edge probability equal to \(p\). For any fixed \(0 < p < 1\) and fixed non-negative integer \(t\), we show that, with probability tending to 1 as \(n \rightarrow \infty \), the \(t\)-stability number takes on at most two values which we identify as functions of \(t, p\) and \(n\). The main tool we use is an asymptotic expression for the expected number of \(t\)-stable sets of order \(k\). We derive this expression by performing a precise count of the number of graphs on \(k\) vertices that have maximum degree at most \(t\).