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

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.

DOI : 10.1214/10-AIHP399
Classification : 60C05, 60D05
Mots-clés : 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},
     pages = {327--342},
     publisher = {Gauthier-Villars},
     volume = {48},
     number = {2},
     year = {2012},
     doi = {10.1214/10-AIHP399},
     mrnumber = {2954257},
     zbl = {1258.60015},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1214/10-AIHP399/}
}
TY  - JOUR
AU  - Angel, Omer
AU  - Benjamini, Itai
AU  - Gurel-Gurevich, Ori
AU  - Meyerovitch, Tom
AU  - Peled, Ron
TI  - Stationary map coloring
JO  - Annales de l'I.H.P. Probabilités et statistiques
PY  - 2012
SP  - 327
EP  - 342
VL  - 48
IS  - 2
PB  - Gauthier-Villars
UR  - http://archive.numdam.org/articles/10.1214/10-AIHP399/
DO  - 10.1214/10-AIHP399
LA  - en
ID  - AIHPB_2012__48_2_327_0
ER  - 
%0 Journal Article
%A Angel, Omer
%A Benjamini, Itai
%A Gurel-Gurevich, Ori
%A Meyerovitch, Tom
%A Peled, Ron
%T Stationary map coloring
%J Annales de l'I.H.P. Probabilités et statistiques
%D 2012
%P 327-342
%V 48
%N 2
%I Gauthier-Villars
%U http://archive.numdam.org/articles/10.1214/10-AIHP399/
%R 10.1214/10-AIHP399
%G en
%F 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) no. 2, pp. 327-342. doi : 10.1214/10-AIHP399. http://archive.numdam.org/articles/10.1214/10-AIHP399/

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

[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

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

[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

[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

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

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

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

[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 | Zbl

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

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

[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

[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/.

Cité par Sources :