论文标题
分布式算法，Lovász本地引理和描述性组合学
Distributed Algorithms, the Lovász Local Lemma, and Descriptive Combinatorics
论文作者
论文摘要
在本文中，我们考虑了标准鲍勒空间上图和其他组合结构上的着色问题。我们的目标是获得足够的条件，在这些条件下，可以从拓扑或衡量标准的意义上使这种颜色的行为良好。为此，我们表明，可以使用有限组合和计算机科学的某些强大技术来生产这种行为良好的着色。首先，我们证明有效的分布式着色算法（在有限的图上）产生了界限的鲍尔图的色彩；粗略地说，确定性算法会产生Borel颜色，而随机算法则具有可测量且可衡量的色彩。其次，我们建立了对称lovász本地引理的可衡量和baire-Measur-Measure-Meastions（在假设$ \ MathSf {p}（\ Mathsf {d} +1）^8 \ leq 2^{ - 15} $中，它比标准LLL LLL假设$ \ Mathsf {p Leq（p Leq）更强大。 e^{ - 1} $，但对于许多应用程序仍然足够）。从这些一般结果中，我们在描述性组合学和千古理论中得出了许多后果。
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 $\mathsf{p}(\mathsf{d}+1)^8 \leq 2^{-15}$, which is stronger than the standard LLL assumption $\mathsf{p}(\mathsf{d} + 1) \leq e^{-1}$ but still sufficient for many applications). From these general results, we derive a number of consequences in descriptive combinatorics and ergodic theory.
