An open problem is to determine which MRFs are ffiid.
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.