Search

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 list-colouring 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.

The classical Kirszbraun theorem says that all 1-Lipschitz functions f : A ⟶ R n , A ⊂ R n , with the Euclidean metric have a 1-Lipschitz extension to R n . For metric spaces X , Y we say that Y is X-Kirszbraun if all 1-Lipschitz functions f : A ⟶ Y , A ⊂ X , have a 1-Lipschitz extension to X. We analyze the case when X and Y are graphs with the usual path metric. We prove that Z d -Kirszbraun graphs are exactly graphs that satisfies a certain Helly's property . We also consider complexity aspects of these properties.

Let $\mathcal H$ be a finite connected undirected graph and $\mathcal H_{walk}$ be the graph of bi-infinite walks on $\mathcal H$; two such walks $\{x_i\}_{i\in \mathbb Z}$ and $\{y_i\}_{i \in \mathbb Z}$ are said to be adjacent if $x_i$ is adjacent to $y_i$ for all $i \in \mathbb Z$. We consider the question: Given a graph $\mathcal H$ when is the diameter (with respect to the graph metric) of $\mathcal H_{walk}$ finite? Such questions arise while studying mixing properties of hom-shifts (shift spaces which arise as the space of graph homomorphisms from the Cayley graph of $\mathbb Z^d$ with respect to the standard generators to $\mathcal H$) and are the subject of this paper., Comment: Corrected typo in the title on the Arxiv page

The Hammersley-Clifford theorem states that if the support of a Markov random field has a safe symbol then it is a Gibbs state with some nearest neighbour interaction. In this paper we generalise the theorem with an added condition that the underlying graph is bipartite. Taking inspiration from "Gibbs Measures and Dismantlable Graphs" by Brightwell and Winkler we introduce a notion of folding for configuration spaces called strong config-folding proving that if all Markov random fields supported on $X$ are Gibbs with some nearest neighbour interaction so are Markov random fields supported on the 'strong config-folds' and 'strong config-unfolds' of $X$., Comment: 27 pages, 7 figures; Typos corrected and some notation has been changed

Fix $d\geq 2$. Given a finite undirected graph ${\mathcal{H}}$ without self-loops and multiple edges, consider the corresponding ‘vertex’ shift, $\text{Hom}(\mathbb{Z}^{d},{\mathcal{H}})$, denoted by $X_{{\mathcal{H}}}$. In this paper, we focus on ${\mathcal{H}}$ which is ‘four-cycle free’. There are two main results of this paper. Firstly, that $X_{{\mathcal{H}}}$ has the pivot property, meaning that, for all distinct configurations $x,y\in X_{{\mathcal{H}}}$, which differ only at a finite number of sites, there is a sequence of configurations $x=x^{1},x^{2},\ldots ,x^{n}=y\in X_{{\mathcal{H}}}$ for which the successive configurations $x^{i},x^{i+1}$ differ exactly at a single site. Secondly, if ${\mathcal{H}}$ is connected ,then $X_{{\mathcal{H}}}$ is entropy minimal, meaning that every shift space strictly contained in $X_{{\mathcal{H}}}$ has strictly smaller entropy. The proofs of these seemingly disparate statements are related by the use of the ‘lifts’ of the configurations in $X_{{\mathcal{H}}}$ to the universal cover of ${\mathcal{H}}$ and the introduction of ‘height functions’ in this context.

The well-known Hammersley-Clifford theorem states (under certain conditions) that any Markov random field is a Gibbs state for a nearest neighbor interaction. In this paper we study Markov random fields for which the proof of the Hammersley-Clifford theorem does not apply. Following Petersen and Schmidt we utilize the formalism of cocycles for the homoclinic equivalence relation and introduce "Markov cocycles", reparametrisations of Markov specifications. The main part of this paper exploits this to deduce the conclusion of the Hammersley-Clifford theorem for a family of Markov fields which are outside the theorem's purview where the underlying graph is $\mathbb{Z}^d$. This family includes all Markov random fields whose support is the d-dimensional "3-colored chessboard". On the other extreme, we construct a family of shift-invariant Markov random fields which are not given by any finite range shift-invariant interaction., 40 pages, 4 figures. Various typos corrected and proofs extended following suggestions by the referees

A Borel system $(X,S)$ is `almost Borel universal' if any free Borel dynamical system $(Y,T)$ of strictly lower entropy is isomorphic to a Borel subsystem of $(X,S)$, after removing a null set. We obtain and exploit a new sufficient condition for a topological dynamical system to be almost Borel universal. We use our main result to deduce various conclusions and answer a number of questions. Along with additional results, we prove that a `generic' homeomorphism of a compact manifold of topological dimension at least two can model any ergodic transformation, that non-uniform specification implies almost Borel universality, and that $3$-colorings in $\mathbb Z^d$ and dimers in $\mathbb Z^2$ are almost Borel universal, Revised after Referee's comments; 70 pages

Graph homomorphisms from the $\mathbb{Z}^d$ lattice to $\mathbb{Z}$ are functions on $\mathbb{Z}^d$ whose gradients equal one in absolute value. These functions are the height functions corresponding to proper $3$-colorings of $\mathbb{Z}^d$ and, in two dimensions, corresponding to the $6$-vertex model (square ice). We consider the uniform model, obtained by sampling uniformly such a graph homomorphism subject to boundary conditions. Our main result is that the model delocalizes in two dimensions, having no translation-invariant Gibbs measures. Additional results are obtained in higher dimensions and include the fact that every Gibbs measure which is ergodic under even translations is extremal and that these Gibbs measures are stochastically ordered., Comment: 21 pages, 2 Figures. Corrected Lemma 4.2 (Lemma 4.12 in the current version) from the previous version