On the stability of the Erdös-Ko-Rado theorem (Q498190): Difference between revisions

A family \(\mathcal{A}\) of sets is said to be \(t\)-intersecting if every two sets in \(\mathcal{A}\) have at least \(t\) common elements. Let \({[n] \choose r}\) denote the family of \(r\)-element subsets of \([n] = \{1, 2, \dots, n\}\). Let \(m(n,r,t)\) denote the size of a \(t\)-intersecting subfamily of \({[n] \choose r}\) of maximum size. The Erdős-Ko-Rado theorem states that, for any two positive integers \(r\) and \(t\) with \(r \geq t\), there exists an integer \(n_0(r,t)\) such that \(m(n,r,t) = {n-t \choose r-t}\) for every \(n \geq n_0(r,t)\). Thus, for \(n \geq n_0(r,t)\), the family of all sets in \({[n] \choose r}\) containing \([t]\) is a \(t\)-intersecting subfamily of \({[n] \choose r}\) of maximum size. Let \(G(n,r,<t)\) be the graph \((V,E)\) with vertex set \(V = {[n] \choose r}\) and edge set \(E = \{\{A,B\} : A, B \in V, \, |A \cap B| < t\}\). The independence number \(\alpha(G)\) of a graph \(G\) is the maximum size of a set \(I\) of vertices of \(G\) such that no two vertices in \(I\) form an edge of \(G\). Thus \(m(n,r,t) = \alpha(G(n,r,<t))\). Assigning equal probability to the subgraphs of \(G(n,r,<t)\), let \(p(n,r,t)\) denote the probability that the independence number of a random subgraph of \(G(n,r,<t)\) is \({n-t \choose r-t}\). Adding to probabilistic variants of the Erdős-Ko-Rado theorem that have been established recently by various authors, the author proves that \(p(n,r,t) \rightarrow 1\) as \(n \rightarrow \infty\).