{
  "id": "2007.04351",
  "version": "v1",
  "published": "2020-07-08T18:12:11.000Z",
  "updated": "2020-07-08T18:12:11.000Z",
  "title": "Tuza's Conjecture for random graphs",
  "authors": [
    "Jeff Kahn",
    "Jinyoung Park"
  ],
  "comment": "13 pages including references and appendix, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "A celebrated conjecture of Zs. Tuza says that in any (finite) graph, the minimum size of a cover of triangles by edges is at most twice the maximum size of a set of edge-disjoint triangles. Resolving a recent question of Bennett, Dudek, and Zerbib, we show that this is true for random graphs; more precisely: \\[ \\mbox{for any $p=p(n)$, $\\mathbb P(\\mbox{$G_{n,p}$ satisfies Tuza's Conjecture})\\rightarrow 1 $ (as $n\\rightarrow\\infty$).} \\]",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-07-08T18:12:11.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random graphs",
      "tuzas conjecture",
      "tuza says",
      "edge-disjoint triangles",
      "celebrated conjecture"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}