Distributed algorithms, the Lovász Local Lemma, and descriptive combinatorics
Distributed algorithms, the Lovász Local Lemma, and descriptive combinatorics
复制标题
分布式算法、Lovasz 局部引理和描述性组合
DOI：
--
复制
发表时间：
2020
影响因子：
3.1
通讯作者：
Anton Bernshteyn
中科院分区：
文献类型：
--
作者：
Anton Bernshteyn
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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathsf{p}(\mathsf{d}+1)^{8} \leqslant 2^{-15}$\end{document}, which is stronger than the standard LLL assumption p(d+1)⩽e−1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathsf{p}(\mathsf{d}+ 1) \leqslant e^{-1}$\end{document} but still sufficient for many applications). From these general results, we derive a number of consequences in descriptive combinatorics and ergodic theory.
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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathsf{p}(\mathsf{d}+1)^{8} \leqslant 2^{-15}$\end{document}, which is stronger than the standard LLL assumption p(d+1)⩽e−1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathsf{p}(\mathsf{d}+ 1) \leqslant e^{-1}$\end{document} but still sufficient for many applications). From these general results, we derive a number of consequences in descriptive combinatorics and ergodic theory.
登录
查看更多内容
影响因子：
1.3
作者：
Kai-Min Chung;Seth Pettie;Hsin-Hao Su
通讯作者：
Kai-Min Chung;Seth Pettie;Hsin-Hao Su
局部模型中随机复杂性和确定性复杂性之间的指数分离
影响因子：
1.6
作者：
Chang, Yi-Jun;Kopelowitz, Tsvi;Pettie, Seth
通讯作者：
Pettie, Seth
定向 Borel 图
影响因子：
1
作者：
Thornton, Riley
通讯作者：
Thornton, Riley
具有有限平均度的图的不友好着色
影响因子：
1.8
作者：
Conley, Clinton T.;Tamuz, Omer
通讯作者：
Tamuz, Omer
超有限性和 Borel 组合学
影响因子：
2.6
作者：
Conley, Clinton;Jackson, Steve;Marks, Andrew;Seward, Brandon;Tucker-Drob, Robin
通讯作者：
Tucker-Drob, Robin