Stationary map coloring

DOI10.1214/10-AIHP399zbMATH Open1258.60015arXiv0905.2563MaRDI QIDQ424689FDOQ424689

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

Publication date: 4 June 2012

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

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.

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)

Cites Work

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

Cited In (4)

• Perfect matchings as IID factors on non-amenable groups
• Finitary codings for spatial mixing Markov random fields
• 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)