Abstract
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.
Originalsprache | englisch |
---|---|
Aufsatznummer | P2.48 |
Seitenumfang | 14 |
Fachzeitschrift | The Electronic Journal of Combinatorics |
Jahrgang | 23 |
Ausgabenummer | 2 |
DOIs | |
Publikationsstatus | Veröffentlicht - 10 Juni 2016 |
ASJC Scopus subject areas
- Diskrete Mathematik und Kombinatorik
Treatment code (Nähere Zuordnung)
- Basic - Fundamental (Grundlagenforschung)