Distributed algorithms, the Lovasz Local Lemma, and descriptive combinatorics

• 成果类型: Article
• 署名作者: Bernshteyn, Anton
• 署名单位: University System of Georgia; Georgia Institute of Technology
• 刊物名称: INVENTIONES MATHEMATICAE
• ISSN/ISSBN: 0020-9910
• DOI: 10.1007/s00222-023-01188-3
• 发表日期: 2023
• 页码: 495-542
• 关键词: coloring graphs; number

摘要

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