General Independence Sets in Random Strongly Sparse Hypergraphs


Citar

Texto integral

Acesso aberto Acesso aberto
Acesso é fechado Acesso está concedido
Acesso é fechado Somente assinantes

Resumo

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.

Sobre autores

A. Semenov

Department of Probability Theory, Faculty of Mechanics and Mathematics; Chair of Discrete Mathematics, Department of Innovation and High Technology

Autor responsável pela correspondência
Email: alexsemenov1992@mail.ru
Rússia, Moscow; Moscow

D. Shabanov

Department of Probability Theory, Faculty of Mechanics and Mathematics; Laboratory of Advanced Combinatorics and Network Applications

Email: alexsemenov1992@mail.ru
Rússia, Moscow; Moscow

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML

Declaração de direitos autorais © Pleiades Publishing, Inc., 2018