{
  "id": "1206.3165",
  "version": "v1",
  "published": "2012-06-14T16:20:38.000Z",
  "updated": "2012-06-14T16:20:38.000Z",
  "title": "Slow mixing of Glauber Dynamics for the hard-core model on regular bipartite graphs",
  "authors": [
    "David Galvin",
    "Prasad Tetali"
  ],
  "comment": "18 pages. This paper appeared in Random Structures and Algorithms in 2006, and is an expanded version of the abstract Slow mixing of Glauber dynamics for the hard-core model on the hypercube that appeared in the proceedings of SODA 2004",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Let $\\gS=(V,E)$ be a finite, $d$-regular bipartite graph. For any $\\lambda>0$ let $\\pi_\\lambda$ be the probability measure on the independent sets of $\\gS$ in which the set $I$ is chosen with probability proportional to $\\lambda^{|I|}$ ($\\pi_\\lambda$ is the {\\em hard-core measure with activity $\\lambda$ on $\\gS$}). We study the Glauber dynamics, or single-site update Markov chain, whose stationary distribution is $\\pi_\\lambda$. We show that when $\\lambda$ is large enough (as a function of $d$ and the expansion of subsets of single-parity of $V$) then the convergence to stationarity is exponentially slow in $|V(\\gS)|$. In particular, if $\\gS$ is the $d$-dimensional hypercube $\\{0,1\\}^d$ we show that for values of $\\lambda$ tending to 0 as $d$ grows, the convergence to stationarity is exponentially slow in the volume of the cube. The proof combines a conductance argument with combinatorial enumeration methods.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-06-14T16:20:38.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68R10",
      "68W25",
      "05C69"
    ],
    "keywords": [
      "regular bipartite graph",
      "glauber dynamics",
      "hard-core model",
      "slow mixing",
      "single-site update markov chain"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1206.3165G"
    }
  }
}