A. S. Semenov, D. A. Shabanov, “General independence sets in random strongly sparse hypergraphs”, Probl. Peredachi Inf., 2018, Volume 54, Issue 1,Pages <nobr>63

This article is cited in 3 papers

Large Systems

General independence sets in random strongly sparse hypergraphs

A. S. Semenov^ab, D. A. Shabanov^ac

^a Department of Probability Theory, Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia
^b Chair of Discrete Mathematics, Department of Innovation and High Technology, Moscow Institute of Physics and Technology (State University), Dolgoprudny, Russia
^c Laboratory of Advanced Combinatorics and Network Applications, Moscow Institute of Physics and Technology (State University), Dolgoprudny, Russia

Abstract: We analyze the asymptotic behavior of the $j$-independence number of a random $k$-uniform hypergraph $H(n,k,p)$ in the binomial model. We prove that in the strongly sparse case, i.e., where $p=c\big/\binom{n-1}{k-1}$ for a positive constant $0<c\le1/(k-1)$, there exists a constant $\gamma(k,j,c)>0$ such that the $j$-independence number $\alpha_j(H(n,k,p))$ obeys the law of large numbers
$$ \frac{\alpha_j(H(n,k,p))}{n}\xrightarrow{\mathbf P\,}\gamma(k,j,c)\qquad\text{as}\quad n\to+\infty. $$

Moreover, we explicitly present $\gamma(k,j,c)$ as a function of a solution of some transcendental equation.

UDC: 621.391.1+519.1

Received: 01.08.2016
Revised: 13.04.2017