{
  "id": "1206.3202",
  "version": "v1",
  "published": "2012-06-14T18:02:16.000Z",
  "updated": "2012-06-14T18:02:16.000Z",
  "title": "Sampling 3-colourings of regular bipartite graphs",
  "authors": [
    "David Galvin"
  ],
  "comment": "19 pages. Appeared in Electronic Journal of Probability in 2007",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "We show that if $\\gS=(V,E)$ is a regular bipartite graph for which the expansion of subsets of a single parity of $V$ is reasonably good and which satisfies a certain local condition (that the union of the neighbourhoods of adjacent vertices does not contain too many pairwise non-adjacent vertices), and if $\\cM$ is a Markov chain on the set of proper 3-colourings of $\\gS$ which updates the colour of at most $\\rho|V|$ vertices at each step and whose stationary distribution is uniform, then for $\\rho \\approx .22$ and $d$ sufficiently large the convergence to stationarity of $\\cM$ is (essentially) exponential in $|V|$. In particular, if $\\gS$ is the $d$-dimensional hypercube $Q_d$ (the graph on vertex set $\\{0,1\\}^d$ in which two strings are adjacent if they differ on exactly one coordinate) then the convergence to stationarity of the well-known Glauber (single-site update) dynamics is exponentially slow in $2^d/(\\sqrt{d}\\log d)$. A combinatorial corollary of our main result is that in a uniform 3-colouring of $Q_d$ there is an exponentially small probability (in $2^d$) that there is a colour $i$ such the proportion of vertices of the even subcube coloured $i$ differs from the proportion of the odd subcube coloured $i$ by at most $.22$. Our proof combines a conductance argument with combinatorial enumeration methods.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-06-14T18:02:16.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "82B20"
    ],
    "keywords": [
      "regular bipartite graph",
      "combinatorial enumeration methods",
      "pairwise non-adjacent vertices",
      "markov chain",
      "single parity"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1206.3202G"
    }
  }
}