Back to Search
Start Over
Creation and Growth of Components in a Random Hypergraph Process.
Creation and Growth of Components in a Random Hypergraph Process.
- Source :
- Computing & Combinatorics (9783540369257); 2006, p350-359, 10p
- Publication Year :
- 2006
-
Abstract
- Denote by an ℓ-component a connected b-uniform hypergraph with k edges and k(b-1) - ℓ vertices. We prove that the expected number of creations of ℓ-component during a random hypergraph process tends to 1 as ℓ and b tend to ∞ with the total number of vertices n such that $\ell = o\left( \sqrt[3]{\frac{n}{b}} \right)$. Under the same conditions, we also show that the expected number of vertices that ever belong to an ℓ-component is approximately 121/3 (b-1)1/3 ℓ1/3n2/3. As an immediate consequence, it follows that with high probability the largest ℓ-component during the process is of size O( (b-1)1/3 ℓ1/3n2/3 ). Our results give insight about the size of giant components inside the phase transition of random hypergraphs. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540369257
- Database :
- Complementary Index
- Journal :
- Computing & Combinatorics (9783540369257)
- Publication Type :
- Book
- Accession number :
- 32887324
- Full Text :
- https://doi.org/10.1007/11809678_37