{
  "id": "1503.09175",
  "version": "v1",
  "published": "2015-03-31T19:34:55.000Z",
  "updated": "2015-03-31T19:34:55.000Z",
  "title": "Bipartite Kneser graphs are Hamiltonian",
  "authors": [
    "Torsten Mütze",
    "Pascal Su"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The Kneser graph $K(n,k)$ has as vertices all $k$-element subsets of $[n]:=\\{1,2,\\ldots,n\\}$ and an edge between any two vertices (=sets) that are disjoint. The bipartite Kneser graph $H(n,k)$ has as vertices all $k$-element and $(n-k)$-element subsets of $[n]$ and an edge between any two vertices where one is a subset of the other. It has long been conjectured that all connected Kneser graphs and bipartite Kneser graphs (apart from few trivial exceptions) have a Hamilton cycle. The main contribution of this paper is proving this conjecture for bipartite Kneser graphs. We also establish the existence of long cycles in Kneser graphs (visiting almost all vertices), generalizing and improving upon previous results on this problem.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-03-31T19:34:55.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bipartite kneser graph",
      "hamiltonian",
      "element subsets",
      "connected kneser graphs",
      "trivial exceptions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150309175M"
    }
  }
}