Mixing of the Glauber dynamics for the ferromagnetic Potts model

We present several results on the mixing time of the Glauber dynamics for sampling from the Gibbs distribution in the ferromagnetic Potts model. At a fixed temperature and interaction strength, we study the interplay between the maximum degree (Δ) of the underlying graph and the number of colours or spins (q) in determining whether the dynamics mixes rapidly or not. We find a lower bound L on the number of colours such that Glauber dynamics is rapidly mixing if at least L colours are used. We give a closely‐matching upper bound U on the number of colours such that with probability that tends to 1, the Glauber dynamics mixes slowly on random Δ‐regular graphs when at most U colours are used. We show that our bounds can be improved if we restrict attention to certain types of graphs of maximum degree Δ, e.g. toroidal grids for Δ = 4. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 21–52, 2016     

Fast mixing for independent sets,colorings, and other models on trees

We study the mixing time of the Glauber dynamics for general spin systems on the regular tree, including the Ising model, the hard‐core model (independent sets), and the antiferromagnetic Potts model at zero temperature (colorings). We generalize a framework, developed in our recent paper (Martinelli, Sinclair, and Weitz, Tech. Report UCB//CSD‐03‐1256, Dept. of EECS, UC Berkeley, July 2003) in the context of the Ising model, for establishing mixing time O(nlog n), which ties this property closely to phase transitions in the underlying model. We use this framework to obtain rapid mixing results for several models over a significantly wider range of parameter values than previously known, including situations in which the mixing time is strongly dependent on the boundary condition. We also discuss applications of our framework to reconstruction problems on trees. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs

Let ∑ = (V,E) be a finite, d‐regular bipartite graph. For any λ > 0 let π_λ be the probability measure on the independent sets of ∑ in which the set I is chosen with probability proportional to λ^|I| (π_λ is the hard‐core measure with activity λ on ∑). We study the Glauber dynamics, or single‐site update Markov chain, whose stationary distribution is π_λ. We show that when λ 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(∑)|. In particular, if ∑ is the d‐dimensional hypercube {0,1}^d we show that for values of λ 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. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Large deviations for Glauber dynamics of continuous gas

This paper is devoted to the large deviation principles of the Glauber-type dynamics of finite or infinite volume continuous particle systems.We prove that the level-2 empirical process satisfies the large deviation principles in the weak convergence topology,while it does not satisfy the large deviation principles in the T-topology.     

Minimum sum set coloring of trees and line graphs of trees

In this paper, we study the minimum sum set coloring (MSSC) problem which consists in assigning a set of x(v) positive integers to each vertex v of a graph so that the intersection of sets assigned to adjacent vertices is empty and the sum of the assigned set of numbers to each vertex of the graph is minimum. The MSSC problem occurs in two versions: non-preemptive and preemptive. We show that the MSSC problem is strongly NP-hard both in the preemptive case on trees and in the non-preemptive case in line graphs of trees. Finally, we give exact parameterized algorithms for these two versions on trees and line graphs of trees.     

Ergodicity of non-equilibrium Glauber dynamics in continuum

We study asymptotic properties of the continuous Glauber dynamics with unbounded death and constant birth rates. In particular, an information about the location of the spectrum for the symbol of the Markov generator is obtained. The latter fact is used for the proof of the ergodicity of this process. We show that the speed of convergence to the equilibrium is exponential.     

Optimal shift coloring of trees

This paper was motivated by the problem of scheduling the openings of pharmacies during week-ends and holiday periods (shifts). The problem can be modeled as a coloring problem on a graph. In this paper we focus on the special case where the underlying graph is a tree, or, more generally, it is endowed with a tree-metric, and we provide a polynomial-time algorithm. We also provide direct optimal solutions for special trees like stars and paths.     

Quasi‐polynomial mixing of critical two‐dimensional random cluster models

We study the Glauber dynamics for the random cluster (FK) model on the torus with parameters (p,q), for q ∈ (1,4] and p the critical point p_c. The dynamics is believed to undergo a critical slowdown, with its continuous‐time mixing time transitioning from for p ≠ p_c to a power‐law in n at p = p_c. This was verified at p ≠ p_c by Blanca and Sinclair, whereas at the critical p = p_c, with the exception of the special integer points q = 2,3,4 (where the model corresponds to the Ising/Potts models) the best‐known upper bound on mixing was exponential in n. Here we prove an upper bound of at p = p_c for all q ∈ (1,4], where a key ingredient is bounding the number of nested long‐range crossings at criticality.     

Randomly coloring planar graphs with fewer colors than the maximum degree

We study Markov chains for randomly sampling k‐colorings of a graph with maximum degree Δ. Our main result is a polynomial upper bound on the mixing time of the single‐site update chain known as the Glauber dynamics for planar graphs when . Our results can be partially extended to the more general case where the maximum eigenvalue of the adjacency matrix of the graph is at most , for fixed . The main challenge when is the possibility of “frozen” vertices, that is, vertices for which only one color is possible, conditioned on the colors of its neighbors. Indeed, when , even a typical coloring can have a constant fraction of the vertices frozen. Our proofs rely on recent advances in techniques for bounding mixing time using “local uniformity” properties. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 731–759, 2015     

Scaling limit of fluctuations for the equilibrium Glauber dynamics in continuum

The Glauber dynamics investigated in this paper are spatial birth and death processes in a continuous system having a grand canonical Gibbs measure of Ruelle type as an invariant measure. We prove that such processes, when appropriately scaled, have as scaling limit a generalized Ornstein-Uhlenbeck process. First we prove convergence of the corresponding Dirichlet forms. This convergence requires only very weak assumptions. The interaction potential ? only has to be stable (S), integrable (I), and we have to assume the low activity high temperature regime. Under a slightly stronger integrability condition (I_∞) and a conjecture on the Percus-Yevick equation we even can prove strong convergence of the corresponding generators. Finally, we prove that the scaled processes converge in law. Here the hardest part is to show tightness of the scaled processes (note that the processes only have càdlàg sample path). For the proof we have to assume that the interaction potential is positive (P). The limiting process then is identified via the associated martingale problem. For this the above mentioned strong convergence of generators is essential.     

Strong spatial mixing of list coloring of graphs

The property of spatial mixing and strong spatial mixing in spin systems has been of interest because of its implications on uniqueness of Gibbs measures on infinite graphs and efficient approximation of counting problems that are otherwise known to be #P hard. In the context of coloring, strong spatial mixing has been established for Kelly trees in (Ge and Stefankovic, arXiv:1102.2886v3 (2011)) when where q the number of colors, Δ is the degree and .. is the unique solution to . It has also been established in (Goldberg et al., SICOMP 35 (2005) 486–517) for bounded degree lattice graphs whenever for some constant β, where Δ is the maximum vertex degree of the graph. We establish strong spatial mixing for a more general problem, namely list coloring, for arbitrary bounded degree triangle‐free graphs. Our results hold for any whenever the size of the list of each vertex v is at least where is the degree of vertex v and β is a constant that only depends on α. The result is obtained by proving the decay of correlations of marginal probabilities associated with graph nodes measured using a suitably chosen error function. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46,599–613, 2015     

Complexity of the packing coloring problem for trees

Packing coloring is a partitioning of the vertex set of a graph with the property that vertices in the i-th class have pairwise distance greater than i. The main result of this paper is a solution of an open problem of Goddard et al. showing that the decision whether a tree allows a packing coloring with at most k classes is NP-complete.We further discuss specific cases when this problem allows an efficient algorithm. Namely, we show that it is decideable in polynomial time for graphs of bounded treewidth and diameter, and fixed parameter tractable for chordal graphs.We accompany these results by several observations on a closely related variant of the packing coloring problem, where the lower bounds on the distances between vertices inside color classes are determined by an infinite nondecreasing sequence of bounded integers.     

List circular coloring of trees and cycles

Suppose G=(V, E) is a graph and p ≥ 2q are positive integers. A (p, q)‐coloring of G is a mapping ?: V → {0, 1, …, p‐1} such that for any edge xy of G, q ≤ |?(x)‐?(y)| ≤ p‐q. A color‐list is a mapping L: V → ({0, 1, …, p‐1}) which assigns to each vertex v a set L(v) of permissible colors. An L‐(p, q)‐coloring of G is a (p, q)‐coloring ? of G such that for each vertex v, ?(v) ∈ L(v). We say G is L‐(p, q)‐colorable if there exists an L‐(p, q)‐coloring of G. A color‐size‐list is a mapping ? which assigns to each vertex v a non‐negative integer ?(v). We say G is ?‐(p, q)‐colorable if for every color‐list L with |L(v)| = ?(v), G is L‐(p, q)‐colorable. In this article, we consider list circular coloring of trees and cycles. For any tree T and for any p ≥ 2q, we present a necessary and sufficient condition for T to be ?‐(p, q)‐colorable. For each cycle C and for each positive integer k, we present a condition on ? which is sufficient for C to be ?‐(2k+1, k)‐colorable, and the condition is sharp. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 249–265, 2007     

Long time heat diffusion on homogeneous trees

Let be a homogeneous tree of degree , , the Laplace operator of and the fundamental solution of the heat equation on . We show that the heat kernel is asymptotically concentrated in an annulus moving to infinity with finite speed . Asymptotic concentration of heat in the norm is also investigated.

     

Cover time and mixing time of random walks on dynamic graphs

The application of simple random walks on graphs is a powerful tool that is useful in many algorithmic settings such as network exploration, sampling, information spreading, and distributed computing. This is due to the reliance of a simple random walk on only local data, its negligible memory requirements, and its distributed nature. It is well known that for static graphs the cover time, that is, the expected time to visit every node of the graph, and the mixing time, that is, the time to sample a node according to the stationary distribution, are at most polynomial relative to the size of the graph. Motivated by real world networks, such as peer‐to‐peer and wireless networks, the conference version of this paper was the first to study random walks on arbitrary dynamic networks. We study the most general model in which an oblivious adversary is permitted to change the graph after every step of the random walk. In contrast to static graphs, and somewhat counter‐intuitively, we show that there are adversary strategies that force the expected cover time and the mixing time of the simple random walk on dynamic graphs to be exponentially long, even when at each time step the network is well connected and rapidly mixing. To resolve this, we propose a simple strategy, the lazy random walk, which guarantees, under minor conditions, polynomial cover time and polynomial mixing time regardless of the changes made by the adversary.     

The mixing time of the giant component of a random graph

We show that the total variation mixing time of the simple random walk on the giant component of supercritical and is . This statement was proved, independently, by Fountoulakis and Reed. Our proof follows from a structure result for these graphs which is interesting in its own right. We show that these graphs are “decorated expanders” — an expander glued to graphs whose size has constant expectation and exponential tail, and such that each vertex in the expander is glued to no more than a constant number of decorations. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 383–407, 2014     

On large‐girth regular graphs and random processes on trees

We study various classes of random processes defined on the regular tree T_d that are invariant under the automorphism group of T_d. The most important ones are factor of i.i.d. processes (randomized local algorithms), branching Markov chains and a new class that we call typical processes. Using Glauber dynamics on processes we give a sufficient condition for a branching Markov chain to be factor of i.i.d.     

Swendsen‐Wang dynamics for general graphs in the tree uniqueness region

The Swendsen‐Wang (SW) dynamics is a popular Markov chain for sampling from the Gibbs distribution for the ferromagnetic Ising model on a graph G = (V,E). The dynamics is conjectured to converge to equilibrium in O(|V|^1/4) steps at any (inverse) temperature β, yet there are few results providing o(|V|) upper bounds. We prove fast convergence of the SW dynamics on general graphs in the tree uniqueness region. In particular, when β < β_c(d) where β_c(d) denotes the uniqueness/nonuniqueness threshold on infinite d‐regular trees, we prove that the relaxation time (i.e., the inverse spectral gap) of the SW dynamics is Θ(1) on any graph of maximum degree d ≥ 3. Our proof utilizes a monotone version of the SW dynamics which only updates isolated vertices. We establish that this variant of the SW dynamics has mixing time and relaxation time Θ(1) on any graph of maximum degree d for all β < β_c(d). Our proof technology can be applied to general monotone Markov chains, including for example the heat‐bath block dynamics, for which we obtain new tight mixing time bounds.     

A linear time algorithm for edge coloring of binomial trees

We consider the problem of efficient coloring of the edges of a so-called binomial tree T, i.e. acyclic graph containing two kinds of edges: those which must have a single color and those which are to be colored with L consecutive colors, where L is an arbitrary integer greater than 1. We give an O(n) time algorithm for optimal coloring of such a tree, where n is the number of vertices of T. Also, we give simple bounds on the chromatic index of T and a division of all binomial trees into two classes depending on their chromaticity.     

Rapid mixing of Gibbs sampling on graphs that are sparse on average

Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erd?s‐Rényi random graph G(n,d/n), where each edge is chosen independently with probability d/n and d is fixed. While the average degree in G(n,d/n) is d(1 ‐ o(1)), it contains many nodes of degree of order log n/log log n. The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n,p) such as uniform coloring (with a constant number of colors) or the Ising model at any fixed inverse temperature β, the mixing time of Gibbs sampling is at least n^{1+Ω(1/log log n)}. Recall that the Ising model with inverse temperature β defined on a graph G = (V,E) is the distribution over {±}^Vgiven by . High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including the Ising model and coloring. Almost all known sufficient conditions in terms of β or number of colors needed for rapid mixing of Gibbs samplers are stated in terms of the maximum degree of the underlying graph. In this work, we show that for every d < ∞ and the Ising model defined on G (n, d/n), there exists a β_d > 0, such that for all β < β_d with probability going to 1 as n →∞, the mixing time of the dynamics on G (n, d/n) is polynomial in n. Our results are the first polynomial time mixing results proven for a natural model on G (n, d/n) for d > 1 where the parameters of the model do not depend on n. They also provide a rare example where one can prove a polynomial time mixing of Gibbs sampler in a situation where the actual mixing time is slower than npolylog(n). Our proof exploits in novel ways the local tree like structure of Erd?s‐Rényi random graphs, comparison and block dynamics arguments and a recent result of Weitz. Our results extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. In particular, they apply to any graph for which every vertex v of the graph has a neighborhood N(v) of radius O(log n) in which the induced sub‐graph is a tree union at most O(log n) edges and where for each simple path in N(v) the sum of the vertex degrees along the path is O(log n). Moreover, our result apply also in the case of arbitrary external fields and provide the first FPRAS for sampling the Ising distribution in this case. We finally present a non Markov Chain algorithm for sampling the distribution which is effective for a wider range of parameters. In particular, for G(n, d/n) it applies for all external fields and β < β_d, where d tanh(β_d) = 1 is the critical point for decay of correlation for the Ising model on G(n, d/n). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009