Sampling 3-colourings of regular bipartite graphs.

Galvin, David J.

Displaying similar documents to “Sampling 3-colourings of regular bipartite graphs.”

Threshold functions for the bipartite Turán property.

Godbole, Anant P., Lamorte, Ben, Sandquist, Erik Jonathan (1997)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Mixing time for the Ising model : a uniform lower bound for all graphs

Jian Ding, Yuval Peres (2011)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

Consider Glauber dynamics for the Ising model on a graph of vertices. Hayes and Sinclair showed that the mixing time for this dynamics is at least log /(), where is the maximum degree and () = (log2). Their result applies to more general spin systems, and in that generality, they showed that some dependence on is necessary. In this paper, we focus on the ferromagnetic Ising model and prove that the mixing time of Glauber dynamics on any -vertex graph is at least (1/4 + o(1))log . ...