Critical random graphs: limiting constructions and distributional properties
We consider the Erdo{double acute}s-Rényi random graph G(n, p) inside the critical window, where p = 1/n + λn-4/3 for some λ ∈ R. We proved in Addario-Berry et al. [2009+] that considering the connected components of G(n, p) as a sequence of metric spaces with the graph distance rescaled by n-1/3 an...
| Үндсэн зохиолчид: | , , |
|---|---|
| Формат: | Journal article |
| Хэл сонгох: | English |
| Хэвлэсэн: |
2010
|
| _version_ | 1826269290172514304 |
|---|---|
| author | Addario-Berry, L Broutin, N Goldschmidt, C |
| author_facet | Addario-Berry, L Broutin, N Goldschmidt, C |
| author_sort | Addario-Berry, L |
| collection | OXFORD |
| description | We consider the Erdo{double acute}s-Rényi random graph G(n, p) inside the critical window, where p = 1/n + λn-4/3 for some λ ∈ R. We proved in Addario-Berry et al. [2009+] that considering the connected components of G(n, p) as a sequence of metric spaces with the graph distance rescaled by n-1/3 and letting n → ∞ yields a non-trivial sequence of limit metric spaces C =(C1,C2,...). These limit metric spaces can be constructed from certain random real trees with vertex-identifications. For a single such metric space, we give here two equivalent constructions, both of which are in terms of more standard probabilistic objects. The first is a global construction using Dirichlet random variables and Aldous' Brownian continuum random tree. The second is a recursive construction from an inhomogeneous Poisson point process on R+. These constructions allow us to characterize the distributions of the masses and lengths in the constituent parts of a limit component when it is decomposed according to its cycle structure. In particular, this strengthens results of Łuczak et al. [1994] by providing precise distributional convergence for the lengths of paths between kernel vertices and the length of a shortest cycle, within any fixed limit component. |
| first_indexed | 2024-03-06T21:22:45Z |
| format | Journal article |
| id | oxford-uuid:42075aee-d27b-4fc3-b7d2-c2153e8b6f1a |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T21:22:45Z |
| publishDate | 2010 |
| record_format | dspace |
| spelling | oxford-uuid:42075aee-d27b-4fc3-b7d2-c2153e8b6f1a2022-03-26T14:47:10ZCritical random graphs: limiting constructions and distributional propertiesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:42075aee-d27b-4fc3-b7d2-c2153e8b6f1aEnglishSymplectic Elements at Oxford2010Addario-Berry, LBroutin, NGoldschmidt, CWe consider the Erdo{double acute}s-Rényi random graph G(n, p) inside the critical window, where p = 1/n + λn-4/3 for some λ ∈ R. We proved in Addario-Berry et al. [2009+] that considering the connected components of G(n, p) as a sequence of metric spaces with the graph distance rescaled by n-1/3 and letting n → ∞ yields a non-trivial sequence of limit metric spaces C =(C1,C2,...). These limit metric spaces can be constructed from certain random real trees with vertex-identifications. For a single such metric space, we give here two equivalent constructions, both of which are in terms of more standard probabilistic objects. The first is a global construction using Dirichlet random variables and Aldous' Brownian continuum random tree. The second is a recursive construction from an inhomogeneous Poisson point process on R+. These constructions allow us to characterize the distributions of the masses and lengths in the constituent parts of a limit component when it is decomposed according to its cycle structure. In particular, this strengthens results of Łuczak et al. [1994] by providing precise distributional convergence for the lengths of paths between kernel vertices and the length of a shortest cycle, within any fixed limit component. |
| spellingShingle | Addario-Berry, L Broutin, N Goldschmidt, C Critical random graphs: limiting constructions and distributional properties |
| title | Critical random graphs: limiting constructions and distributional properties |
| title_full | Critical random graphs: limiting constructions and distributional properties |
| title_fullStr | Critical random graphs: limiting constructions and distributional properties |
| title_full_unstemmed | Critical random graphs: limiting constructions and distributional properties |
| title_short | Critical random graphs: limiting constructions and distributional properties |
| title_sort | critical random graphs limiting constructions and distributional properties |
| work_keys_str_mv | AT addarioberryl criticalrandomgraphslimitingconstructionsanddistributionalproperties AT broutinn criticalrandomgraphslimitingconstructionsanddistributionalproperties AT goldschmidtc criticalrandomgraphslimitingconstructionsanddistributionalproperties |