On the matching number and the independence number of a random induced subhypergraph of a hypergraph

Abstract

For $r\geq 2$, let $\mathcal H$ be an $r$-uniform hypergraph with $n$ vertices and $m$ hyperedges. Let $R$ be a random vertex set obtained by choosing each vertex of $\mathcal H$ independently with probability $p$. Let $\mathcal H[R]$ be the subhypergraph of $\mathcal H$ induced on $R$. We obtain an upper bound on the matching number $\nu(\mathcal H[R])$ and a lower bound on the independence number $\alpha(\mathcal H[R])$ of $\mathcal H[R]$. First, we show that if $mp^r\geq \log n$, then $\nu(\mathcal H[R])\leq 2e^\ell mp^r$ with probability at least $1-1/n^\ell$ for each positive integer~$\ell$. It is best possible up to a constant factor depending only on $\ell$ if $m\leq n/r$. Next, we show that if $mp^r\geq \log n$, then $\alpha(\mathcal H[R])\geq np-\sqrt{3\ell np \log n}-2re^\ell mp^r$ with probability at least $1-3/n^\ell$.