{
  "id": "0907.4083",
  "version": "v1",
  "published": "2009-07-23T14:49:46.000Z",
  "updated": "2009-07-23T14:49:46.000Z",
  "title": "Embedding into bipartite graphs",
  "authors": [
    "Julia Böttcher",
    "Peter Christian Heinig",
    "Anusch Taraz"
  ],
  "comment": "16 pages, 2 figures",
  "journal": "SIAM J. Discrete Math. 24(4) (2010), 1215--1233",
  "doi": "10.1137/090765481",
  "categories": [
    "math.CO"
  ],
  "abstract": "The conjecture of Bollob\\'as and Koml\\'os, recently proved by B\\\"ottcher, Schacht, and Taraz [Math. Ann. 343(1), 175--205, 2009], implies that for any $\\gamma>0$, every balanced bipartite graph on $2n$ vertices with bounded degree and sublinear bandwidth appears as a subgraph of any $2n$-vertex graph $G$ with minimum degree $(1+\\gamma)n$, provided that $n$ is sufficiently large. We show that this threshold can be cut in half to an essentially best-possible minimum degree of $(\\frac12+\\gamma)n$ when we have the additional structural information of the host graph $G$ being balanced bipartite. This complements results of Zhao [to appear in SIAM J. Discrete Math.], as well as Hladk\\'y and Schacht [to appear in SIAM J. Discrete Math.], who determined a corresponding minimum degree threshold for $K_{r,s}$-factors, with $r$ and $s$ fixed. Moreover, it implies that the set of Hamilton cycles of $G$ is a generating system for its cycle space.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-07-23T14:49:46.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D40",
      "05C35"
    ],
    "keywords": [
      "bipartite graph",
      "discrete math",
      "corresponding minimum degree threshold",
      "balanced bipartite",
      "sublinear bandwidth appears"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0907.4083B"
    }
  }
}