Transference for the Erdős–Ko–Rado theorem

3 November 2015
Bhargav Narayanan

The ErdősKoRado theorem is a central result in extremal set theory which tells us how large uniform intersecting families can be. In this talk, I shall discuss some recent results concerning the 'stability' of this result. One possible formulation of the ErdősKoRado theorem is the following: if $n \ge 2r$, then the size of the largest independent set of the Kneser graph $K(n,r)$ is $\binom{n-1}{r-1}$, where $K(n,r)$ is the graph on the family of $r$-element subsets of $\{1,\dots,n\}$ in which two sets are adjacent if and only if they are disjoint. The following will be the question of interest. Delete the edges of the Kneser graph with some probability, independently of each other: is the independence number of this random graph equal to the independence number of the Kneser graph itself? I shall discuss an affirmative answer to this question in a few different regimes. Joint work with Bollobás and Raigorodskii, and Balogh and Bollobás.

  • Combinatorial Theory Seminar