Gibbs rapidly samples colorings of G(n, d/n)

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, d/n) 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) with high probability. High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including coloring. Almost all known sufficient conditions in terms of 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 consider sampling q-colorings and show that for every d < ∞ there exists q(d) < ∞ such that for all q ≥ q(d) the mixing time of the Gibbs sampling on G(n, d/n) is polynomial in n with high probability. Our results are the first polynomial time mixing results proven for the coloring model on G(n, d/n) for d > 1 where the number of colors does 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). In previous work we have shown that similar results hold for the ferromagnetic Ising model. However, the proof for the Ising model crucially relied on monotonicity arguments and the “Weitz tree”, both of which have no counterparts in the coloring setting. Our proof presented here exploits in novel ways the local treelike structure of Erd?s–Rényi random graphs, block dynamics, spatial decay properties and coupling arguments. Our results give the first polynomial-time algorithm to approximately sample colorings on G(n, d/n) with a constant number of colors. They 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 there exists an α > 0 such that every vertex v of the graph has a neighborhood N(v) of radius O(log n) in which the induced sub-graph is the union of a tree and at most O(1) edges and where each simple path Γ of length O(log n) satisfies ${\sum_{u \in \Gamma}\sum_{v \neq u}\alpha^{d(u,v)} = O({\rm log} n)}$ . The results also generalize to the hard-core model at low fugacity and to general models of soft constraints at high temperatures.     

Very rapidly mixing Markov chains for 2Δ‐colorings and for independent sets in a graph with maximum degree 4

We introduce a new technique for analyzing the mixing rate of Markov chains. We use it to prove that the Glauber dynamics on 2Δ‐colorings of a graph with maximum degree Δ mixes in O(n log n) time. We prove the same mixing rate for the Insert/Delete/Drag chain of Dyer and Greenhill (Random Structures Algorithms 13 , 285–317 (1998)) on independent sets of graphs with maximum degree 4. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 101–115, 2001     

Mixing Times of Critical Two‐Dimensional Potts Models

We study dynamical aspects of the q‐state Potts model on an n × n box at its critical β_c(q). Heat‐bath Glauber dynamics and cluster dynamics such as Swendsen–Wang (that circumvent low‐temperature bottlenecks) are all expected to undergo “critical slowdowns” in the presence of periodic boundary conditions: the inverse spectral gap, which in the subcritical regime is O(1), should at criticality be polynomial in n for 1 < q ≤ 4, and exponential in n for q > 4 in accordance with the predicted discontinuous phase transition. This was confirmed for q = 2 (the Ising model) by the second author and Sly, and for sufficiently large q by Borgs et al. Here we show that the following holds for the critical Potts model on the torus: for q=3, the inverse gap of Glauber dynamics is n^O(1); for q = 4, it is at most n^{O(log n)}; and for every q > 4 in the phase‐coexistence regime, the inverse gaps of both Glauber dynamics and Swendsen‐Wang dynamics are exponential in n. For free or monochromatic boundary conditions and large q, we show that the dynamics at criticality is faster than on the torus (unlike the Ising model where free/periodic boundary conditions induce similar dynamical behavior at all temperatures): the inverse gap of Swendsen‐Wang dynamics is exp(n^o(1)). © 2017 Wiley Periodicals, Inc.     

Boundary proximity of SLE

This paper examines how close the chordal SLE _κ curve gets to the real line asymptotically far away from its starting point. In particular, when κ ? (0, 4), it is shown that if β > β _κ  := 1/(8/κ ? 2), then the intersection of the SLE _κ curve with the graph of the function y = x/(log x) ^β , x > e, is a.s. bounded, while it is a.s. unbounded if β = β _κ . The critical SLE₄ curve a.s. intersects the graph of $y=x^{{-({\rm log\,log\,x})}^{\alpha}}, x > e^e$ , x > e ^e , in an unbounded set if α ≤ 1, but not if α > 1. Under a very mild regularity assumption on the function y(x), we give a necessary and sufficient integrability condition for the intersection of the SLE _κ path with the graph of y to be unbounded. When the intersection is bounded a.s., we provide an estimate for the probability that the SLE _κ path hits the graph of y. We also prove that the Hausdorff dimension of the intersection set of the SLE _κ curve and the real axis is 2 ? 8/κ when 4 < κ < 8.     

The Semilinear Wave Equation on Asymptotically Euclidean Manifolds

We consider the quadratically semilinear wave equation on (? ^d , 𝔤), d ≥ 3. The metric 𝔤 is non-trapping and approaches the Euclidean metric like ?x?^?ρ. Using Mourre estimates and the Kato theory of smoothness, we obtain, for ρ > 0, a Keel–Smith–Sogge type inequality for the linear equation. Thanks to this estimate, we prove long time existence for the nonlinear problem with small initial data for ρ ≥ 1. Long time existence means that, for all n > 0, the life time of the solution is a least δ^?n , where δ is the size of the initial data in some appropriate Sobolev space. Moreover, for d ≥ 4 and ρ > 1, we obtain global existence for small data.     

On SA, CA, and GA numbers

Gronwall’s function G is defined for n>1 by $G(n)=\frac{\sigma(n)}{n \log\log n}$ where σ(n) is the sum of the divisors of n. We call an integer N>1 a GA1 number if N is composite and G(N)≥G(N/p) for all prime factors p of N. We say that N is a GA2 number if G(N)≥G(aN) for all multiples aN of N. In (Caveney et al. Integers 11:A33, 2011), we used Robin’s and Gronwall’s theorems on G to prove that the Riemann Hypothesis (RH) is true if and only if 4 is the only number that is both GA1 and GA2. In the present paper, we study GA1 numbers and GA2 numbers separately. We compare them with superabundant (SA) and colossally abundant (CA) numbers (first studied by Ramanujan). We give algorithms for computing GA1 numbers; the smallest one with more than two prime factors is 183783600, while the smallest odd one is 1058462574572984015114271643676625. We find nineteen GA2 numbers ≤5040, and prove that a GA2 number N>5040 exists if and only if RH is false, in which case N is even and >10⁸⁵⁷⁶.     

On some classes of bounded univalent mappings in several complex variables

Let B ⁿ be the Euclidean unit ball in C ⁿ . In this paper, we study several properties of strongly starlike mappings of order α (0 < α < 1) and bounded convex mappings on B ⁿ . We prove that K-quasiregular strongly starlike mappings of order α on B ⁿ have continuous and univalent extensions to ${\overline{B}^n}$ . We show that bounded convex mappings on B ⁿ are strongly starlike of some order α. We give a coefficient estimate for K-quasiregular strongly starlike mappings of order α on B ⁿ . Finally, we give examples of strongly starlike mappings of order α and bounded convex mappings on B ⁿ .     

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     

On a conjecture of Butler and Graham

Motivated by a hat guessing problem proposed by Iwasawa, Butler and Graham made the following conjecture on the existence of a certain way of marking the coordinate lines in [k] ⁿ : there exists a way to mark one point on each coordinate line in [k] ⁿ , so that every point in [k] ⁿ is marked exactly a or b times as long as the parameters (a, b, n, k) satisfies that there are nonnegative integers s and t such that s + t = k ⁿ and as + bt = nk ^n?1. In this paper we prove this conjecture for any prime number k. Moreover, we prove the conjecture for the case when a = 0 for general k.     

Nonnegative functions as squares or sums of squares

We prove that, for n?4, there are C^∞ nonnegative functions f of n variables (and even flat ones for n?5) which are not a finite sum of squares of C² functions. For n=1, where a decomposition in a sum of two squares is always possible, we investigate the possibility of writing f=g². We prove that, in general, one cannot require a better regularity than g∈C¹. Assuming that f vanishes at all its local minima, we prove that it is possible to get g∈C² but that one cannot require any additional regularity.     

The mixing time of Glauber dynamics for coloring regular trees

We consider Metropolis Glauber dynamics for sampling proper q‐colorings of the n‐vertex complete b‐ary tree when 3 ≤ q ≤ b/(2lnb). We give both upper and lower bounds on the mixing time. Our upper bound is n^{O(b/ log b)} and our lower bound is n^{Ω(b/(q log b))}, where the constants implicit in the O() and Ω() notation do not depend upon n, q or b. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Many L-Shaped Polyominoes Have Odd Rectangular Packings

A polyomino is called odd if it can tile a rectangle using an odd number of copies. We give a very general family of odd polyominoes. Specifically, consider an L-shaped polyomino, i.e., a rectangle that has a rectangular piece removed from one corner. For some of these polyominoes, two copies tile a rectangle, called a basic rectangle. We prove that such a polyomino is odd if its basic rectangle has relatively prime side lengths. This general family encompasses several previously known families of odd polyominoes, as well as many individual examples. We prove a stronger result for a narrower family of polyominoes. Let L _n denote the polyomino formed by removing a 1 ×  (n?2) corner from a 2 ×  (n?1) rectangle. We show that when n is odd, L _n tiles all rectangles both of whose sides are at least 8n ³, and whose area is a multiple of n. If we only allow L _n to be rotated, but not reflected, then the same is true, provided that both sides of the rectangle are at least 16n ⁴. We also give several isolated examples of odd polyominoes.     

Flip Graphs of Bounded Degree Triangulations

We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider triangulations of sets of n points in convex position in the plane and prove that their flip graph is connected if and only if k > 6; the diameter of the flip graph is O(n ²). We also show that, for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for k ≤ 9, and flip graphs of triangulations can be disconnected for any k. Additionally, we consider a relaxed version of the original problem. We allow the violation of the degree bound k by a small constant. Any two triangulations with maximum degree at most k of a convex point set are connected in the flip graph by a path of length O(n log n), where every intermediate triangulation has maximum degree at most k + 4.     

Transcendance « à la Liouville » de certains nombres réels

Using a Liouville-like approach, we prove that real numbers like ∑_n=0^+∞(1/β^u_n), where β is a Pisot or a Salem number and where (u_n)_n?0 is a sufficiently lacunary sequence of positive integers, are transcendental. To cite this article: B. Adamczewski, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Low Frequency Estimates and Local Energy Decay for Asymptotically Euclidean Laplacians

For Riemannian metrics G on ? ^d which are long range perturbations of the flat one, we prove estimates for (? Δ _G  ? λ ?iε)^?n as λ → 0, which are uniform with respect to ε, for all n ≤ [d/2] +1 in odd dimension and n ≤ d/2 in even dimension. We also give applications to the time decay of Schrödinger and Wave (or Klein–Gordon) equations.     

Cutoff for the Ising model on the lattice

Introduced in 1963, Glauber dynamics is one of the most practiced and extensively studied methods for sampling the Ising model on lattices. It is well known that at high temperatures, the time it takes this chain to mix in L ¹ on a system of size n is O(logn). Whether in this regime there is cutoff, i.e. a sharp transition in the L ¹-convergence to equilibrium, is a fundamental open problem: If so, as conjectured by Peres, it would imply that mixing occurs abruptly at (c+o(1))logn for some fixed c>0, thus providing a rigorous stopping rule for this MCMC sampler. However, obtaining the precise asymptotics of the mixing and proving cutoff can be extremely challenging even for fairly simple Markov chains. Already for the one-dimensional Ising model, showing cutoff is a longstanding open problem. We settle the above by establishing cutoff and its location at the high temperature regime of the Ising model on the lattice with periodic boundary conditions. Our results hold for any dimension and at any temperature where there is strong spatial mixing: For ?² this carries all the way to the critical temperature. Specifically, for fixed d≥1, the continuous-time Glauber dynamics for the Ising model on (?/n?) ^d with periodic boundary conditions has cutoff at (d/2λ _∞)logn, where λ _∞ is the spectral gap of the dynamics on the infinite-volume lattice. To our knowledge, this is the first time where cutoff is shown for a Markov chain where even understanding its stationary distribution is limited. The proof hinges on a new technique for translating L ¹-mixing to L ²-mixing of projections of the chain, which enables the application of logarithmic-Sobolev inequalities. The technique is general and carries to other monotone and anti-monotone spin-systems, e.g. gas hard-core, Potts, anti-ferromagentic Ising, arbitrary boundary conditions, etc.     

Distribution of the coefficients of modular forms and the partition function

Let ? be an odd prime and j, s be positive integers. We study the distribution of the coefficients of integer and half-integral weight modular forms modulo an odd positive integer M. As an application, we investigate the distribution of the ordinary partition function p(n) modulo ? ^j and prove that for each integer 1?≤ r?<?? ^j , $$\sharp\{1\le n\le X\ |\ p(n)\equiv r\pmod{\ell^j} \}\gg_{s,r,\ell^j} \frac{\sqrt X}{\log X}(\log\log X)^s.$$      

On the set of natural numbers which only yield orders of Abelian groups

Let A denote the set of all natural numbers n such that every group of order n is Abelian. Let C denote the set of all natural numbers n such that every group of order n is cyclic. We prove that Σ_{n ≤ x,n?A?C}1 has roughly the order of magnitude x(log log x)^?1.