Transference for the Erdős-Ko-Rado theorem

A random analogue of the Erdős-Ko-Rado theorem sheds light on its stability in an area of parameter space which has not yet been explored.

Forum of Mathematics, Sigma 3, 18 (2015)

J. Balogh, B. Bollobas, B. Narayanan

Transference for the Erdős-Ko-Rado theorem

For natural numbers, 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 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.

More in Spectre of hypercubes

  • European Journal of Combinatorics

    Hypercube eigenvalues

    Hamming balls, subgraphs of the hypercube, maximise the graph’s largest eigenvalue exactly when the dimension of the cube is large enough.

  • Journal of Physics A

    Spin systems on Bethe lattices

    Exact equations for the thermodynamic quantities of lattices made of d-dimensional hypercubes are obtainable with the Bethe-Peierls approach.

  • Discrete Mathematics

    Eigenvalues of neutral networks

    The principal eigenvalue of small neutral networks determines their robustness, and is bounded by the logarithm of the number of vertices.