ProbXiv
Explorersign in
Problem archiveProblem record

Statement

An open problem is to determine which MRFs are ffiid. factors with bounded coding radius) of i.i.d. processes. More interesting examples, which are not block factors of i.i.d. processes, are the 1-dependent 4-coloring and 2-dependent 3-coloring of Z constructed by Holroyd and Liggett [5]. A result of Smorodinsky [8] shows that finitely dependent invariant processes on Z are ffiid. This was extended by the author to all dimensions and in fact holds for any transitive amenable graph [9]. The proof in [9] shows that for one dimensional processes the coding radius R satisfies P(R > r) \leq Cr , which falls just short of showing that the coding radius has finite expectation. An interesting open problem is whether there exists a finitely dependent invariant process which cannot be expressed as an ffiid with finite expected coding radius. The 1-dependent 4-coloring and 2-dependent 3- coloring from [5] are potential such candidates (see [4]). Descriptive Combinatorics, LOCAL Algorithms and Random Processes 449

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.