{
  "id": "2102.10912",
  "version": "v1",
  "published": "2021-02-22T11:29:17.000Z",
  "updated": "2021-02-22T11:29:17.000Z",
  "title": "Powers of Hamilton cycles of high discrepancy are unavoidable",
  "authors": [
    "Domagoj Bradač"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The P\\'osa-Seymour conjecture asserts that every graph on $n$ vertices with minimum degree at least $(1 - 1/(r+1))n$ contains the $r^{th}$ power of a Hamilton cycle. Koml\\'os, S\\'ark\\\"ozy and Szemer\\'edi famously proved the conjecture for large $n.$ The notion of discrepancy appears in many areas of mathematics, including graph theory. In this setting, a graph $G$ is given along with a $2$-coloring of its edges. One is then asked to find in $G$ a copy of a given subgraph with a large discrepancy, i.e., with many more edges in one of the colors. For $r \\geq 2,$ we determine the minimum degree threshold needed to find the $r^{th}$ power of a Hamilton cycle of large discrepancy, answering a question posed by Balogh, Csaba, Pluh\\'ar and Treglown. Notably, for $r \\geq 3,$ this threshold approximately matches the minimum degree requirement of the P\\'osa-Seymour conjecture.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-02-22T11:29:17.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "hamilton cycle",
      "high discrepancy",
      "large discrepancy",
      "posa-seymour conjecture asserts",
      "minimum degree threshold"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}