{
  "id": "1610.01276",
  "version": "v1",
  "published": "2016-10-05T05:48:38.000Z",
  "updated": "2016-10-05T05:48:38.000Z",
  "title": "On the Cycle Space of a Random Graph",
  "authors": [
    "Jacob D. Baron",
    "Jeff Kahn"
  ],
  "comment": "38 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Write $\\mathcal{C}(G)$ for the cycle space of a graph $G$, $\\mathcal{C}_\\kappa(G)$ for the subspace of $\\mathcal{C}(G)$ spanned by the copies of the $\\kappa$-cycle $C_\\kappa$ in $G$, $\\mathcal{T}_\\kappa$ for the class of graphs satisfying $\\mathcal{C}_\\kappa(G)=\\mathcal{C}(G)$, and $\\mathcal{Q}_\\kappa$ for the class of graphs each of whose edges lies in a $C_\\kappa$. We prove that for every odd $\\kappa \\geq 3$ and $G=G_{n,p}$, \\[\\max_p \\, \\Pr(G \\in \\mathcal{Q}_\\kappa \\setminus \\mathcal{T}_\\kappa) \\rightarrow 0;\\] so the $C_\\kappa$'s of a random graph span its cycle space as soon as they cover its edges. For $\\kappa=3$ this was shown by DeMarco, Hamm and Kahn (2013).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-10-05T05:48:38.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05C38",
      "05D40"
    ],
    "keywords": [
      "cycle space",
      "random graph span",
      "edges lies"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 38,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}