{
  "id": "1312.0732",
  "version": "v1",
  "published": "2013-12-03T08:53:16.000Z",
  "updated": "2013-12-03T08:53:16.000Z",
  "title": "Random Subgraphs in Sparse Graphs",
  "authors": [
    "Felix Joos"
  ],
  "comment": "14 pages",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "We investigate the threshold probability for connectivity of sparse graphs under weak assumptions. As a corollary this completely solve the problem for Cartesian powers of arbitrary graphs. In detail, let $G$ be a connected graph on $k$ vertices, $G^n$ the $n$-th Cartesian power of $G$, $\\alpha_i$ be the number of vertices of degree $i$ of $G$, $\\lambda$ be a positive real number, and $G^n_p$ be the graph obtained from $G^n$ by deleting every edge independently with probability $1-p$. If $\\sum_{i}\\alpha_i(1-p)^i=\\lambda^{\\frac{1}{n}}$, then $\\lim_{n\\rightarrow \\infty}\\mathbb{P}[G^n_p {\\rm\\ is\\ connected}]=\\exp(-\\lambda)$. This result extends known results for regular graphs. The main result implies that the threshold probability does not depend on the graph structure of $G$ itself, but only on the degree sequence of the graph.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-12-03T08:53:16.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "sparse graphs",
      "random subgraphs",
      "threshold probability",
      "th cartesian power",
      "main result implies"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1312.0732J"
    }
  }
}