Stationary map coloring

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

Type: Article

Publication Date: 2012-04-11

Citations: 8

DOI: https://doi.org/10.1214/10-aihp399

Abstract

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.

Locations

Annales de l Institut Henri Poincaré Probabilités et Statistiques - View - PDF
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	None	1999	Ming Liao
+	None	2001	I. N. Kostin
+	None	1999	Yong-Gao Chen Imre Z. Ruzsa
+	None	2003	Paul Sablonnière
+	None	2001	Emmanuel Fragnière Jacek Gondzio Robert Sarkissian
+	None	1998	G. Sardanashvily
+	None	1998	Hans Keiding
+	None	2003	Haihua Feng Vincenzo Galdi David A. Castañón
+	None	2003	V. Z. Kanchukoev B. S. Karamurzov В. А. Созаев Vladimir Chernov
+	None	2001	Petr Habala Nicole Tomczak-Jaegermann
+	None	2001	S. E. Kozlov
+ PDF Chat	None	2008	田村直義
+	None	2001	Joaquin Soriano
+	None	2001	Shigetaka Fukuda
+	None	2003	Solomon Friedberg
+	None	2003	Igor Belegradek
+	None	1997	Salih Çelïk
+	None	2001	M. de Montigny Hubert de Guise
+	None	2001	A. Yu. Kolesov Н. Х. Розов
+	None	2002	D. G. Djumbayeva Erlan Nursultanov

Works That Cite This (8)

Action	Title	Year	Authors
+	Ising model on trees and factors of IID	2020	Danny Nam Allan Sly Lingfu Zhang
+ PDF Chat	Perfect matchings as IID factors on non-amenable groups	2011	Russell Lyons Fëdor Nazarov
+ PDF Chat	Finitary codings for spatial mixing Markov random fields	2020	Yinon Spinka
+ PDF Chat	Factors of IID on Trees	2016	Russell Lyons
+ PDF Chat	Ising Model on Trees and Factors of IID	2022	Danny Nam Allan Sly Lingfu Zhang
+	Finitary codings for spatial mixing Markov random fields	2018	Yinon Spinka
+	Factors of IID on Trees	2014	Russell Lyons
+	Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics	2021	Sebastian Brandt Yi‐Jun Chang Jan Grebík Christoph Grunau Václav Rozhoň Zoltán Vidnyánszky

Works Cited by This (17)

Action	Title	Year	Authors
+ PDF Chat	The critical probability for random Voronoi percolation in the plane is 1/2	2005	Béla Bollobás Oliver Riordan
+	Set Theory An Introduction to Independence Proofs	1980	Kenneth Kunen
+ PDF Chat	Domination by product measures	1997	Thomas M. Liggett Roberto H. Schonmann Alan Stacey
+ PDF Chat	Poisson Thinning by Monotone Factors	2005	Karen Ball
+ PDF Chat	Generating stationary random graphs on ℤ with prescribed independent, identically distributed degrees	2006	Maria Deijfen Ronald Meester
+ PDF Chat	Descending chains, the lilypond model, and mutual-nearest-neighbour matching	2005	D. J. Daley Günter Last
+ PDF Chat	Phase Transitions in Gravitational Allocation	2010	Sourav Chatterjee Ron Peled Yuval Peres Dan Romik
+ PDF Chat	Trees and Matchings from Point Processes	2003	Alexander E. Holroyd Yuval Peres
+ PDF Chat	Tail Bounds for the Stable Marriage of Poisson and Lebesgue	2009	Christopher Hoffman Alexander E. Holroyd Yuval Peres
+ PDF Chat	Gravitational allocation to Poisson points	2010	Sourav Chatterjee Ron Peled Yuval Peres Dan Romik