TRANSFERENCE FOR THE ERDOS-KO-RADO THEOREM

József Balogh, Béla Bollobás, Bhargav P. Narayanan

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

For natural numbers n, ∈ 2 ℕ with n ≥ r, the Kneser graph K (n, r) is the graph on the family of r-element subsets of {1; ⋯, 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 Erdos-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.

Original languageEnglish (US)
Article numbere23
JournalForum of Mathematics, Sigma
Volume3
DOIs
StatePublished - Jan 1 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Analysis
  • Theoretical Computer Science
  • Algebra and Number Theory
  • Statistics and Probability
  • Mathematical Physics
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'TRANSFERENCE FOR THE ERDOS-KO-RADO THEOREM'. Together they form a unique fingerprint.

Cite this