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.

Authors :
Chen, Danny Z.
Lee, D. T.
Ravelomanana, Vlady
Rijamamy, Alphonse Laza
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