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.
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://www.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://www.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://www.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://www.numdam.org/articles/10.1214/10-AIHP399/
[1] Multi-color matching. Unpublished manuscript.
, and .[2] Deterministic thinning of finite Poisson processes. Proc. Amer. Math. Soc. 139 (2011) 707-720. | MR | Zbl
, and .[3] Poisson thinning by monotone factors. Electron. Comm. Probab. 10 (2005) 60-69 (electronic). | EuDML | MR | Zbl
.[4] Finitary coloring. Unpublished manuscript.
, , and .[5] The critical probability for random Voronoi percolation in the plane is 1/2. Probab. Theory Related Fields 136 (2006) 417-468. | MR | Zbl
and .[6] Phase transitions in gravitational allocation. Preprint. Available at http://arxiv.org/abs/0903.4647. | MR | Zbl
, , and .[7] Gravitational allocation to Poisson points. Ann. of Math. (2) 172 (2010) 617-671. | MR | Zbl
, , and .[8] Descending chains, the lilypond model, and mutual-nearest-neighbour matching. Adv. in Appl. Probab. 37 (2005) 604-628. | MR | Zbl
and .[9] Generating stationary random graphs on ℤ with prescribed independent, identically distributed degrees. Adv. in Appl. Probab. 38 (2006) 287-298. | MR | Zbl
and .[10] A convex partition of R3 with applications to Crum's problem and Knuth's post-office problem. Utilitas Math. 12 (1977) 193-199. | Zbl
and .[11] A stable marriage of Poisson and Lebesgue. Ann. Probab. 34 (2006) 1241-1272. | Zbl
, and .[12] Tail bounds for the stable marriage of Poisson and Lebesgue. Canad. J. Math. 61 (2009) 1279-1299. | Zbl
, and .[13] Poisson splitting by factors. Ann. Probab. To appear. Available at http://arxiv.org/abs/0908.3409. | Zbl
, and .[14] Poisson matching. Ann. Inst. H. Poincaré Probab. Statist. 45 (2009) 266-287. | Numdam | MR | Zbl
, , and .[15] Trees and matchings from point processes. Electron. Comm. Probab. 8 (2003) 17-27 (electronic). | MR | Zbl
and .[16] Extra heads and invariant allocations. Ann. Probab. 33 (2005) 31-52. | MR | Zbl
and .[17] Private communication, 2007.
.[18] Connected allocation to Poisson points in ℝ2. Electron. Comm. Probab. 12 (2007) 140-145 (electronic). | MR | Zbl
.[19] Set Theory: An Introduction to Independence Proofs. Studies in Logic and the Foundations of Mathematics 102. North-Holland, Amsterdam, 1980. | MR | Zbl
.[20] Domination by product measures. Ann. Probab. 25 (1997) 71-95. | MR | Zbl
, and .[21] Private communication, 2007.
.[22] Steps into computational geometry. Technical report, Coordinated Science Laboratory, Univ. Illinois, 1977.
.[23] Invariant colorings of random planar graphs. Preprint. Available at arXiv:0909.1091. | Zbl
.[24] Invariant matchings of exponential tail on coin flips in ℤd. Preprint. Available at arXiv:0909.1090.
.[25] 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 :