{
  "id": "1605.07791",
  "version": "v1",
  "published": "2016-05-25T09:18:56.000Z",
  "updated": "2016-05-25T09:18:56.000Z",
  "title": "A proof of Mader's conjecture on large clique subdivisions in $C_4$-free graphs",
  "authors": [
    "Hong Liu",
    "Richard Montgomery"
  ],
  "comment": "25 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "Given any integers $s,t\\geq 2$, we show there exists some $c=c(s,t)>0$ such that any $K_{s,t}$-free graph with average degree $d$ contains a subdivision of a clique with at least $cd^{\\frac{1}{2}\\frac{s}{s-1}}$ vertices. In particular, when $s=2$ this resolves in a strong sense the conjecture of Mader in 1999 that every $C_4$-free graph has a subdivision of a clique with order linear in the average degree of the original graph. In general, the widely conjectured asymptotic behaviour of the extremal density of $K_{s,t}$-free graphs suggests our result is tight up to the constant $c(s,t)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-05-25T09:18:56.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "free graph",
      "large clique subdivisions",
      "maders conjecture",
      "average degree",
      "extremal density"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}