Geodesic
Threshold and hitting time for high-order connectedness in random hypergraphs
Oliver Cooley1 ; Mihyun Kang1 ; Christoph Koch1
1Graz University of Technology
The electronic journal of combinatorics, Tome 23 (2016) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We consider the following definition of connectedness in $k$-uniform hypergraphs: two $j$-sets (sets of $j$ vertices) are $j$-connected if there is a walk of edges between them such that two consecutive edges intersect in at least $j$ vertices. The hypergraph is $j$-connected if all $j$-sets are pairwise $j$-connected. We determine the threshold at which the random $k$-uniform hypergraph with edge probability $p$ becomes $j$-connected with high probability. We also deduce a hitting time result for the random hypergraph process – the hypergraph becomes $j$-connected at exactly the moment when the last isolated $j$-set disappears. This generalises the classical hitting time result of Bollobás and Thomason for graphs.
DOI : 10.37236/5064
Classification : 05C65, 05C80, 05C40
Mots-clés : random hypergraphs, connectivity, hitting time

Oliver Cooley  1   ; Mihyun Kang  1   ; Christoph Koch  1

1 Graz University of Technology 
@article{10_37236_5064,
     author = {Oliver Cooley and Mihyun Kang and Christoph Koch},
     title = {Threshold and hitting time for high-order connectedness in random hypergraphs},
     journal = {The electronic journal of combinatorics},
     year = {2016},
     volume = {23},
     number = {2},
     doi = {10.37236/5064},
     zbl = {1339.05271},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/5064/}
}
TY  - JOUR
AU  - Oliver Cooley
AU  - Mihyun Kang
AU  - Christoph Koch
TI  - Threshold and hitting time for high-order connectedness in random hypergraphs
JO  - The electronic journal of combinatorics
PY  - 2016
VL  - 23
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/5064/
DO  - 10.37236/5064
ID  - 10_37236_5064
ER  - 
%0 Journal Article
%A Oliver Cooley
%A Mihyun Kang
%A Christoph Koch
%T Threshold and hitting time for high-order connectedness in random hypergraphs
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/5064/
%R 10.37236/5064
%F 10_37236_5064
Oliver Cooley; Mihyun Kang; Christoph Koch. Threshold and hitting time for high-order connectedness in random hypergraphs. The electronic journal of combinatorics, Tome 23 (2016) no. 2. doi: 10.37236/5064

Cité par Sources :