# 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. Bollobás, B. Narayanan

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

### Hypercube eigenvalues

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

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

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