{
  "id": "2407.19027",
  "version": "v1",
  "published": "2024-07-26T18:11:25.000Z",
  "updated": "2024-07-26T18:11:25.000Z",
  "title": "Critical Conditions for the Coverage of Complete Graphs with the Frog Model",
  "authors": [
    "Gustavo O. de Carvalho",
    "Fábio P. Machado"
  ],
  "comment": "20 pages",
  "categories": [
    "math.PR"
  ],
  "abstract": "We consider a system of interacting random walks known as the frog model. Let $\\mathcal{K}_n=(\\mathcal{V}_n,\\mathcal{E}_n)$ be the complete graph with $n$ vertices and $o\\in\\mathcal{V}_n$ be a special vertex called the root. Initially, $1+\\eta_o$ active particles are placed at the root and $\\eta_v$ inactive particles are placed at each other vertex $v\\in\\mathcal{V}_n\\setminus\\{o\\}$, where $\\{\\eta_v\\}_{v\\in \\mathcal{V}_n}$ 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 $\\mathcal{K}_n$ until the moment it dies, activating all inactive particles it hits along its path. Let $V_\\infty(\\mathcal{K}_n,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_\\infty(\\mathcal{K}_n,p_n)\\geq (1-\\epsilon)n$ with high probability for any fixed $\\epsilon>0$ whenever $p_n\\rightarrow 1$. Furthermore, we establish the critical growth rate of $p_n$ so that all vertices are visited. Specifically, we show that if $p_n=1-\\frac{\\alpha}{\\log n}$, then $V_\\infty(\\mathcal{K}_n,p_n)=n$ with high probability whenever $0<\\alpha<E(\\eta)$ and $V_\\infty(\\mathcal{K}_n,p_n)<n$ with high probability whenever $\\alpha>E(\\eta)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-07-26T18:11:25.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60K35",
      "05C81"
    ],
    "keywords": [
      "frog model",
      "complete graph",
      "critical conditions",
      "high probability",
      "inactive particles"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}