An old approach to the giant component problem
In 1998, Molloy and Reed showed that, under suitable conditions, if a sequence of degree sequences converges to a probability distribution $D$, then the size of the largest component in corresponding $n$-vertex random graph is asymptotically $\rho(D)n$, where $\rho(D)$ is a constant defined by the s...
| Автори: | , |
|---|---|
| Формат: | Journal article |
| Опубліковано: |
2012
|
| _version_ | 1826271560862793728 |
|---|---|
| author | Bollobas, B Riordan, O |
| author_facet | Bollobas, B Riordan, O |
| author_sort | Bollobas, B |
| collection | OXFORD |
| description | In 1998, Molloy and Reed showed that, under suitable conditions, if a sequence of degree sequences converges to a probability distribution $D$, then the size of the largest component in corresponding $n$-vertex random graph is asymptotically $\rho(D)n$, where $\rho(D)$ is a constant defined by the solution to certain equations that can be interpreted as the survival probability of a branching process associated to $D$. There have been a number of papers strengthening this result in various ways; here we prove a strong form of the result (with exponential bounds on the probability of large deviations) under minimal conditions. |
| first_indexed | 2024-03-06T21:58:35Z |
| format | Journal article |
| id | oxford-uuid:4dcc3a95-ccb0-4947-b5aa-0c206589f98a |
| institution | University of Oxford |
| last_indexed | 2024-03-06T21:58:35Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | oxford-uuid:4dcc3a95-ccb0-4947-b5aa-0c206589f98a2022-03-26T15:57:36ZAn old approach to the giant component problemJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:4dcc3a95-ccb0-4947-b5aa-0c206589f98aSymplectic Elements at Oxford2012Bollobas, BRiordan, OIn 1998, Molloy and Reed showed that, under suitable conditions, if a sequence of degree sequences converges to a probability distribution $D$, then the size of the largest component in corresponding $n$-vertex random graph is asymptotically $\rho(D)n$, where $\rho(D)$ is a constant defined by the solution to certain equations that can be interpreted as the survival probability of a branching process associated to $D$. There have been a number of papers strengthening this result in various ways; here we prove a strong form of the result (with exponential bounds on the probability of large deviations) under minimal conditions. |
| spellingShingle | Bollobas, B Riordan, O An old approach to the giant component problem |
| title | An old approach to the giant component problem |
| title_full | An old approach to the giant component problem |
| title_fullStr | An old approach to the giant component problem |
| title_full_unstemmed | An old approach to the giant component problem |
| title_short | An old approach to the giant component problem |
| title_sort | old approach to the giant component problem |
| work_keys_str_mv | AT bollobasb anoldapproachtothegiantcomponentproblem AT riordano anoldapproachtothegiantcomponentproblem AT bollobasb oldapproachtothegiantcomponentproblem AT riordano oldapproachtothegiantcomponentproblem |