RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2016 Volume 28, Issue 3, Pages 126–144 (Mi dm1387)

This article is cited 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.

UDC: 519.214+519.179.1+519.179.4

Received: 19.06.2016

DOI: 10.4213/dm1387


 English version:
Discrete Mathematics and Applications, 2017, 27:4, 231–245

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025