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

coloringshift of finite typefinitary factortower function

Mathematics Subject Classification ID

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

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

(15)

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

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)