Abstract
We prove that proper coloring distinguishes between block factors and finitely dependent stationary processes. A stochastic process is finitely dependent if variables at sufficiently wellseparated locations are independent; it is a block factor if it can be expressed as an equivariant finiterange function of independent variables. The problem of finding nonblockfactor finitely dependent processes dates back to 1965. The first published example appeared in 1993, and we provide arguably the first natural examples. Schramm proved in 2008 that no stationary 1dependent 3coloring of the integers exists, and asked whether a kdependentqcoloring exists for any k and q. We give a complete answer by constructing a 1dependent 4coloring and a 2dependent 3coloring. Our construction is canonical and natural, yet very different from all previous schemes. In its pure form it yields precisely the two finitely dependent colorings mentioned above, and no others. The processes provide unexpected connections between extremal cases of the Lovasz local lemma and descent and peak sets of random permutations. Neither coloring can be expressed as a block factor, nor as a function of a finitestate Markov chain; indeed, no stationary finitely dependent coloring can be so expressed. We deduce extensions involving d dimensions and shifts of finite type; in fact, any nondegenerate shift of finite type also distinguishes between block factors and finitely dependent processes.
Original language  English 

Article number  e9 
Number of pages  43 
Journal  Forum of Mathematics, Pi 
Volume  4 
DOIs  
Publication status  Published  3 Nov 2016 
Fingerprint
Dive into the research topics of 'Finitely dependent coloring'. Together they form a unique fingerprint.Profiles

Professor Alexander E Holroyd
Person: Academic