Abstract Hajnal and Szemerédi proved that if G is a finite graph with maximum degree $\Delta $ , then for every integer $k \geq \Delta +1$ , G has a proper colouring with k colours in which every two colour classes differ in size at most by $1$ ; such colourings are called equitable. We obtain an analogue of this result for infinite graphs in the Borel setting. Specifically, we show that if G is an aperiodic Borel graph of finite maximum degree $\Delta $ , then for each $k \geq \Delta + 1$ , G has a Borel proper k -colouring in which every two colour classes are related by an element of the Borel full semigroup of G . In particular, such colourings are equitable with respect to every G -invariant probability measure. We also establish a measurable version of a result of Kostochka and Nakprasit on equitable $\Delta $ -colourings of graphs with small average degree. Namely, we prove that if $\Delta \geq 3$ , G does not contain a clique on $\Delta + 1$ vertices and $\mu $ is an atomless G -invariant probability measure such that the average degree of G with respect to $\mu $ is at most $\Delta /5$ , then G has a $\mu $ -equitable $\Delta $ -colouring. As steps toward the proof of this result, we establish measurable and list-colouring extensions of a strengthening of Brooks’ theorem due to Kostochka and Nakprasit.
more »
« less
Mixing properties of colourings of the ℤ d lattice
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 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.
more »
« less
- Award ID(s):
- 1855464
- NSF-PAR ID:
- 10338572
- Date Published:
- Journal Name:
- Combinatorics, Probability and Computing
- Volume:
- 30
- Issue:
- 3
- ISSN:
- 0963-5483
- Page Range / eLocation ID:
- 360 to 373
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
Abstract A
$(p,q)$ $G$ $G$ $q$ $p$ $f(n,p,q)$ $(p,q)$ $K_n$ $r_k(p)$ $f(n,p,q)$ $p=q$ $p\in \{4,5\}$ $(p,p-1)$ In this paper, we provide a framework for proving new upper bounds on
$f(n,p,p)$ $p$ $p-1$ $(p,p-1)$ $(p,p)$ $p$ $p=5$ $f(n,6,6)$ $f(n,8,8)$ -
Let $\Omega_q$ denote the set of proper $[q]$-colorings of the random graph $G_{n,m}, m=dn/2$ and let $H_q$ be the graph with vertex set $\Omega_q$ and an edge $\set{\s,\t}$ where $\s,\t$ are mappings $[n]\to[q]$ iff $h(\s,\t)=1$. Here $h(\s,\t)$ is the Hamming distance $|\set{v\in [n]:\s(v)\neq\t(v)}|$. We show that w.h.p. $H_q$ contains a single giant component containing almost all colorings in $\Omega_q$ if $d$ is sufficiently large and $q\geq \frac{cd}{\log d}$ for a constant $c>3/2$.more » « less
-
more » « less
We describe the confining instabilities of a proposed quantum spin liquid underlying the pseudogap metal state of the hole-doped cuprates. The spin liquid can be described by a SU(2) gauge theory of
N f = 2 massless Dirac fermions carrying fundamental gauge charges—this is the low-energy theory of a mean-field state of fermionic spinons moving on the square lattice withπ -flux per plaquette in the ℤ2center of SU(2). This theory has an emergent SO(5)f global symmetry and is presumed to confine at low energies to the Néel state. At nonzero doping (or smaller Hubbard repulsionU at half-filling), we argue that confinement occurs via the Higgs condensation of bosonic chargons carrying fundamental SU(2) gauge charges also moving inπ ℤ2-flux. At half-filling, the low-energy theory of the Higgs sector hasN b = 2 relativistic bosons with a possible emergent SO(5)b global symmetry describing rotations between ad -wave superconductor, period-2 charge stripes, and the time-reversal breaking “d -density wave” state. We propose a conformal SU(2) gauge theory withN f = 2 fundamental fermions,N b = 2 fundamental bosons, and a SO(5)f ×SO(5)b global symmetry, which describes a deconfined quantum critical point between a confining state which breaks SO(5)f and a confining state which breaks SO(5)b . The pattern of symmetry breaking within both SO(5)s is determined by terms likely irrelevant at the critical point, which can be chosen to obtain a transition between Néel order andd -wave superconductivity. A similar theory applies at nonzero doping and largeU , with longer-range couplings of the chargons leading to charge order with longer periods. -
Let Ωq denote the set of proper [q]-colorings of the random graph Gn,m,m=dn/2 and let Hq be the graph with vertex set Ωq and an edge {σ,τ} where σ,τ are mappings [n]→[q] iff h(σ,τ)=1. Here h(σ,τ) is the Hamming distance |{v∈[n]:σ(v)≠τ(v)}|. We show that w.h.p. Hq contains a single giant component containing almost all colorings in Ωq if d is sufficiently large and q≥cdlogd for a constant c>3/2.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/s0963548320000395
