TY - JOUR

T1 - Transference for the ErdH os-Ko-Rado theorem

AU - Balogh, József

AU - Bollobás, Béla

AU - Narayanan, Bhargav P.

N1 - Funding Information:
The first author is partially supported by a Simons fellowship, NSF CAREER grant DMS-0745185, Arnold O. Beckman Research Award (UIUC Campus Research Board 13039), and Marie Curie grant FP7-PEOPLE-2012-IIF 327763. The second author would like to acknowledge support from EU MULTIPLEX grant 317532 and NSF grant DMS-1301614.
Publisher Copyright:
© 2015 The Author(s).

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85016403522&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85016403522&partnerID=8YFLogxK

U2 - 10.1017/fms.2015.21

DO - 10.1017/fms.2015.21

M3 - Article

VL - 3

SP - e23, 18

JO - Forum of Mathematics, Pi

JF - Forum of Mathematics, Pi

SN - 2050-5094

M1 - e23

ER -