General Independence Sets in Random Strongly Sparse Hypergraphs |
| |
Authors: | A S Semenov D A Shabanov |
| |
Affiliation: | 1.Department of Probability Theory, Faculty of Mechanics and Mathematics,Lomonosov Moscow State University,Moscow,Russia;2.Chair of Discrete Mathematics, Department of Innovation and High Technology,Moscow Institute of Physics and Technology (State University),Moscow,Russia;3.Laboratory of Advanced Combinatorics and Network Applications,Moscow Institute of Physics and Technology (State University),Moscow,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/\left( \begin{gathered} n - 1 \hfill \\ k - 1 \hfill \\ \end{gathered} \right)\) for a positive constant 0 < c ≤ 1/(k ? 1), there exists a constant γ(k, j, c) > 0 such that the j-independence number α j (H(n, k, p)) obeys the law of large numbers \(\frac{{{\alpha _j}\left( {H\left( {n,k,p} \right)} \right)}}{n}\xrightarrow{P}\gamma \left( {k,j,c} \right)asn \to + \infty \) Moreover, we explicitly present γ(k, j, c) as a function of a solution of some transcendental equation. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|