Distributed algorithms, the Lovász Local Lemma, and descriptive combinatorics

In this paper we consider coloring problems on graphs and other combinatorial structures on standard Borel spaces. Our goal is to obtain sufficient conditions under which such colorings can be made well-behaved in the sense of topology or measure. To this end, we show that such well-behaved coloring...

Full description

Saved in:
Bibliographic Details
Published in:Inventiones mathematicae 2023-08, Vol.233 (2), p.495-542
Main Author: Bernshteyn, Anton
Format: Article
Language:English
Subjects:
Algorithms
Coloring
Combinatorial analysis
Combinatorics
Computer science
Graph coloring
Graphs
Mathematics
Mathematics and Statistics
Topology
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we consider coloring problems on graphs and other combinatorial structures on standard Borel spaces. Our goal is to obtain sufficient conditions under which such colorings can be made well-behaved in the sense of topology or measure. To this end, we show that such well-behaved colorings can be produced using certain powerful techniques from finite combinatorics and computer science. First, we prove that efficient distributed coloring algorithms (on finite graphs) yield well-behaved colorings of Borel graphs of bounded degree; roughly speaking, deterministic algorithms produce Borel colorings, while randomized algorithms give measurable and Baire-measurable colorings. Second, we establish measurable and Baire-measurable versions of the Symmetric Lovász Local Lemma (under the assumption p ( d + 1 ) 8 ⩽ 2 − 15 , which is stronger than the standard LLL assumption p ( d + 1 ) ⩽ e − 1 but still sufficient for many applications). From these general results, we derive a number of consequences in descriptive combinatorics and ergodic theory.
ISSN:0020-9910
1432-1297
DOI:10.1007/s00222-023-01188-3