|
This article is cited in 2 scientific papers (total in 2 papers)
Independence numbers of random sparse hypergraphs
A. S. Semenov, D. A. Shabanov Lomonosov Moscow State University
Abstract:
The paper is concerned with the asymptotic behaviour of the independence number for the binomial model of a random $k$-regular hypergraph $H(n,k,p)$ in a sparse case, when $p=c/{n-1\choose k-1}$ with positive constant $c>0$. The independence number $\alpha(H(n,k,p))$ is shown to satisfy the law of large numbers $$ \frac{\alpha(H(n,k,p))}{n}\stackrel{P}{\to}\gamma(c)\;\; as n\to+\infty $$ with some constant $\gamma(c)>0$. We also shows that $\gamma(c)>0$ is a solution of some transcendental equation for small values of $c\leqslant (k-1)^{-1}$.
Keywords:
hypergraph, independence number, sparse hypergraphs, the method of interpolation, the Karp–Sipser algorithm.
Received: 19.06.2016
Citation:
A. S. Semenov, D. A. Shabanov, “Independence numbers of random sparse hypergraphs”, Diskr. Mat., 28:3 (2016), 126–144; Discrete Math. Appl., 27:4 (2017), 231–245
Linking options:
https://www.mathnet.ru/eng/dm1387https://doi.org/10.4213/dm1387 https://www.mathnet.ru/eng/dm/v28/i3/p126
|
Statistics & downloads: |
Abstract page: | 545 | Full-text PDF : | 95 | References: | 77 | First page: | 39 |
|