Stationary map coloring
Annales de l'I.H.P. Probabilités et statistiques, Volume 48 (2012) no. 2, p. 327-342

We consider a planar Poisson process and its associated Voronoi map. We show that there is a proper coloring with 6 colors of the map which is a deterministic isometry-equivariant function of the Poisson process. As part of the proof we show that the 6-core of the corresponding Delaunay triangulation is empty. Generalizations, extensions and some open questions are discussed.

Nous étudions un processus de Poisson planaire et sa partition de Voronoi associée. Nous montrons qu'il existe une coloration à six couleurs de cette partition satisfaisant les deux propriétés suivantes : la coloration est une fonction déterministe du processus de Poisson. Par ailleurs, elle commute avec les isométries du plan. Une partie de la preuve consiste à montrer que le “6-core” de la triangulation de Delaunay associée est vide. Des généralisations, extensions et problèmes ouverts sont discutés.

DOI : https://doi.org/10.1214/10-AIHP399
Classification:  60C05,  60D05
Keywords: Poisson process, graph coloring, planar graphs, Voronoi tessellation, Delaunay triangulation, percolation
@article{AIHPB_2012__48_2_327_0,
     author = {Angel, Omer and Benjamini, Itai and Gurel-Gurevich, Ori and Meyerovitch, Tom and Peled, Ron},
     title = {Stationary map coloring},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     publisher = {Gauthier-Villars},
     volume = {48},
     number = {2},
     year = {2012},
     pages = {327-342},
     doi = {10.1214/10-AIHP399},
     zbl = {1258.60015},
     mrnumber = {2954257},
     language = {en},
     url = {http://www.numdam.org/item/AIHPB_2012__48_2_327_0}
}
Angel, Omer; Benjamini, Itai; Gurel-Gurevich, Ori; Meyerovitch, Tom; Peled, Ron. Stationary map coloring. Annales de l'I.H.P. Probabilités et statistiques, Volume 48 (2012) no. 2, pp. 327-342. doi : 10.1214/10-AIHP399. http://www.numdam.org/item/AIHPB_2012__48_2_327_0/

[1] O. Angel, G. Amir and A. Holroyd. Multi-color matching. Unpublished manuscript.

[2] O. Angel, A. Holroyd and T. Soo. Deterministic thinning of finite Poisson processes. Proc. Amer. Math. Soc. 139 (2011) 707-720. | MR 2736350 | Zbl 1208.60047

[3] K. Ball. Poisson thinning by monotone factors. Electron. Comm. Probab. 10 (2005) 60-69 (electronic). | MR 2133893 | Zbl 1110.60050

[4] I. Benjamini, A. Holroyd, O. Schramm and D. Wilson. Finitary coloring. Unpublished manuscript.

[5] B. Bollobás and O. Riordan. The critical probability for random Voronoi percolation in the plane is 1/2. Probab. Theory Related Fields 136 (2006) 417-468. | MR 2257131 | Zbl 1100.60054

[6] S. Chatterjee, R. Peled, Y. Peres and D. Romik. Phase transitions in gravitational allocation. Preprint. Available at http://arxiv.org/abs/0903.4647. | MR 2729280 | Zbl 1209.60008

[7] S. Chatterjee, R. Peled, Y. Peres and D. Romik. Gravitational allocation to Poisson points. Ann. of Math. (2) 172 (2010) 617-671. | MR 2680428 | Zbl 1206.60013

[8] D. J. Daley and G. Last. Descending chains, the lilypond model, and mutual-nearest-neighbour matching. Adv. in Appl. Probab. 37 (2005) 604-628. | MR 2156551 | Zbl 1078.60038

[9] M. Deijfen and R. Meester. Generating stationary random graphs on ℤ with prescribed independent, identically distributed degrees. Adv. in Appl. Probab. 38 (2006) 287-298. | MR 2264945 | Zbl 1102.05054

[10] A. K. Dewdney and J. K. Vranch. A convex partition of R3 with applications to Crum's problem and Knuth's post-office problem. Utilitas Math. 12 (1977) 193-199. | Zbl 0367.52004

[11] C. Hoffman, A. E. Holroyd and Y. Peres. A stable marriage of Poisson and Lebesgue. Ann. Probab. 34 (2006) 1241-1272. | Zbl 1111.60008

[12] C. Hoffman, A. E. Holroyd and Y. Peres. Tail bounds for the stable marriage of Poisson and Lebesgue. Canad. J. Math. 61 (2009) 1279-1299. | Zbl 1191.60015

[13] A. Holroyd, R. Lyons and T. Soo. Poisson splitting by factors. Ann. Probab. To appear. Available at http://arxiv.org/abs/0908.3409. | Zbl 1277.60087

[14] A. Holroyd, R. Pemantle, Y. Peres and O. Schramm. Poisson matching. Ann. Inst. H. Poincaré Probab. Statist. 45 (2009) 266-287. | Numdam | MR 2500239 | Zbl 1175.60012

[15] A. E. Holroyd and Y. Peres. Trees and matchings from point processes. Electron. Comm. Probab. 8 (2003) 17-27 (electronic). | MR 1961286 | Zbl 1060.60048

[16] A. E. Holroyd and Y. Peres. Extra heads and invariant allocations. Ann. Probab. 33 (2005) 31-52. | MR 2118858 | Zbl 1097.60032

[17] G. Kozma. Private communication, 2007.

[18] M. Krikun. Connected allocation to Poisson points in ℝ2. Electron. Comm. Probab. 12 (2007) 140-145 (electronic). | MR 2318161 | Zbl 1128.60012

[19] K. Kunen. Set Theory: An Introduction to Independence Proofs. Studies in Logic and the Foundations of Mathematics 102. North-Holland, Amsterdam, 1980. | MR 597342 | Zbl 0443.03021

[20] T. M. Liggett, R. H. Schonmann and A. M. Stacey. Domination by product measures. Ann. Probab. 25 (1997) 71-95. | MR 1428500 | Zbl 0882.60046

[21] R. Lyons. Private communication, 2007.

[22] F. P. Preparata. Steps into computational geometry. Technical report, Coordinated Science Laboratory, Univ. Illinois, 1977.

[23] A. Timár. Invariant colorings of random planar graphs. Preprint. Available at arXiv:0909.1091. | Zbl 1223.05086

[24] A. Timár. Invariant matchings of exponential tail on coin flips in ℤd. Preprint. Available at arXiv:0909.1090.

[25] A. Zvavitch. The critical probability for Voronoi percolation. Master's thesis, Weizmann Institute of Science, 1996. Available at http://www.math.kent.edu/~zvavitch/.