- Current Issue - Ahead of Print Articles - All Issues - Search - Open Access - Information for Authors - Downloads - Guideline - Regulations ㆍPaper Submission ㆍPaper Reviewing ㆍPublication and Distribution - Code of Ethics - For Authors ㆍOnlilne Submission ㆍMy Manuscript - For Reviewers - For Editors
 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.b170883Published 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