Stationary map coloring

Omer Angel; Itai Benjamini; Ori Gurel-Gurevich; Tom Meyerovitch; Ron Peled

Annales de l'I.H.P. Probabilités et statistiques (2012)

  • Volume: 48, Issue: 2, page 327-342
  • ISSN: 0246-0203

Abstract

top
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.

How to cite

top

Angel, Omer, et al. "Stationary map coloring." Annales de l'I.H.P. Probabilités et statistiques 48.2 (2012): 327-342. <http://eudml.org/doc/272076>.

@article{Angel2012,
abstract = {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.},
author = {Angel, Omer, Benjamini, Itai, Gurel-Gurevich, Ori, Meyerovitch, Tom, Peled, Ron},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {Poisson process; graph coloring; planar graphs; Voronoi tessellation; Delaunay triangulation; percolation},
language = {eng},
number = {2},
pages = {327-342},
publisher = {Gauthier-Villars},
title = {Stationary map coloring},
url = {http://eudml.org/doc/272076},
volume = {48},
year = {2012},
}

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
PB - Gauthier-Villars
VL - 48
IS - 2
SP - 327
EP - 342
AB - 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.
LA - eng
KW - Poisson process; graph coloring; planar graphs; Voronoi tessellation; Delaunay triangulation; percolation
UR - http://eudml.org/doc/272076
ER -

References

top
  1. [1] O. Angel, G. Amir and A. Holroyd. Multi-color matching. Unpublished manuscript. 
  2. [2] O. Angel, A. Holroyd and T. Soo. Deterministic thinning of finite Poisson processes. Proc. Amer. Math. Soc.139 (2011) 707–720. Zbl1208.60047MR2736350
  3. [3] K. Ball. Poisson thinning by monotone factors. Electron. Comm. Probab. 10 (2005) 60–69 (electronic). Zbl1110.60050MR2133893
  4. [4] I. Benjamini, A. Holroyd, O. Schramm and D. Wilson. Finitary coloring. Unpublished manuscript. 
  5. [5] B. Bollobás and O. Riordan. The critical probability for random Voronoi percolation in the plane is 1/2. Probab. Theory Related Fields136 (2006) 417–468. Zbl1100.60054MR2257131
  6. [6] S. Chatterjee, R. Peled, Y. Peres and D. Romik. Phase transitions in gravitational allocation. Preprint. Available at http://arxiv.org/abs/0903.4647. Zbl1209.60008
  7. [7] S. Chatterjee, R. Peled, Y. Peres and D. Romik. Gravitational allocation to Poisson points. Ann. of Math. (2) 172 (2010) 617–671. Zbl1206.60013MR2680428
  8. [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. Zbl1078.60038
  9. [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. Zbl1102.05054MR2264945
  10. [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. Zbl0367.52004
  11. [11] C. Hoffman, A. E. Holroyd and Y. Peres. A stable marriage of Poisson and Lebesgue. Ann. Probab.34 (2006) 1241–1272. Zbl1111.60008
  12. [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. Zbl1191.60015
  13. [13] A. Holroyd, R. Lyons and T. Soo. Poisson splitting by factors. Ann. Probab. To appear. Available at http://arxiv.org/abs/0908.3409. Zbl1277.60087
  14. [14] A. Holroyd, R. Pemantle, Y. Peres and O. Schramm. Poisson matching. Ann. Inst. H. Poincaré Probab. Statist.45 (2009) 266–287. Zbl1175.60012MR2500239
  15. [15] A. E. Holroyd and Y. Peres. Trees and matchings from point processes. Electron. Comm. Probab. 8 (2003) 17–27 (electronic). Zbl1060.60048MR1961286
  16. [16] A. E. Holroyd and Y. Peres. Extra heads and invariant allocations. Ann. Probab.33 (2005) 31–52. Zbl1097.60032MR2118858
  17. [17] G. Kozma. Private communication, 2007. 
  18. [18] M. Krikun. Connected allocation to Poisson points in ℝ2. Electron. Comm. Probab. 12 (2007) 140–145 (electronic). Zbl1128.60012MR2318161
  19. [19] K. Kunen. Set Theory: An Introduction to Independence Proofs. Studies in Logic and the Foundations of Mathematics 102. North-Holland, Amsterdam, 1980. Zbl0443.03021MR597342
  20. [20] T. M. Liggett, R. H. Schonmann and A. M. Stacey. Domination by product measures. Ann. Probab.25 (1997) 71–95. Zbl0882.60046MR1428500
  21. [21] R. Lyons. Private communication, 2007. 
  22. [22] F. P. Preparata. Steps into computational geometry. Technical report, Coordinated Science Laboratory, Univ. Illinois, 1977. 
  23. [23] A. Timár. Invariant colorings of random planar graphs. Preprint. Available at arXiv:0909.1091. Zbl1223.05086
  24. [24] A. Timár. Invariant matchings of exponential tail on coin flips in ℤd. Preprint. Available at arXiv:0909.1090. 
  25. [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/. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.