{
  "id": "1005.0895",
  "version": "v4",
  "published": "2010-05-06T06:30:49.000Z",
  "updated": "2012-03-06T00:35:44.000Z",
  "title": "Small Minors in Dense Graphs",
  "authors": [
    "Samuel Fiorini",
    "Gwenaël Joret",
    "Dirk Oliver Theis",
    "David R. Wood"
  ],
  "journal": "European Journal of Combinatorics, 33/6:1226--1245, 2012",
  "doi": "10.1016/j.ejc.2012.02.003",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "A fundamental result in structural graph theory states that every graph with large average degree contains a large complete graph as a minor. We prove this result with the extra property that the minor is small with respect to the order of the whole graph. More precisely, we describe functions $f$ and $h$ such that every graph with $n$ vertices and average degree at least $f(t)$ contains a $K_t$-model with at most $h(t)\\cdot\\log n$ vertices. The logarithmic dependence on $n$ is best possible (for fixed $t$). In general, we prove that $f(t)\\leq 2^{t-1}+\\eps$. For $t\\leq 4$, we determine the least value of $f(t)$; in particular $f(3)=2+\\eps$ and $f(4)=4+\\eps$. For $t\\leq4$, we establish similar results for graphs embedded on surfaces, where the size of the $K_t$-model is bounded (for fixed $t$).",
  "revisions": [
    {
      "version": "v4",
      "updated": "2012-03-06T00:35:44.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C83",
      "05C35"
    ],
    "keywords": [
      "dense graphs",
      "small minors",
      "structural graph theory states",
      "large average degree contains",
      "large complete graph"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1005.0895F"
    }
  }
}