On the random version of the Erdős matching conjecture

Abstract

The Kneser hypergraph ${\mathrm{KG}}_{n,k}^r$ is an $r$-uniform hypergraph with vertex set consisting of all $k$-subsets of $\{1,\dots ,n\}$ and any collection of $r$ vertices forms an edge if their corresponding $k$-sets are pairwise disjoint. The random Kneser hypergraph ${\mathrm{KG}}_{n,k}^r(p)$ is a spanning subhypergraph of ${\mathrm{KG}}_{n,k}^r$ in which each edge of ${\mathrm{KG}}_{n,k}^r$ is retained independently of each other with probability $p$. The independence number of random subgraphs of ${\mathrm{KG}}_{n,k}^2$ was recently addressed in a series of works by Bollob{á}s, Narayanan, and Raigorodskii (2016), Balogh, Bollob{á}s, and Narayanan (2015), Das and Tran (2016), and Devlin and Kahn (2016). It was proved that the random counterpart of the Erdős-Ko-Rado theorem continues to be valid even for very small values of $p$. In this paper, generalizing this result, we will investigate the independence number of random Kneser hypergraphs ${\mathrm{KG}}_{n,k}^r(p)$. Broadly speaking, when $k$ is much smaller that $n$, we will prove that the random analogue of the Erdős matching conjecture is true even for extremely small values of $p$.

11 pages