The spread of fire on a random multigraph

DOI10.1017/APR.2019.2MaRDI QIDQ5203890zbMATH OpenOpenAlexWikidataFDO

Authors Christina Goldschmidt, Eleonora Kreačić

Publication date 9 December 2019

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.09898

zbMATH Keywords

differential equations methodKarp-Sipser algorithmrandom multigraphreflected stochastic differential equation

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial probability (60C05) Functional limit theorems; invariance principles (60F17)

Abstract: 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)/no0$ as $noinfty$, with i.i.d. standard exponential edge-lengths. Depending on whether $alpha(n)ggsqrtn$ or $alpha(n)=O(sqrtn)$, we prove that as $noinfty$ 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 ErdH{o}s-R'enyi random graph.

Recommendations

• Forest fire models on configuration random graphs
• Karp-Sipser on random graphs with a fixed degree sequence
• Fighting constrained fires in graphs
• Firefighting on a random geometric graph
• Sparse graphs are not flammable

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• An introduction to stochastic differential equations with reflection
• An invariance principle for semimartingale reflecting Brownian motions in domains with piecewise smooth boundaries
• Differential equation approximations for Markov chains
• Differential equations for random processes and random graphs
• Diffusion processes with boundary conditions
• Enumeration of Labelled Graphs I: 3-Connected Graphs
• How to determine if a random graph with a fixed degree sequence has a giant component
• scientific article; zbMATH DE number 2127742 (Why is no real title available?)
• scientific article; zbMATH DE number 3951715 (Why is no real title available?)
• scientific article; zbMATH DE number 1245556 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 1139976 (Why is no real title available?)
• Karp-Sipser on random graphs with a fixed degree sequence
• Logarithmic combinatorial structures: A probabilistic approach
• Random graphs and complex networks. Volume 1
• The asymptotic connectivity of labelled regular graphs
• The asymptotic distribution of short cycles in random regular graphs
• The asymptotic number of labeled graphs with given degree sequences

Cited in

(3)

• Forest fire model on configuration graphs with random node degree distribution
• Forest fire models on configuration random graphs
• The critical Karp-Sipser core of random graphs

This page was built for publication: The spread of fire on a random multigraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5203890)