On the Matching Problem in Random Hypergraphs

Abstract

We study a variant of the Erdős Matching Problem in random hypergraphs. Let ${\mathcal{K}}_p(n,k)$ denote the Erdős-Rényi random $k$-uniform hypergraph on $n$ vertices where each possible edge is included with probability $p$. We show that when $n\gg k^{2}s$ and $p$ is not too small, with high probability, the maximum number of edges in a sub-hypergraph of ${\mathcal{K}}_p(n,k)$ with matching number $s$ is obtained by the trivial sub-hypergraphs, i.e. the sub-hypergraph consisting of all edges containing at least one vertex in a fixed set of $s$ vertices.

14 pages