A Random Graph Growth Model
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910347041964032 |
|---|---|
| author | Farber, Michael Gnedin, Alexander Mannan, Wajid |
| author_facet | Farber, Michael Gnedin, Alexander Mannan, Wajid |
| contents | A growing random graph is constructed by successively sampling without replacement an element from the pool of virtual vertices and edges. At start of the process the pool contains $N$ virtual vertices and no edges. Each time a vertex is sampled and occupied, the edges linking the vertex to previously occupied vertices are added to the pool of virtual elements. We focus on the edge-counting at times when the graph has $n\leq N$ occupied vertices. Two different Poisson limits are identified for $n\asymp N^{1/3}$ and $N-n\asymp 1$. For the bulk of the process, when $n\asymp N$, the scaled number of edges is shown to fluctuate about a deterministic curve, with fluctuations being of the order of $N^{3/2}$ and approximable by a Gaussian bridge. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_07809 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Random Graph Growth Model Farber, Michael Gnedin, Alexander Mannan, Wajid Probability Combinatorics 05C80, 60B20 A growing random graph is constructed by successively sampling without replacement an element from the pool of virtual vertices and edges. At start of the process the pool contains $N$ virtual vertices and no edges. Each time a vertex is sampled and occupied, the edges linking the vertex to previously occupied vertices are added to the pool of virtual elements. We focus on the edge-counting at times when the graph has $n\leq N$ occupied vertices. Two different Poisson limits are identified for $n\asymp N^{1/3}$ and $N-n\asymp 1$. For the bulk of the process, when $n\asymp N$, the scaled number of edges is shown to fluctuate about a deterministic curve, with fluctuations being of the order of $N^{3/2}$ and approximable by a Gaussian bridge. |
| title | A Random Graph Growth Model |
| topic | Probability Combinatorics 05C80, 60B20 |
| url | https://arxiv.org/abs/2301.07809 |