= Independent sets in every large subset of a dense random graph
{title2=$|U|\ge n/(\log n)^2\Longrightarrow\alpha(G[U])\ge(2-\gamma)\log_{1/(1-p)}n$}
For fixed $p$ and $\gamma>0$, <Janson inequality> bounds the failure probability for a given large <vertex> subset by $\exp(-c|U|^2/(\log n)^4)$. A union bound over all at most $2^n$ subsets still tends to zero. This uniform statement is essential because <vertex> sets left by a greedy colouring procedure depend on the <graph>; one cannot assume each adaptively chosen remainder is an independent fresh random <graph>.
Back to article page
