Abstract We study and classify proper q colourings of the ℤ d lattice, identifying three regimes where different combinatorial behaviour holds. (1) When $q\le d+1$ , there exist frozen colourings, that is, proper q colourings of ℤ d which cannot be modified on any finite subset. (2) We prove a strong listcolouring property which implies that, when $q\ge d+2$ , any proper q colouring of the boundary of a box of side length $n \ge d+2$ can be extended to a proper q colouring of the entire box. (3) When $q\geq 2d+1$ , the latter holds for any $n \ge 1$ . Consequently, we classify the space of proper q colourings of the ℤ d lattice by their mixing properties.
more »
« less
Sampling biased monotonic surfaces using exponential metrics
Abstract Monotonic surfaces spanning finite regions of ℤ d arise in many contexts, including DNAbased selfassembly, cardshuffling and lozenge tilings. One method that has been used to uniformly generate these surfaces is a Markov chain that iteratively adds or removes a single cube below the surface during a step. We consider a biased version of the chain, where we are more likely to add a cube than to remove it, thereby favouring surfaces that are ‘higher’ or have more cubes below it. We prove that the chain is rapidly mixing for any uniform bias in ℤ 2 and for bias λ > d in ℤ d when d > 2. In ℤ 2 we match the optimal mixing time achieved by Benjamini, Berger, Hoffman and Mossel in the context of biased card shuffling [2], but using much simpler arguments. The proofs use a geometric distance function and a variant of path coupling in order to handle distances that can be exponentially large. We also provide the first results in the case of fluctuating bias , where the bias can vary depending on the location of the tile. We show that the chain continues to be rapidly mixing if the biases are close to uniform, but that the chain can converge exponentially slowly in the general setting.
more »
« less
 Award ID(s):
 1733812
 NSFPAR ID:
 10324726
 Date Published:
 Journal Name:
 Combinatorics, Probability and Computing
 Volume:
 29
 Issue:
 5
 ISSN:
 09635483
 Page Range / eLocation ID:
 672 to 697
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Abstract We study the mixing time of a Markov chain on biased permutations, a problem related to self‐organizing lists. We are given probabilities for all such that . The chain iteratively chooses two adjacent elements and , and swaps them with probability . It has been conjectured that is rapidly mixing whenever the set of probabilities are “positively biased,” that is, for all . We define two general classes and give the first proofs that is rapidly mixing for both. We also demonstrate that the chain can have exponential mixing time, disproving the most general version of this conjecture.

A bstract The 3d Ising model in the low temperature (ferromagnetic) phase describes dynamics of twodimensional surfaces — domain walls between clusters of parallel spins. The KramersWannier duality maps these surfaces into worldsheets of confining strings in the Wegner’s ℤ 2 gauge theory. We study the excitation spectrum of long Ising strings by simulating the ℤ 2 gauge theory on a lattice. We observe a strong mixing between string excitations and the lightest glueball state and do not find indications for light massive resonances on the string worldsheet.more » « less

The seminal result of Kahn, Kalai and Linial shows that a coalition of O(n/(log n)) players can bias the outcome of any Boolean function {0,1}^n > {0,1} with respect to the uniform measure. We extend their result to arbitrary product measures on {0,1}^n, by combining their argument with a completely different argument that handles very biased input bits. We view this result as a step towards proving a conjecture of Friedgut, which states that Boolean functions on the continuous cube [0,1]^n (or, equivalently, on {1,...,n}^n) can be biased using coalitions of o(n) players. This is the first step taken in this direction since Friedgut proposed the conjecture in 2004. Russell, Saks and Zuckerman extended the result of Kahn, Kalai and Linial to multiround protocols, showing that when the number of rounds is o(log^* n), a coalition of o(n) players can bias the outcome with respect to the uniform measure. We extend this result as well to arbitrary product measures on {0,1}^n. The argument of Russell et al. relies on the fact that a coalition of o(n) players can boost the expectation of any Boolean function from epsilon to 1epsilon with respect to the uniform measure. This fails for general product distributions, as the example of the AND function with respect to mu_{11/n} shows. Instead, we use a novel boosting argument alongside a generalization of our first result to arbitrary finite ranges.more » « less

Certain patterns of symmetry fractionalization in topologicallyordered phases of matter are anomalous, in the sense that they can onlyoccur at the surface of a higher dimensional symmetryprotectedtopological (SPT) state. An important question is to determine how tocompute this anomaly, which means determining which SPT hosts a givensymmetryenriched topological order at its surface. While special casesare known, a general method to compute the anomaly has so far beenlacking. In this paper we propose a general method to compute relativeanomalies between different symmetry fractionalization classes of agiven (2+1)D topological order. This method applies to all types ofsymmetry actions, including anyonpermuting symmetries and generalspacetime reflection symmetries. We demonstrate compatibility of therelative anomaly formula with previous results for diagnosing anomaliesfor \mathbb{Z}_2^{T} ℤ 2 T spacetime reflection symmetry (e.g. where timereversal squares to theidentity) and mixed anomalies for U(1) \times \mathbb{Z}_2^{T} U ( 1 ) × ℤ 2 T and U(1) \rtimes \mathbb{Z}_2^{T} U ( 1 ) ⋊ ℤ 2 T symmetries. We also study a number of additional examples, includingcases where spacetime reflection symmetries are intertwined innontrivial ways with unitary symmetries, such as \mathbb{Z}_4^{T} ℤ 4 T and mixed anomalies for \mathbb{Z}_2 \times \mathbb{Z}_2^{T} ℤ 2 × ℤ 2 T symmetry, and unitary \mathbb{Z}_2 \times \mathbb{Z}_2 ℤ 2 × ℤ 2 symmetry with nontrivial anyon permutations.more » « less