A simple branching process approach to the phase transition in $G_{n,p}$
It is well known that the branching process approach to the study of the random graph $G_{n,p}$ gives a very simple way of understanding the size of the giant component when it is fairly large (of order $\Theta(n)$). Here we show that a variant of this approach works all the way down to the phase tr...
| Główni autorzy: | , |
|---|---|
| Format: | Journal article |
| Język: | English |
| Wydane: |
2012
|
| _version_ | 1826260183546855424 |
|---|---|
| author | Bollobas, B Riordan, O |
| author_facet | Bollobas, B Riordan, O |
| author_sort | Bollobas, B |
| collection | OXFORD |
| description | It is well known that the branching process approach to the study of the random graph $G_{n,p}$ gives a very simple way of understanding the size of the giant component when it is fairly large (of order $\Theta(n)$). Here we show that a variant of this approach works all the way down to the phase transition: we use branching process arguments to give a simple new derivation of the asymptotic size of the largest component whenever $(np-1)^3n\to\infty$. |
| first_indexed | 2024-03-06T19:01:36Z |
| format | Journal article |
| id | oxford-uuid:13b7e4a0-c4f3-43ed-96d6-01bd06cf26b9 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T19:01:36Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | oxford-uuid:13b7e4a0-c4f3-43ed-96d6-01bd06cf26b92022-03-26T10:15:27ZA simple branching process approach to the phase transition in $G_{n,p}$Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:13b7e4a0-c4f3-43ed-96d6-01bd06cf26b9EnglishSymplectic Elements at Oxford2012Bollobas, BRiordan, OIt is well known that the branching process approach to the study of the random graph $G_{n,p}$ gives a very simple way of understanding the size of the giant component when it is fairly large (of order $\Theta(n)$). Here we show that a variant of this approach works all the way down to the phase transition: we use branching process arguments to give a simple new derivation of the asymptotic size of the largest component whenever $(np-1)^3n\to\infty$. |
| spellingShingle | Bollobas, B Riordan, O A simple branching process approach to the phase transition in $G_{n,p}$ |
| title | A simple branching process approach to the phase transition in $G_{n,p}$ |
| title_full | A simple branching process approach to the phase transition in $G_{n,p}$ |
| title_fullStr | A simple branching process approach to the phase transition in $G_{n,p}$ |
| title_full_unstemmed | A simple branching process approach to the phase transition in $G_{n,p}$ |
| title_short | A simple branching process approach to the phase transition in $G_{n,p}$ |
| title_sort | simple branching process approach to the phase transition in g n p |
| work_keys_str_mv | AT bollobasb asimplebranchingprocessapproachtothephasetransitioningnp AT riordano asimplebranchingprocessapproachtothephasetransitioningnp AT bollobasb simplebranchingprocessapproachtothephasetransitioningnp AT riordano simplebranchingprocessapproachtothephasetransitioningnp |