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

Voir la notice de l'article provenant de la source Numdam

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 : 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},
     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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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. | Zbl | MR

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

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

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

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

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

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

[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. | Zbl | MR | mathdoc-id

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

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

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

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

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

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

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