{
  "id": "1810.02041",
  "version": "v1",
  "published": "2018-10-04T03:39:49.000Z",
  "updated": "2018-10-04T03:39:49.000Z",
  "title": "On connectivity, conductance and bootstrap percolation for a random k-out, age-biased graph",
  "authors": [
    "Hüseyin Acan",
    "Boris Pittel"
  ],
  "comment": "27 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A uniform attachment graph (with parameter $k$), denoted $G_{n,k}$ in the paper, is a random graph on the vertex set $[n]$, where each vertex $v$ makes $k$ selections from $[v-1]$ uniformly and independently, and these selections determine the edge set. We study several aspects of this graph. Our motivation comes from two similarly constructed, well-studied random graphs: $k$-out graphs and preferential attachment graphs. In this paper, we find the asymptotic distribution of its minimum degree and connectivity, and study the expansion properties of $G_{n,k}$ to show that the conductance of $G_{n,k}$ is of order $(\\log n)^{-1}$. We also study the bootstrap percolation on $G_{n,k}$, where $r$ infected neighbors infect a vertex, and show that $(\\log n)^{-r/(r-1)}$ is a threshold probability of initial infection for the spread of the disease to the whole vertex set.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-10-04T03:39:49.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80"
    ],
    "keywords": [
      "bootstrap percolation",
      "random k-out",
      "age-biased graph",
      "connectivity",
      "conductance"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 27,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}