Cover time for the frog model on trees

DOI10.1017/FMS.2019.37MaRDI QIDQ5243131zbMATH OpenOpenAlexWikidataFDO

Authors Tobias Johnson, Matthew Junge, Christopher Hoffman

Publication date 14 November 2019

Published in Forum of Mathematics, Sigma (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

branching random walkfrog model

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: The frog model is a branching random walk on a graph in which particles branch only at unvisited sites. Consider an initial particle density of $mu$ on the full $d$-ary tree of height $n$. If $mu=Omega(d^2)$, all of the vertices are visited in time $Theta(nlogn)$ with high probability. Conversely, if $mu=O(d)$ the cover time is $exp(Theta(sqrtn))$ with high probability.

Recommendations

• Frogs on trees?
• Recurrence and transience for the frog model on trees
• Cover time for branching random walks on regular trees
• Infection spread for the frog model on trees
• An improved upper bound for the critical probability of the frog model on homogeneous trees

Cites work

• A zero-one law for recurrence and transience of frog processes
• Frogs on trees?
• From transience to recurrence with Poisson tree frogs
• scientific article; zbMATH DE number 1740398 (Why is no real title available?)
• Infection spread for the frog model on trees
• On an epidemic model on finite graphs
• Probability on trees and networks
• Random walk covering of some special trees
• Random walks and the effective resistance of networks
• Rapid social connectivity
• Recurrence and transience for the frog model on trees
• Stochastic orders and the frog model
• The critical density for the frog model is the degree of the tree
• The social network model on infinite graphs
• Universality and sharpness in activated random walks

Cited in

(10)

• Frogs on trees?
• Brownian snails with removal: epidemics in diffusing populations
• Infection spread for the frog model on trees
• Frog model wakeup time on the complete graph
• Laws of large numbers for the frog model on the complete graph
• The coverage ratio of the frog model on complete graphs
• Explosion and non-explosion for the continuous-time frog model
• Critical conditions for the coverage of complete graphs with the frog model
• Dissipative particle systems on expanders
• The critical density for the frog model is the degree of the tree

This page was built for publication: Cover time for the frog model on trees

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