{
  "id": "1702.07342",
  "version": "v1",
  "published": "2017-02-23T18:58:38.000Z",
  "updated": "2017-02-23T18:58:38.000Z",
  "title": "On the inducibility of cycles",
  "authors": [
    "Dan Hefetz",
    "Mykhaylo Tyomkyn"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "In 1975 Pippenger and Golumbic proved that any graph on $n$ vertices admits at most $2e(n/k)^k$ induced $k$-cycles. This bound is larger by a multiplicative factor of $2e$ than the simple lower bound obtained by a blow-up construction. Pippenger and Golumbic conjectured that the latter lower bound is essentially tight. In the present paper we establish a better upper bound of $(128e/81) \\cdot (n/k)^k$. This constitutes the first progress towards proving the aforementioned conjecture since it was posed.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-02-23T18:58:38.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "inducibility",
      "simple lower bound",
      "better upper bound",
      "vertices admits",
      "first progress"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}