Stationary map coloring
Angel, Omer ; Benjamini, Itai ; Gurel-Gurevich, Ori ; Meyerovitch, Tom ; Peled, Ron
Annales de l'I.H.P. Probabilités et statistiques, Tome 48 (2012), p. 327-342 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

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.

Publié le : 2012-01-01
DOI : https://doi.org/10.1214/10-AIHP399
Classification:  60C05,  60D05 
@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},
     volume = {48},
     year = {2012},
     pages = {327-342},
     doi = {10.1214/10-AIHP399},
     mrnumber = {2954257},
     zbl = {1258.60015},
     language = {en},
     url = {http://dml.mathdoc.fr/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, Tome 48 (2012) pp. 327-342. doi : 10.1214/10-AIHP399. http://gdmltest.u-ga.fr/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/.