TRANSFERENCE FOR THE ERDŐS–KO–RADO THEOREM. (26th October 2015)

• Record Type: Journal Article
• Authors: BALOGH, JÓZSEF; BOLLOBÁS, BÉLA; NARAYANAN, BHARGAV P.
• Is Part Of: Forum of mathematics. Volume 3(2015)
• Publication Date: 2015-10-26
• Subjects: 05D05 (primary), -- 05C80, -- 05D40 (secondary); Mathematics -- Periodicals; 510
• DOI: 10.1017/fms.2015.21
• Languages: English
• ISSNs: 2050-5094

Abstract

Abstract : For natural numbers $n, r\in \mathbb{N}$ with $n\geqslant r$, the Kneser graph $K(n, r)$ is the graph on the family of $r$ -element subsets of $\{1, \ldots, n\}$ in which two sets are adjacent if and only if they are disjoint. Delete the edges of $K(n, r)$ 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? We shall answer this question affirmatively as long as $r/n$ is bounded away from $1/2$, even when the probability of retaining an edge of the Kneser graph is quite small. This gives us a random analogue of the Erdős–Ko–Rado theorem, since an independent set in the Kneser graph is the same as a uniform intersecting family. To prove our main result, we give some new estimates for the number of disjoint pairs in a family in terms of its distance from an intersecting family; these might be of independent interest.