Fetching the paper…

Reading the bibliography…

2014

One-dependent coloring by finitary factors

Holroyd, Alexander E.

Original
PDF
Post on X

Understand

Holroyd and Liggett recently proved the existence of a stationary 1-dependent 4-coloring of the integers, the first stationary k-dependent q-coloring for any k and q.

That proof specifies a consistent family of finite-dimensional distributions, but does not yield a probabilistic construction on the whole integer line.
Here we prove that the process can be expressed as a finitary factor of an i.i.d.
process.

One-dependent coloring by finitary factors · Around

Built on

Runs in m m -dependent sequences
S. Janson · 1984
Earlier work this paper cites.
Distributive graph algorithms – global solutions from local data
N. Linial · 1987
Earlier work this paper cites.
An algebraic construction of a class of one-dependent processes
J. Aaronson, D. Gilat, M. Keane, and V. de Valk · 1989
Earlier work this paper cites.

Similar

A lower bound on probabilistic algorithms for distributive ring coloring
M. Naor · 1991
Cited alongside, same era.
Finitary coloring
A. E. Holroyd, O. Schramm, and D. B. Wilson · 2008
Cited alongside, same era.
On adding a list of numbers (and other one-dependent determinantal processes)
A. Borodin, P. Diaconis, and J. Fulman · 2010
Cited alongside, same era.

Then

Probability: theory and examples
R. Durrett · 2010
Later among the works it cites.
Finitely dependent coloring
Original
A. E. Holroyd and T. M. Liggett · 2014
Closest in time.
Symmetric 1-dependent colorings of the integers
Original
A. E. Holroyd and T. M. Liggett · 2014
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…