Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-15T23:25:58.731Z Has data issue: false hasContentIssue false

TRANSFERENCE FOR THE ERDŐS–KO–RADO THEOREM

Published online by Cambridge University Press:  26 October 2015

JÓZSEF BALOGH
Affiliation:
Department of Mathematics, University of Illinois, 1409 W. Green Street, Urbana, IL 61801, USABolyai Institute, University of Szeged, 6720 Szeged, Hungary; jobal@math.uiuc.edu
BÉLA BOLLOBÁS
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK; b.p.narayanan@dpmms.cam.ac.ukDepartment of Mathematical Sciences, University of Memphis, Memphis, TN 38152, USALondon Institute for Mathematical Sciences, 35a South St., Mayfair, London W1K 2XF, UK; b.bollobas@dpmms.cam.ac.uk
BHARGAV P. NARAYANAN
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK; b.p.narayanan@dpmms.cam.ac.uk

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s) 2015