Finitely dependent coloring
From MaRDI portal
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 well-separated locations are independent; it is a block-factor if it can be expressed as an equivariant 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 1993, 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 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 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 non-degenerate shift of finite type also distinguishes between block-factors and finitely dependent processes.
Recommendations
Cites work
- A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
- A new proof of the sharpness of the phase transition for Bernoulli percolation and the Ising model
- A note on general sliding window processes
- A recurrence for linear extensions
- An algebraic construction of a class of one-dependent processes
- Analytic combinatorics
- Asymptotic expansions for potential functions of I.I.D. random fields
- Asymptotic Expansions in the Central Limit Theorem for a Special Class ofm-Dependent Random Fields II – Lattice Case
- Combining \(m\)-dependence with Markovness
- Domination by product measures
- Extremal two-correlations of two-valued stationary one-dependent processes
- Finitary coloring
- Hilbert space representations of \(m\)-dependent processes
- scientific article; zbMATH DE number 1713116 (Why is no real title available?)
- scientific article; zbMATH DE number 3753778 (Why is no real title available?)
- scientific article; zbMATH DE number 7391 (Why is no real title available?)
- scientific article; zbMATH DE number 3492718 (Why is no real title available?)
- scientific article; zbMATH DE number 1745905 (Why is no real title available?)
- scientific article; zbMATH DE number 3248575 (Why is no real title available?)
- scientific article; zbMATH DE number 3263280 (Why is no real title available?)
- scientific article; zbMATH DE number 3348831 (Why is no real title available?)
- scientific article; zbMATH DE number 3349105 (Why is no real title available?)
- Necklace Processes Via Pólya Urns
- On 1-dependent processes and k-block factors
- On a problem of Spencer
- On adding a list of numbers (and other one-dependent determinantal processes)
- On degenerate sums of m-dependent variables
- On Dependency Graphs and the Lattice Gas
- On regression representations of stochastic processes
- On the structure of 1-dependent Markov chains
- On two–block–factor sequences and one–dependence
- One-dependent coloring by finitary factors
- One-dependent trigonometric determinantal processes are two-block-factors
- Permutations with given peak set
- Renewal theory for m-dependent variables
- Runs in m-dependent sequences
- Scaling transformations for {0, 1}-valued sequences
- Symmetric 1-dependent colorings of the integers
- The central limit theorem for dependent random variables
- The Necklace Process
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- TRANSFER-MATRIX STUDY OF NEGATIVE-FUGACITY SINGULARITY OF HARD-CORE LATTICE GAS
Cited in
(16)- Finitary coloring
- Finitely dependent cycle coloring
- Stationary distributions for the Voter model in \(d\geq 3\) are factors of IID
- Mallows permutations and finite dependence
- One-dependent coloring by finitary factors
- Long paths and connectivity in 1-independent random graphs
- DOWNWARD UNARY COLORINGS
- Finitely dependent insertion processes
- CLT with explicit variance for products of random singular matrices related to Hill's equation
- Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
- One-dependent colorings of the star graph
- On connectivity in random graph models with limited dependencies
- Symmetrization for finitely dependent colouring
- Finitely dependent random colorings of bounded degree graphs
- Shared randomness helps with local distributed problems
- Finitely dependent processes are finitary
This page was built for publication: Finitely dependent coloring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2971028)
