Tue, 03 Nov 2015
Bhargav Narayanan
University of Cambridge

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.

Please contact us for feedback and comments about this page. Last updated on 04 Apr 2022 14:57.