Name
Abstract | ||
|---|---|---|
We consider high-order connectivity in k-uniform hypergraphs defined as follows: Two j-sets are j-connected if there is a walk of edges between them such that two consecutive edges intersect in at least j vertices. We describe the evolution of j-connected components in the k-uniform binomial random hypergraph Hk(n,p). In particular, we determine the asymptotic size of the giant component shortly after its emergence and establish the threshold at which Hk(n,p) becomes j-connected with high probability. We also obtain a hitting time result for the related random hypergraph process {Hk(n,M)}M – the hypergraph becomes j-connected exactly at the moment when the last isolated j-set disappears. This generalises well-known results for graphs and vertex-connectivity in hypergraphs. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.endm.2015.06.077 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Random hypergraphs,high-order connectivity,hitting time,giant component,phase transition | Discrete mathematics,Combinatorics,Vertex (geometry),Hypergraph,Constraint graph,Binomial,Giant component,Connected component,Hitting time,Mathematics,The Intersect | Journal |
Volume | ISSN | Citations |
49 | 1571-0653 | 1 |
PageRank | References | Authors |
0.35 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oliver Cooley | 1 | 39 | 9.15 |
| Mihyun Kang | 2 | 163 | 29.18 |
| Christoph Koch | 3 | 1 | 0.35 |