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.