zbMATH — the first resource for mathematics

Finitely dependent coloring. (English) Zbl 1361.60025
Summary: 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. Schramm proved in 2008 (see [A. E. Holroyd, O. Schramm and D. B. Wilson, “Finitary coloring”, Preprint, arXiv:1412.2725] that no stationary 1-dependent 3-coloring of the integers exists, and asked whether a \(k\)-dependent \(q\)-coloring exists for any \(k\) and \(q\). We give a complete answer by constructing a 1-dependent 4-coloring and a 2-dependent 3-coloring. 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 Lovász 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 block factors and finitely dependent processes.

60G10 Stationary stochastic processes
05C15 Coloring of graphs and hypergraphs
60C05 Combinatorial probability
Full Text: DOI arXiv
[1] Aaronson, J., Gilat, D. and Keane, M., ‘On the structure of 1-dependent Markov chains’, J. Theoret. Probab.5(3) (1992), 545-561. · Zbl 0754.60070
[2] Aaronson, J., Gilat, D., Keane, M. and De Valk, V., ‘An algebraic construction of a class of one-dependent processes’, Ann. Probab.17(1) (1989), 128-143. · Zbl 0681.60038
[3] Alon, N. and Feldheim, O. N., ‘A note on general sliding window processes’, Electron. Commun. Probab.19(66) (2014), 1-7. · Zbl 1300.60043
[4] Alon, N. and Spencer, J. H., The Probabilistic Method, 3rd edn, , (John Wiley & Sons, Inc., Hoboken, NJ, 2008), With an appendix on the life and work of Paul Erdős. · Zbl 1148.05001
[5] Billey, S., Burdzy, K. and Sagan, B. E., ‘Permutations with given peak set’, J. Integer Seq.16(6) (2013), Article 13.6.1, 18. · Zbl 1295.05008
[6] Borodin, A., Diaconis, P. and Fulman, J., ‘On adding a list of numbers (and other one-dependent determinantal processes)’, Bull. Amer. Math. Soc. (N.S.)47(4) (2010), 639-670. · Zbl 1230.05292
[7] Broman, E. I., One-dependent trigonometric determinantal processes are two-block-factors, Ann. Probab., 33, 2, 601-609, (2005) · Zbl 1067.60010
[8] Burton, R. M., Goulet, M. and Meester, R., ‘On 1-dependent processes and k-block factors’, Ann. Probab.21(4) (1993), 2157-2168. · Zbl 0788.60049
[9] De Valk, V., A problem on 0-1 matrices, Compositio Math., 71, 2, 139-179, (1989) · Zbl 0741.15007
[10] De Valk, V., Hilbert space representations of m-dependent processes, Ann. Probab., 21, 3, 1550-1570, (1993) · Zbl 0802.60034
[11] Duminil-Copin, H. and Tassion, V., ‘A new proof of the sharpness of the phase transition for Bernoulli percolation and the Ising model’, Comm. Math. Phys.343(2) (2016), 725-745. · Zbl 1342.82026
[12] Edelman, P., Hibi, T. and Stanley, R. P., ‘A recurrence for linear extensions’, Order6(1) (1989), 15-18. · Zbl 0692.06001
[13] ErdőS, P. and Lovász, L., ‘Problems and results on 3-chromatic hypergraphs and some related questions’, inInfinite and Finite Sets, Vol. II, (North-Holland, Amsterdam, 1975), 609-627.
[14] Flajolet, P. and Sedgewick, R., Analytic Combinatorics (Cambridge University Press, Cambridge, 2009). · Zbl 1165.05001
[15] Gandolfi, A., Keane, M. and De Valk, V., ‘Extremal two-correlations of two-valued stationary one-dependent processes’, Probab. Theory Related Fields80(3) (1989), 475-480. · Zbl 0638.60056
[16] Götze, F. and Hipp, C., ‘Asymptotic expansions for potential functions of i.i.d. random fields’, Probab. Theory Related Fields82(3) (1989), 349-370. · Zbl 0659.60035
[17] Haiman, M. G., Valeurs extrémales de suites stationnaires de variables aléatoires m-dépendantes, Ann. Inst. H. Poincaré Sect. B (N.S.), 17, 3, 309-330, (1981) · Zbl 0479.60044
[18] Heinrich, L., Asymptotic expansions in the central limit theorem for a special class of m-dependent random fields. II. Lattice case, Math. Nachr., 145, 309-327, (1990) · Zbl 0705.60025
[19] Hoeffding, W. and Robbins, H., ‘The central limit theorem for dependent random variables’, Duke Math. J.15 (1948), 773-780. · Zbl 0031.36701
[20] Holroyd, A. E., One-dependent coloring by finitary factors. Ann. Inst. Henri Poincaré, arXiv:1411.1463.
[21] Holroyd, A. E. and Liggett, T. M., ‘Symmetric 1-dependent colorings of the integers’, Electron. Commun. Probab.20(31) (2015), 1-8. · Zbl 1385.60014
[22] Holroyd, A. E., Schramm, O. and Wilson, D. B., Finitary coloring. Ann. Probab., arXiv:1412.2725.
[23] Ibragimov, I. A. and Linnik, Yu. V., Nezavisimye stalionarno svyazannye velichiny, , (Nauka, Moscow, 1965). · Zbl 0154.42201
[24] Ibragimov, I. A. and Linnik, Yu. V., Independent and Stationary Sequences of Random Variables (Wolters-Noordhoff Publishing, Groningen, 1971), With a supplementary chapter by I. A. Ibragimov and V. V. Petrov, Translation from the Russian edited by J. F. C. Kingman. · Zbl 0219.60027
[25] Janson, S., Renewal theory for M-dependent variables, Ann. Probab., 11, 3, 558-568, (1983) · Zbl 0514.60086
[26] Janson, S., Runs in m-dependent sequences, Ann. Probab., 12, 3, 805-818, (1984) · Zbl 0545.60080
[27] Janson, S., On degenerate sums of m-dependent variables, J. Appl. Probab., 52, 4, 1146-1155, (2015) · Zbl 1334.60021
[28] Kallenberg, O., Foundations of Modern Probability, (2002), Springer: Springer, New York · Zbl 0996.60001
[29] Karlin, S., Total Positivity, Vol. I, (1968), Stanford University Press: Stanford University Press, Stanford, CA · Zbl 0219.47030
[30] Lax, P. D., Functional Analysis, Pure and Applied Mathematics, (2002), Wiley-Interscience: Wiley-Interscience, New York · Zbl 1009.47001
[31] Levit, V. E. and Mandrescu, E., ‘The independence polynomial of a graph—a survey’, inProceedings of the 1st International Conference on Algebraic Informatics (Aristotle Univ. Thessaloniki, Thessaloniki, 2005), 233-254.
[32] Liggett, T. M., Schonmann, R. H. and Stacey, A. M., ‘Domination by product measures’, Ann. Probab.25(1) (1997), 71-95. · Zbl 0882.60046
[33] Linial, N., ‘Distributive graph algorithms—global solutions from local data’, in28th Annual Symposium on Foundations of Computer Science (IEEE, 1987), 331-335.
[34] Mallows, C. and Shepp, L., ‘The necklace process’, J. Appl. Probab.45(1) (2008), 271-278. · Zbl 1213.60027
[35] Matúš, F., On two-block-factor sequences and one-dependence, Proc. Amer. Math. Soc., 124, 4, 1237-1242, (1996) · Zbl 0843.60036
[36] Matúš, F., Combining m-dependence with Markovness, Ann. Inst. Henri Poincaré Probab. Stat., 34, 4, 407-423, (1998) · Zbl 0910.60055
[37] Nakata, T., Necklace processes via Pólya urns, J. Appl. Probab., 46, 1, 284-295, (2009) · Zbl 1160.60303
[38] Naor, M., A lower bound on probabilistic algorithms for distributive ring coloring, SIAM J. Discrete Math., 4, 3, 409-412, (1991) · Zbl 0738.68007
[39] Niven, I., A combinatorial problem of finite sequences, Nieuw Arch. Wiskd. (3), 16, 116-123, (1968) · Zbl 0164.33102
[40] O’Brien, G. L., Scaling transformations for 0, 1-valued sequences, Z. Wahrsch. Verw. Gebiete, 53, 1, 35-49, (1980) · Zbl 0417.60035
[41] Rüschendorf, L. and De Valk, V., ‘On regression representations of stochastic processes’, Stochastic Process. Appl.46(2) (1993), 183-198. · Zbl 0779.60058
[42] Scott, A. D. and Sokal, A. D., ‘The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma’, J. Stat. Phys.118(5-6) (2005), 1151-1261. · Zbl 1107.82013
[43] Scott, A. D. and Sokal, A. D., ‘On dependency graphs and the lattice gas’, Combin. Probab. Comput.15(1-2) (2006), 253-279. · Zbl 1138.05323
[44] Shearer, J. B., On a problem of Spencer, Combinatorica, 5, 3, 241-245, (1985) · Zbl 0587.60012
[45] Titchmarsh, E. C., The Theory of Functions, (1939), Oxford University Press · JFM 65.0302.01
[46] Todo, S., Transfer-matrix study of negative-fugacity singularity of hard-core lattice gas, Internat. J. Modern Phys. C, 10, 4, 517-529, (1999) · Zbl 0940.82012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.