|
Problemy Peredachi Informatsii, 2018, Volume 54, Issue 1, Pages 63–77
(Mi ppi2260)
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers)
Large Systems
General independence sets in random strongly sparse hypergraphs
A. S. Semenovab, D. A. Shabanovac 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.
Received: 01.08.2016 Revised: 13.04.2017
Citation:
A. S. Semenov, D. A. Shabanov, “General independence sets in random strongly sparse hypergraphs”, Probl. Peredachi Inf., 54:1 (2018), 63–77; Problems Inform. Transmission, 54:1 (2018), 56–69
Linking options:
https://www.mathnet.ru/eng/ppi2260 https://www.mathnet.ru/eng/ppi/v54/i1/p63
|
Statistics & downloads: |
Abstract page: | 320 | Full-text PDF : | 41 | References: | 35 | First page: | 6 |
|