More Like this

1. Equitable colourings of Borel graphs

   https://doi.org/10.1017/fmp.2021.12  

   Bernshteyn, Anton; Conley, Clinton T. (January 2021, Forum of Mathematics, Pi)

   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
2. New upper bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers

   https://doi.org/10.1017/S0963548322000293  

   Cameron, Alex; Heath, Emily (March 2023, Combinatorics, Probability and Computing)

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

   more » « less
3. Constraining the clustering transition for colorings of sparse random graphs

   Anastos, M.; Frieze, A.; Pegden, W. (January 2018, The electronic journal of combinatorics)

   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
4. A model of d -wave superconductivity, antiferromagnetism, and charge order on the square lattice

   https://doi.org/10.1073/pnas.2302701120  

   Christos, Maine; Luo, Zhu-Xi; Shackleton, Henry; Zhang, Ya-Hui; Scheurer, Mathias_S; Sachdev, Subir (May 2023, Proceedings of the National Academy of Sciences)

   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 ofN_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 ℤ₂center of SU(2). This theory has an emergent SO(5)_fglobal symmetry and is presumed to confine at low energies to the Néel state. At nonzero doping (or smaller Hubbard repulsionUat half-filling), we argue that confinement occurs via the Higgs condensation of bosonic chargons carrying fundamental SU(2) gauge charges also moving inπℤ₂-flux. At half-filling, the low-energy theory of the Higgs sector hasN_b= 2 relativistic bosons with a possible emergent SO(5)_bglobal 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)_bglobal symmetry, which describes a deconfined quantum critical point between a confining state which breaks SO(5)_fand 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. 

   more » « less
5. A deterministic near-linear time approximation scheme for geometric transportation

   https://doi.org/10.1109/FOCS57990.2023.00078  

   Fox, Emily; Lu, Jiashuai (November 2023, IEEE)

   Given a set of points $$P = (P^+ \sqcup P^-) \subset \mathbb{R}^d$$ for some constant $$d$$ and a supply function $$\mu:P\to \mathbb{R}$$ such that $$\mu(p) > 0~\forall p \in P^+$$, $$\mu(p) < 0~\forall p \in P^-$$, and $$\sum_{p\in P}{\mu(p)} = 0$$, the geometric transportation problem asks one to find a transportation map $$\tau: P^+\times P^-\to \mathbb{R}_{\ge 0}$$ such that $$\sum_{q\in P^-}{\tau(p, q)} = \mu(p)~\forall p \in P^+$$, $$\sum_{p\in P^+}{\tau(p, q)} = -\mu(q) \forall q \in P^-$$, and the weighted sum of Euclidean distances for the pairs $$\sum_{(p,q)\in P^+\times P^-}\tau(p, q)\cdot ||q-p||_2$$ is minimized. We present the first deterministic algorithm that computes, in near-linear time, a transportation map whose cost is within a $$(1 + \varepsilon)$$ factor of optimal. More precisely, our algorithm runs in $$O(n\varepsilon^{-(d+2)}\log^5{n}\log{\log{n}})$$ time for any constant $$\varepsilon > 0$$. While a randomized $$n\varepsilon^{-O(d)}\log^{O(d)}{n}$$ time algorithm for this problem was discovered in the last few years, all previously known deterministic $$(1 + \varepsilon)$$-approximation algorithms run in~$$\Omega(n^{3/2})$$ time. A similar situation existed for geometric bipartite matching, the special case of geometric transportation where all supplies are unit, until a deterministic $$n\varepsilon^{-O(d)}\log^{O(d)}{n}$$ time $$(1 + \varepsilon)$$-approximation algorithm was presented at STOC 2022. Surprisingly, our result is not only a generalization of the bipartite matching one to arbitrary instances of geometric transportation, but it also reduces the running time for all previously known $$(1 + \varepsilon)$$-approximation algorithms, randomized or deterministic, even for geometric bipartite matching. In particular, we give the first $$(1 + \varepsilon)$$-approximate deterministic algorithm for geometric bipartite matching and the first $$(1 + \varepsilon)$$-approximate deterministic or randomized algorithm for geometric transportation with no dependence on $$d$$ in the exponent of the running time's polylog. As an additional application of our main ideas, we also give the first randomized near-linear $$O(\varepsilon^{-2} m \log^{O(1)} n)$$ time $$(1 + \varepsilon)$$-approximation algorithm for the uncapacitated minimum cost flow (transshipment) problem in undirected graphs with arbitrary \emph{real} edge costs. 

   more » « less