The spread of fire on a random multigraph
We study a model for the destruction of a random network by fire. Suppose that we are given a multigraph of minimum degree at least 2 having real-valued edge-lengths. We pick a uniform point from along the length and set it alight; the edges of the multigraph burn at speed 1. If the fire reaches a v...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
Applied Probability Trust
2019
|
| _version_ | 1797058315653480448 |
|---|---|
| author | Goldschmidt, C Kreačić, E |
| author_facet | Goldschmidt, C Kreačić, E |
| author_sort | Goldschmidt, C |
| collection | OXFORD |
| description | We study a model for the destruction of a random network by fire. Suppose that we are given a multigraph of minimum degree at least 2 having real-valued edge-lengths. We pick a uniform point from along the length and set it alight; the edges of the multigraph burn at speed 1. If the fire reaches a vertex of degree 2, the fire gets directly passed on to the neighbouring edge; a vertex of degree at least 3, however, passes the fire either to all of its neighbours or none, each with probability $1/2$. If the fire goes out before the whole network is burnt, we again set fire to a uniform point. We are interested in the number of fires which must be set in order to burn the whole network, and the number of points which are burnt from two different directions. We analyse these quantities for a random multigraph having $n$ vertices of degree 3 and $\alpha(n)$ vertices of degree 4, where $\alpha(n)/n \to 0$ as $n \to \infty$, with i.i.d. standard exponential edge-lengths. Depending on whether $\alpha(n) \gg \sqrt{n}$ or $\alpha(n)=O(\sqrt{n})$, we prove that as $n \to \infty$ these quantities converge jointly in distribution when suitably rescaled to either a pair of constants or to (complicated) functionals of Brownian motion. We use our analysis of this model to make progress towards a conjecture of Aronson, Frieze and Pittel concerning the number of vertices which remain unmatched when we use the Karp-Sipser algorithm to find a matching on the Erd\H{o}s-R\'enyi random graph. |
| first_indexed | 2024-03-06T19:48:45Z |
| format | Journal article |
| id | oxford-uuid:233ee410-e42c-48b7-9a29-20ab25bac481 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T19:48:45Z |
| publishDate | 2019 |
| publisher | Applied Probability Trust |
| record_format | dspace |
| spelling | oxford-uuid:233ee410-e42c-48b7-9a29-20ab25bac4812022-03-26T11:43:19ZThe spread of fire on a random multigraphJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:233ee410-e42c-48b7-9a29-20ab25bac481Symplectic Elements at OxfordApplied Probability Trust2019Goldschmidt, CKreačić, EWe study a model for the destruction of a random network by fire. Suppose that we are given a multigraph of minimum degree at least 2 having real-valued edge-lengths. We pick a uniform point from along the length and set it alight; the edges of the multigraph burn at speed 1. If the fire reaches a vertex of degree 2, the fire gets directly passed on to the neighbouring edge; a vertex of degree at least 3, however, passes the fire either to all of its neighbours or none, each with probability $1/2$. If the fire goes out before the whole network is burnt, we again set fire to a uniform point. We are interested in the number of fires which must be set in order to burn the whole network, and the number of points which are burnt from two different directions. We analyse these quantities for a random multigraph having $n$ vertices of degree 3 and $\alpha(n)$ vertices of degree 4, where $\alpha(n)/n \to 0$ as $n \to \infty$, with i.i.d. standard exponential edge-lengths. Depending on whether $\alpha(n) \gg \sqrt{n}$ or $\alpha(n)=O(\sqrt{n})$, we prove that as $n \to \infty$ these quantities converge jointly in distribution when suitably rescaled to either a pair of constants or to (complicated) functionals of Brownian motion. We use our analysis of this model to make progress towards a conjecture of Aronson, Frieze and Pittel concerning the number of vertices which remain unmatched when we use the Karp-Sipser algorithm to find a matching on the Erd\H{o}s-R\'enyi random graph. |
| spellingShingle | Goldschmidt, C Kreačić, E The spread of fire on a random multigraph |
| title | The spread of fire on a random multigraph |
| title_full | The spread of fire on a random multigraph |
| title_fullStr | The spread of fire on a random multigraph |
| title_full_unstemmed | The spread of fire on a random multigraph |
| title_short | The spread of fire on a random multigraph |
| title_sort | spread of fire on a random multigraph |
| work_keys_str_mv | AT goldschmidtc thespreadoffireonarandommultigraph AT kreacice thespreadoffireonarandommultigraph AT goldschmidtc spreadoffireonarandommultigraph AT kreacice spreadoffireonarandommultigraph |