{
  "id": "1412.1838",
  "version": "v1",
  "published": "2014-12-04T21:03:43.000Z",
  "updated": "2014-12-04T21:03:43.000Z",
  "title": "A note on a problem of Erdos and Rothschild",
  "authors": [
    "Aaron Potechin"
  ],
  "comment": "7 pages, 0 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "A set of $q$ triangles sharing a common edge is a called a book of size $q$. Letting $bk(G)$ denote the size of the largest book in a graph $G$, Erd\\H{o}s and Rothschild \\cite{erdostwo} asked what the minimal value of $bk(G)$ is for graphs $G$ with $n$ vertices and a set number of edges where every edge is contained in at least one triangle. In this paper, we show that for any graph $G$ with $n$ vertices and $\\frac{n^2}{4} - nf(n)$ edges where every edge is contained in at least one triangle, $bk(G) \\geq \\Omega\\left(\\min{\\{\\frac{n}{\\sqrt{f(n)}}, \\frac{n^2}{f(n)^2}\\}}\\right)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-12-04T21:03:43.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "rothschild",
      "common edge",
      "largest book",
      "minimal value",
      "set number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 7,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1412.1838P"
    }
  }
}