Geodesic
Independence numbers of random sparse hypergraphs
Diskretnaya Matematika, Tome 28 (2016) no. 3, pp. 126-144.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_2016_28_3_a8,
     author = {A. S. Semenov and D. A. Shabanov},
     title = {Independence numbers of random sparse hypergraphs},
     journal = {Diskretnaya Matematika},
     pages = {126--144},
     publisher = {mathdoc},
     volume = {28},
     number = {3},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2016_28_3_a8/}
}
TY  - JOUR
AU  - A. S. Semenov
AU  - D. A. Shabanov
TI  - Independence numbers of random sparse hypergraphs
JO  - Diskretnaya Matematika
PY  - 2016
SP  - 126
EP  - 144
VL  - 28
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2016_28_3_a8/
LA  - ru
ID  - DM_2016_28_3_a8
ER  - 
%0 Journal Article
%A A. S. Semenov
%A D. A. Shabanov
%T Independence numbers of random sparse hypergraphs
%J Diskretnaya Matematika
%D 2016
%P 126-144
%V 28
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2016_28_3_a8/
%G ru
%F DM_2016_28_3_a8
A. S. Semenov; D. A. Shabanov. Independence numbers of random sparse hypergraphs. Diskretnaya Matematika, Tome 28 (2016) no. 3, pp. 126-144. http://geodesic.mathdoc.fr/item/DM_2016_28_3_a8/

[1] Matula D. W., “On the complete subgraphs of a random graph”, Combinatory Mathematics and its applications, Chapel Hill, 1970, 356–369 | MR | Zbl

[2] Grimmett G., McDiarmid C., “On colouring random graphs”, Math. Proc. Cambr. Phil. Soc., 77 (1975), 313–325 | DOI | MR

[3] Bollobás B., Erdős P., “Cliques in random graphs”, Math. Proc. Cambr. Phil. Soc., 80 (1976), 419–427 | DOI | MR | Zbl

[4] Frieze A., “On the independence number of random graphs”, Discrete Mathematics, 81 (1990), 171–175 | DOI | MR | Zbl

[5] Wormald N., “Models of random regular graphs”, Surveys in Combinatorics, London Math. Soc. Lec. Notes Ser., 267, Cambridge Univ. Press, Cambridge, 1999, 239–298 | MR | Zbl

[6] Bayati M., Gamarnik D., Tetali P., “Combinatorial approach to the interpolation method and scaling limits in sparse random graphs”, Ann. Probab., 41:6 (2013), 4080–4015 | DOI | MR

[7] Karp R., Sipser M., “Maximum matchings in sparse random graphs”, 22nd Ann. Symp. on Found. Computer Sci., 1981, 364–375 | DOI

[8] Ding J., Sly A., Sun N., Maximum independent sets on random regular graphs, arXiv: 1310.4787

[9] Krivelevich M., Sudakov B., “The chromatic numbers of random hypergraphs”, Random Structures and Algorithms, 12 (1998), 381–403 | 3.0.CO;2-P class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[10] Bollobás B., Random Graphs, Cambridge Univ. Press, Cambridge, 2002 | MR

[11] Schmidt-Pruzan J., Shamir E., “Component structures in the evolution of random hypergraphs”, Combinatorica, 5:1 (1985), 81–94 | DOI | MR | Zbl