Presented on October 2, 2017 at 11:00 a.m. in the Klaus Advanced Computing Building, room 1116E.
As for Swendsen--Wang, comparison estimates due to Ullrich @cite_2 @cite_39 imply that its inverse gap is at most that of Glauber dynamics on any graph and at any temperature (see Theorem ); thus for @math on @math it also has @math for all @math and for all @math thanks to duality, and similarly at @math it has @math .
@cite_39 @cite_2
1980404829 1982190141 2126692288 2963060913 2243323450 2135481845 2889042315 2611336766 2030987833 2002456042 2031651515 1965879843 2004724832 2147668104 2030344865 2128943288 2102318662 1968429800 2095138947 2152708178
We prove comparison results for the Swendsen-Wang (SW) dynamics, the heat-bath (HB) dynamics for the Potts model and the single-bond (SB) dynamics for the random-cluster model on arbitrary graphs. In particular, we prove that rapid mixing of HB implies rapid mixing of SW on graphs with bounded maximum degree and that rapid mixing of SW and rapid mixing of SB are equivalent. Additionally, the spectral gap of SW and SB on planar graphs is bounded from above and from below by the spectral gap of these dynamics on the corresponding dual graph with suitably changed temperature. As a consequence we obtain rapid mixing of the Swendsen-Wang dynamics for the Potts model on the two-dimensional square lattice at all non-critical temperatures as well as rapid mixing for the two-dimensional Ising model at all temperatures. Furthermore, we obtain new results for general graphs at high or low enough temperatures. We prove that the spectral gap of the Swendsen-Wang process for the Potts model on graphs with bounded degree is bounded from below by some constant times the spectral gap of any single-spin dynamics. This implies rapid mixing for the two-dimensional Potts model at all temperatures above the critical one, as well as rapid mixing at the critical temperature for the Ising model. After this we introduce a modified version of the Swendsen-Wang algorithm for planar graphs and prove rapid mixing for the two-dimensional Potts models at all non-critical temperatures. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 520–535, 2013 Studies two widely used algorithms, Glauber dynamics and the Swendsen-Wang (1987) algorithm, on rectangular subsets of the hypercubic lattice Z sup d . We prove that, under certain circumstances, the mixing time in a box of side length L with periodic boundary conditions can be exponential in L sup d-1 . In other words, under these circumstances, the mixing in these widely used algorithms is not rapid; instead it is torpid. The models we study are the independent set model and the q-state Potts model. For both models, we prove that Glauber dynamics is torpid in the region with phase coexistence. For the Potts model, we prove that the Swendsen-Wang mixing is torpid at the phase transition point. We show for the first time that the mixing time of Glauber (single edge update) dynamics for the random cluster model at q = 2 is bounded by a polynomial in the size of the underlying graph. As a consequence, the Swendsen-Wang algorithm for the ferromagnetic Ising model at any temperature has the same polynomial mixing time bound. We consider a Glauber dynamics reversible with respect to the two-dimensional Ising model in a finite square of sideL, in the absence of an external field and at large inverse temperature β. We first consider the gap in the spectrum of the generator of the dynamics in two different cases: with plus and open boundary conditions. We prove that, when the symmetry under global spin flip is broken by the boundary conditions, the gap is much larger than the case in which the symmetry is present. For this latter we compute exactly the asymptotics of −(1 βL) log(gap) asL→∞ and show that it coincides with the surface tension along one of the coordinate axes. As a consequence we are able to study quite precisely the large deviations in time of the magnetization and to obtain an upper bound on the spin-spin time correlation in the infinite-volume plus phase. Our results establish a connection between the dynamical large deviations and those of the equilibrium Gibbs measure studied by Shlosman in the framework of the rigorous description of the Wulff shape for the Ising model. Finally we show that, in the case of open boundary conditions, it is possible to rescale the time withL in such a way that, asL→∞, the finite-dimensional distributions of the time-rescaled magnetization converge to those of a symmetric continuous-time Markov chain on the two-state space −m*(β),m*(β) ,m*(β) being the spontaneous magnetization. Our methods rely upon a novel combination of techniques for bounding from below the gap of symmetric Markov chains on complicated graphs, developed by Jerrum and Sinclair in their Markov chain approach to hard computational problems, and the idea of introducing “block Glauber dynamics” instead of the standard single-site dynamics, in order to put in evidence more effectively the effect of the boundary conditions in the approach to equilibrium. We study discrete time Glauber dynamics for random configurations with local constraints (e.g. proper coloring, Ising and Potts models) on finite graphs with n vertices and of bounded degree. We show that the relaxation time (defined as the reciprocal of the spectral gap 1- spl lambda sub 2 ) for the dynamics on trees and on certain hyperbolic graphs, is polynomial in n. For these hyperbolic graphs, this yields a general polynomial sampling algorithm for random configurations. We then show that if the relaxation time spl tau sub 2 satisfies spl tau sub 2 =O(n), then the correlation coefficient, and the mutual information, between any local function (which depends only on the configuration in a fixed window) and the boundary conditions, decays exponentially in the distance between the window and the boundary. For the Ising model on a regular tree, this condition is sharp. Oliveira conjectured that the order of the mixing time of the exclusion process with @math -particles on an arbitrary @math -vertex graph is at most that of the mixing-time of @math independent particles. We verify this up to a constant factor for @math -regular graphs when each edge rings at rate @math in various cases: (1) when @math or (2) when @math the spectral-gap of a single walk is @math and @math or (3) when @math for some constant @math . In these cases our analysis yields a probabilistic proof of a weaker version of Aldous' famous spectral-gap conjecture (resolved by ). We also prove a general bound which is at worst @math , which is within a @math factor from Oliveira's conjecture when @math . As applications we get new mixing bounds: (a) @math for expanders, (b) order @math for the hypercube @math and (c) order @math for vertex-transitive graphs of moderate growth and for supercritical percolation on a fixed dimensional torus. We study discrete time Glauber dynamics for random configurations with local constraints (e.g. proper coloring, Ising and Potts models) on finite graphs with n vertices and of bounded degree. We show that the relaxation time (defined as the reciprocal of the spectral gap 1 - _2 for the dynamics on trees and on certain hyperbolic graphs is polynomial in n. For these hyperbolic graphs, this yields a general polynomial sampling algorithm for random configurations. We then show that if the relaxation time T2 satisfies T2 = O(n), then the correlation coefficient, and the mutual information, between any local function (which dependsonly on the configuration in a fixed window) and the boundary conditions, decays exponentially in the distance between the window and the boundary. For the Ising model on a regular tree, this condition is sharp. We introduce a new graph parameter, called the Grothendieck constant of a graph G=(V,E), which is defined as the least constant K such that for every A:E→ℝ, @math The classical Grothendieck inequality corresponds to the case of bipartite graphs, but the case of general graphs is shown to have various algorithmic applications. Indeed, our work is motivated by the algorithmic problem of maximizing the quadratic form ∑ u,v ∈E A(u,v)ϕ(u)ϕ(v) over all ϕ:V→ -1,1 , which arises in the study of correlation clustering and in the investigation of the spin glass model. We give upper and lower estimates for the integrality gap of this program. We show that the integrality gap is (O( ( G )) ), where ( ( G ) ) is the Lovasz Theta Function of the complement of G, which is always smaller than the chromatic number of G. This yields an efficient constant factor approximation algorithm for the above maximization problem for a wide range of graphs G. We also show that the maximum possible integrality gap is always at least Ω(log ω(G)), where ω(G) is the clique number of G. In particular it follows that the maximum possible integrality gap for the complete graph on n vertices with no loops is Θ(logn). More generally, the maximum possible integrality gap for any perfect graph with chromatic number n is Θ(logn). The lower bound for the complete graph improves a result of Kashin and Szarek on Gram matrices of uniformly bounded functions, and settles a problem of Megretski and of Charikar and Wirth. We consider the Glauber dynamics for the 2D Ising model in a box of side L, at inverse temperature β and random boundary conditions τ whose distribution P either stochastically dominates the extremal plus phase (hence the quotation marks in the title) or is stochastically dominated by the extremal minus phase. A particular case is when P is concentrated on the homogeneous configuration identically equal to + (equal to −). For β large enough we show that for any ( >0 ) there exists ( c=c( , ) ) such that the corresponding mixing time T mix satisfies ( lim _ L , P (T_ mix exp ( cL^ ) ) =0 ). In the non-random case τ ≡ + (or τ ≡ −), this implies that ( T_ mix exp ( cL^ ) ). The same bound holds when the boundary conditions are all + on three sides and all − on the remaining one. The result, although still very far from the expected Lifshitz behavior T mix = O(L 2), considerably improves upon the previous known estimates of the form ( T_ mix exp ( c L^ 12 + ) ). The techniques are based on induction over length scales, combined with a judicious use of the so-called “censoring inequality” of Y. Peres and P. Winkler, which in a sense allows us to guide the dynamics to its equilibrium measure. We consider Glauber dynamics (starting from an extremal configuration) in a monotone spin system, and show that interjecting extra updates cannot increase the expected Hamming distance or the total variation distance to the stationary distribution. We deduce that for monotone Markov random fields, when block dynamics contracts a Hamming metric, single-site dynamics mixes in O(n log n) steps on an n-vertex graph. In particular, our result completes work of Kenyon, Mossel and Peres concerning Glauber dynamics for the Ising model on trees. Our approach also shows that on bipartite graphs, alternating updates systematically between odd and even vertices cannot improve the mixing time by more than a factor of log n compared to updates at uniform random locations on an n-vertex graph. Our result is especially effective in comparing block and single-site dynamics; it has already been used in works of Martinelli, Toninelli, Sinclair, Mossel, Sly, Ding, Lubetzky, and Peres in various combinations. We give the first comprehensive analysis of the effect of boundary conditions on the mixing time of the Glauber dynamics in the so-called Bethe approximation. Specifically, we show that the spectral gap and the log-Sobolev constant of the Glauber dynamics for the Ising model on an n-vertex regular tree with (+)-boundary are bounded below by a constant independent of n at all temperatures and all external fields. This implies that the mixing time is O(logn) (in contrast to the free boundary case, where it is not bounded by any fixed polynomial at low temperatures). In addition, our methods yield simpler proofs and stronger results for the spectral gap and log-Sobolev constant in the regime where the mixing time is insensitive to the boundary condition. Our techniques also apply to a much wider class of models, including those with hard-core constraints like the antiferromagnetic Potts model at zero temperature (proper colorings) and the hard–core lattice gas (independent sets). Consider the problem of approximately counting weighted independent sets of a graph G with activity λ, i.e., where the weight of an independent set I is λ|I|. We present a novel analysis yielding a deterministic approximation scheme which runs in polynomial time for any graph of maximum degree Δ and λ< λc=(Δ-1)Δ-1 (Δ-2)Δ. This improves on the previously known general bound of λ ≤ (2 ‾ Δ-2). The new regime includes the interesting case of λ=1 (uniform weights) and Δ ≤ 5. The previous bound required Δ ≤ 4 for uniform approximate counting and there is evidence that for Δ ≥ 6 the problem is hard. Note that λc is the critical activity for uniqueness of the Gibbs measure on the regular tree of degree Δ, i.e., for λ ≤ λc the probability that the root is in the independent set is asymptotically independent of the configuration on the leaves far below. Indeed, our analysis is focused on establishing decay of correlations with distance in the above weighted distribution. We show that on any graph of maximum degree Δ correlations decay with distance at least as fast as they do on the regular tree of the same degree. This resolves an open conjecture in statistical physics. Our comparison of a general graph with the tree uses an algorithmic argument yielding the approximation scheme mentioned above. Also, by existing arguments, establishing decay of correlations for all graphs and λ<λc gives that the Glauber dynamics is rapidly mixing in this regime. However, the implication from decay of correlations to rapid mixing of the dynamics is only known to hold for graphs of subexponential growth, and hence, our result regarding the Glauber dynamics is limited to this class of graphs. We show that the Goemans-Linial semidefinite relaxation of the Sparsest Cut problem with general demands has integrality gap @math . This is achieved by exhibiting @math -point metric spaces of negative type whose @math distortion is @math . Our result is based on quantitative bounds on the rate of degeneration of Lipschitz maps from the Heisenberg group to @math when restricted to cosets of the center. We consider the two-dimensional stochastic Ising model in finite square Λ with free boundary conditions, at inverse temperature β>β0 and zero external field. Using duality and recent results of Ioffe on the Wulff construction close to the critical temperature, we extend some of the results obtained by Martinelli in the low-temperature regime to any temperature below the critical one. In particular we show that the gap in the spectrum of the generator of the dynamics goes to zero in the thermodynamic limit as an exponential of the side length of Λ, with a rate constant determined by the surface tension along one of the coordinate axes. We also extend to the same range of temperatures the result due to Shlosman on the equilibrium large deviations of the magnetization with free boundary conditions. Friedland's Lower Matching Conjecture asserts that if @math is a @math --regular bipartite graph on @math vertices, and @math denotes the number of matchings of size @math , then @math where @math . When @math , this conjecture reduces to a theorem of Schrijver which says that a @math --regular bipartite graph on @math vertices has at least @math perfect matchings. L. Gurvits proved an asymptotic version of the Lower Matching Conjecture, namely he proved that @math In this paper, we prove the Lower Matching Conjecture. In fact, we will prove a slightly stronger statement which gives an extra @math factor compared to the conjecture if @math is separated away from @math and @math , and is tight up to a constant factor if @math is separated away from @math . We will also give a new proof of Gurvits's and Schrijver's theorems, and we extend these theorems to @math --biregular bipartite graphs. We study the maximum of a Gaussian field on @math ( @math ) whose correlations decay logarithmically with the distance. Kahane Kah85 introduced this model to construct mathematically the Gaussian multiplicative chaos in the subcritical case. Duplantier, Rhodes, Sheffield and Vargas DRSV12a DRSV12b extended Kahane's construction to the critical case and established the KPZ formula at criticality. Moreover, they made in DRSV12a several conjectures on the supercritical case and on the maximum of this Gaussian field. In this paper we resolve Conjecture 12 in DRSV12a : we establish the convergence in law of the maximum and show that the limit law is the Gumbel distribution convoluted by the limit of the derivative martingale. We study the quantitative geometry of graphs in terms of their genus, using the structure of certain "cut graphs," i.e. subgraphs whose removal leaves a planar graph. In particular, we give optimal bounds for random partitioning schemes, as well as various types of embeddings. Using these geometric primitives, we present exponentially improved dependence on genus for a number of problems like approximate max-flow min-cut theorems, approximations for uniform and nonuniform Sparsest Cut, treewidth approximation, Laplacian eigenvalue bounds, and Lipschitz extension theorems and related metric labeling problems. We list here a sample of these improvements. All the following statements refer to graphs of genus g, unless otherwise noted. • We show that such graphs admit an O(log g)-approximate multi-commodity max-flow min-cut theorem for the case of uniform demands. This bound is optimal, and improves over the previous bound of O(g) [KPR93, FT03]. For general demands, we show that the worst possible gap is O(log g + CP), where CP is the gap for planar graphs. This dependence is optimal, and already yields a bound of O(log g + √log n), improving over the previous bound of O(√g log n) [KLMN04]. • We give an O(√log g)-approximation for the uniform Sparsest Cut, balanced vertex separator, and treewidth problems, improving over the previous bound of O(g) [FHL05]. • If a graph G has genus g and maximum degree D, we show that the kth Laplacian eigenvalue of G is (log g)2 · O(kgD n), improving over the previous bound of g2·O(kgD n) [KLPT09]. There is a lower bound of Ω(kgD n), making this result almost tight. • We show that if (X, d) is the shortest-path metric on a graph of genus g and S ⊆ X, then every L-Lipschitz map f: S → Z into a Banach space Z admits an O(L log g)-Lipschitz extension f: X → Z. This improves over the previous bound of O(Lg) [LN05], and compares to a lower bound of Ω(L√log g). In a related way, we show that there is an O(log g)-approximation for the 0-extension problem on such graphs, improving over the previous O(g) bound. • We show that every n-vertex shortest-path metric on a graph of genus g embeds into L2 with distortion O(log g + √log n), improving over the previous bound of O(√g log n). Our result is asymptotically optimal for every dependence g = g(n). A convergent low-temperature expansion for a variety of models of twodimensional surfaces is presented. It yields existence of the thermodynamic limit for the pressure and correlation functions as well as analyticity inz =e−β In addition, the estimates give exponential decay of truncated correlations, which proves the existence of a gap in the spectrum of the transfer matrix below the ground state eigenvalue. Two particular examples included in the general framework are the solid-on-solid and discrete Gaussian models. We study two widely used algorithms for the Potts model on rectangular subsets of the hypercubic lattice ( Z ^ d )—heat bath dynamics and the Swendsen–Wang algorithm—and prove that, under certain circumstances, the mixing in these algorithms is torpid or slow. In particular, we show that for heat bath dynamics throughout the region of phase coexistence, and for the Swendsen–Wang algorithm at the transition point, the mixing time in a box of side length L with periodic boundary conditions has upper and lower bounds which are exponential in L d-1. This work provides the first upper bound of this form for the Swendsen–Wang algorithm, and gives lower bounds for both algorithms which significantly improve the previous lower bounds that were exponential in L (log L)2.