Critical Conditions for the Coverage of Complete Graphs with the Frog Model

We consider a system of interacting random walks known as the frog model. Let Kₙ=(Vₙ,Eₙ) be the complete graph with n vertices and oₙ be a special vertex called the root. Initially, 1+ηₒ active particles are placed at the root and ηᵥ inactive particles are placed at each other vertex vₙ\, where \ηᵥ∈ Vₙ are i.i.d. random variables. At each instant of time, each active particle may die with probability $1-p$. Every active particle performs a simple random walk on Kₙ until the moment it dies, activating all inactive particles it hits along its path. Let V_∞(Kₙ,p) be the total number of visited vertices by some active particle up to the end of the process, after all active particles have died. In this paper, we show that V_∞(Kₙ,pₙ)≥ (1-ε)n with high probability for any fixed ε>0 whenever pₙ→ 1. Furthermore, we establish the critical growth rate of pₙ so that all vertices are visited. Specifically, we show that if pₙ=1-α/log n, then V_∞(Kₙ,pₙ)=n with high probability whenever 0<α<E(η) and V_∞(Kₙ,pₙ)<n with high probability whenever α>E(η).