Finitary coloring

DOI10.1214/16-AOP1127MaRDI QIDQ1681594zbMATH OpenOpenAlexFDO

Authors A. E. Holroyd, Oded Schramm, David B. Wilson

Publication date 24 November 2017

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.2725, https://projecteuclid.org/euclid.aop/1506132029

zbMATH Keywords

coloringfinitary factorshift of finite typetower function

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Dynamical systems and their relations with probability theory and stochastic processes (37A50) Stationary stochastic processes (60G10)

Abstract: Suppose that the vertices of ${mathbbZ}^d$ are assigned random colors via a finitary factor of independent identically distributed (iid) vertex-labels. That is, the color of vertex $v$ is determined by a rule that examines the labels within a finite (but random and perhaps unbounded) distance $R$ of $v$, and the same rule applies at all vertices. We investigate the tail behavior of $R$ if the coloring is required to be proper (that is, if adjacent vertices must receive different colors). When $dgeq2$, the optimal tail is given by a power law for 3 colors, and a tower (iterated exponential) function for 4 or more colors (and also for 3 or more colors when $d=1$). If proper coloring is replaced with any shift of finite type in dimension 1, then, apart from trivial cases, tower function behavior also applies.

Recommendations

• One-dependent coloring by finitary factors
• Finitely dependent coloring
• Mallows permutations and finite dependence
• Finitely dependent cycle coloring
• Finitely dependent insertion processes

Cited in

(17)

• Local mending
• Distributed algorithms for fractional coloring
• Finitary isomorphisms of renewal point processes and continuous-time regenerative processes
• Mallows permutations and finite dependence
• What can be sampled locally?
• One-dependent coloring by finitary factors
• Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022
• Finitely dependent coloring
• scientific article; zbMATH DE number 5035591 (Why is no real title available?)
• Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
• Uniform even subgraphs and graphical representations of Ising as factors of i.i.d.
• One-dependent colorings of the star graph
• Symmetrization for finitely dependent colouring
• Finitely dependent random colorings of bounded degree graphs
• Large-scale geometry of Borel graphs of polynomial growth
• Finitely dependent processes are finitary
• Finitary codings for spatial mixing Markov random fields

This page was built for publication: Finitary coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1681594)