Creation and Growth of Components in a Random Hypergraph Process
| dc.creator | Ravelomanana, Vlady | |
| dc.creator | Rijamame, Alphonse Laza | |
| dc.date | 2006-07-12 | |
| dc.date.accessioned | 2026-07-07T07:16:20Z | |
| dc.date.available | 2026-07-07T07:16:20Z | |
| dc.description | Denote by an $\ell$-component a connected $b$-uniform hypergraph with $k$ edges and $k(b-1) - \ell$ vertices. We prove that the expected number of creations of $\ell$-component during a random hypergraph process tends to 1 as $\ell$ and $b$ tend to $\infty$ with the total number of vertices $n$ such that $\ell = o(\sqrt[3]{\frac{n}{b}})$. Under the same conditions, we also show that the expected number of vertices that ever belong to an $\ell$-component is approximately $12^{1/3} (b-1)^{1/3} \ell^{1/3} n^{2/3}$. As an immediate consequence, it follows that with high probability the largest $\ell$-component during the process is of size $O((b-1)^{1/3} \ell^{1/3} n^{2/3})$. Our results give insight about the size of giant components inside the phase transition of random hypergraphs. | |
| dc.description | Résumé étendu | |
| dc.identifier | https://arxiv.org/abs/cs/0607059 | |
| dc.identifier | http://arxiv.org/abs/cs/0607059 | |
| dc.identifier | Proceedings of The Twelfth Annual International Computing and Combinatorics Conference (COCOON'06) -- Lecture Notes in Computer Science (2006) à paraître | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/113551 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.subject | G.2.1; G.2.2; G.3 | |
| dc.title | Creation and Growth of Components in a Random Hypergraph Process | |
| dc.type | text |