 Award ID(s):
 1855464
 NSFPAR ID:
 10338572
 Date Published:
 Journal Name:
 Combinatorics, Probability and Computing
 Volume:
 30
 Issue:
 3
 ISSN:
 09635483
 Page Range / eLocation ID:
 360 to 373
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

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 listcolouring extensions of a strengthening of Brooks’ theorem due to Kostochka and Nakprasit.more » « less

Abstract A
colouring of a graph$(p,q)$ is an edgecolouring of$G$ which assigns at least$G$ colours to each$q$ clique. The problem of determining the minimum number of colours,$p$ , needed to give a$f(n,p,q)$ colouring of the complete graph$(p,q)$ is a natural generalization of the wellknown problem of identifying the diagonal Ramsey numbers$K_n$ . The bestknown general upper bound on$r_k(p)$ was given by Erdős and Gyárfás in 1997 using a probabilistic argument. Since then, improved bounds in the cases where$f(n,p,q)$ have been obtained only for$p=q$ , each of which was proved by giving a deterministic construction which combined a$p\in \{4,5\}$ colouring using few colours with an algebraic colouring.$(p,p1)$ In this paper, we provide a framework for proving new upper bounds on
in the style of these earlier constructions. We characterize all colourings of$f(n,p,p)$ cliques with$p$ colours which can appear in our modified version of the$p1$ colouring of Conlon, Fox, Lee, and Sudakov. This allows us to greatly reduce the amount of casechecking required in identifying$(p,p1)$ colourings, which would otherwise make this problem intractable for large values of$(p,p)$ . In addition, we generalize our algebraic colouring from the$p$ setting and use this to give improved upper bounds on$p=5$ and$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

We describe the confining instabilities of a proposed quantum spin liquid underlying the pseudogap metal state of the holedoped 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 lowenergy theory of a meanfield state of fermionic spinons moving on the square lattice withπ flux per plaquette in the ℤ_{2}center 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 halffilling), we argue that confinement occurs via the Higgs condensation of bosonic chargons carrying fundamental SU(2) gauge charges also moving inπ ℤ_{2}flux. At halffilling, the lowenergy 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, period2 charge stripes, and the timereversal 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 longerrange 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