Finitely Dependent Coloring

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 a finite-range function of independent variables. The problem of finding non-block-factor finitely dependent processes dates back to 1965. The first published example appeared in 1989, and we provide arguably the first natural examples. More precisely, Schramm proved in 2008 that no stationary 1-dependent 3-coloring of the integers exists, and conjectured that no stationary k-dependent q-coloring exists for any k and q. We disprove this by constructing a 1-dependent 4-coloring and a 2-dependent 3-coloring, thus resolving the question for all k and q.

Our construction is canonical and natural, yet very different from all previous schemes. In its pure form it yields precisely the two colorings mentioned above, and no others. The processes provide unexpected connections between extremal cases of the Lov´asz 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 finite-state 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 blockfactors and finitely dependent processes.