Stationary map coloring

DOI10.1214/10-AIHP399MaRDI QIDQ424689zbMATHFDO

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

Publication date 4 June 2012

Published in Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0905.2563

zbMATH Keywords

Poisson processgraph coloringDelaunay triangulationpercolationplanar graphsVoronoi tessellation

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15)

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.

Recommendations

• Invariant colorings of random planar maps
• Random partitions of the plane via Poissonian coloring and a self-similar process of coalescing planar partitions
• scientific article; zbMATH DE number 866027
• scientific article; zbMATH DE number 2209737
• Colouring proximity graphs in the plane

Cites work

• scientific article; zbMATH DE number 3572825 (Why is no real title available?)
• A stable marriage of Poisson and Lebesgue
• Connected allocation to Poisson points in \(\mathbb R^{2}\)
• Descending chains, the lilypond model, and mutual-nearest-neighbour matching
• Deterministic thinning of finite Poisson processes
• Domination by product measures
• Extra heads and invariant allocations
• Generating stationary random graphs on ℤ with prescribed independent, identically distributed degrees
• Gravitational allocation to Poisson points
• Phase transitions in gravitational allocation
• Poisson matching
• Poisson splitting by factors
• Poisson thinning by monotone factors
• Set theory. An introduction to independence proofs
• Tail Bounds for the Stable Marriage of Poisson and Lebesgue
• The critical probability for random Voronoi percolation in the plane is 1/2
• Trees and matchings from point processes

Cited in

(7)

• Fractal properties of the frontier in Poissonian coloring
• Perfect matchings as IID factors on non-amenable groups
• Random partitions of the plane via Poissonian coloring and a self-similar process of coalescing planar partitions
• Finitary codings for spatial mixing Markov random fields
• Invariant colorings of random planar maps
• Factors of IID on trees
• Ising model on trees and factors of IID

This page was built for publication: Stationary map coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q424689)