On the matching number and the independence number of a random induced subhypergraph of a hypergraph
Bull. Korean Math. Soc. 2018 Vol. 55, No. 5, 1523-1528
https://doi.org/10.4134/BKMS.b170883
Published online September 30, 2018
Sang June Lee
Duksung Women's University
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$.
Keywords : matching number, independence number, hypergraph
MSC numbers : 05C70, 05C69, 05C65
Downloads: Full-text PDF  


Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd