Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms
Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms
复制标题
连续组合中的概率构造和分布式算法的桥梁
DOI：
10.1016/j.aim.2023.108895
复制
发表时间：
2023
影响因子：
1.7
通讯作者：
Bernshteyn, Anton
中科院分区：
文献类型：
--
作者：
Bernshteyn, Anton
概率方法是一种证明组合存在结果的技术，通过显示随机选择的对象具有正概率的期望属性。一个特别强大的概率工具是Lovász局部引理（简称LLL），它是由埃尔德什和Lovász在20世纪70年代中期提出的。在这里，我们开发了一个版本的LLL，可以用来证明连续着色的存在。然后，我们给出了在Borel和拓扑动力学中的几个应用。·Seward和Tucker-Drob证明了可数群Γ的每一个自由Borel作用Γ <$X都允许一个等变Borel映射π：X→ Y到一个自由子移位Y <$2 Γ。我们给出了这个结果的一个新的简单证明。·我们证明了对于可数群Γ，Free（2 Γ）在Elek意义下弱包含于零维Polish空间上Γ的每个自由连续作用中.这一事实类似于Abért和韦斯关于概率测度保持作用的定理，并且在连续组合学中有许多结果。特别地，我们推导出一个着色问题在Free（2 Γ）上有连续解当且仅当它可以在Γ的Cayley图的有限子图上用一个有效的确定性分布式算法求解（这一事实也由Seward用不同的方法独立地证明了）。这在连续组合学和分布式计算中独立研究的问题之间建立了正式的对应关系。
The probabilistic method is a technique for proving combinatorial existence results by means of showing that a randomly chosen object has the desired properties with positive probability. A particularly powerful probabilistic tool is the Lovász Local Lemma (the LLL for short), which was introduced by Erdős and Lovász in the mid-1970s. Here we develop a version of the LLL that can be used to prove the existence of continuous colorings. We then give several applications in Borel and topological dynamics.• Seward and Tucker-Drob showed that every free Borel action Γ↷ X of a countable group Γ admits an equivariant Borel map π: X→ Y to a free subshift Y⊂ 2 Γ. We give a new simple proof of this result.• We show that for a countable group Γ, Free (2 Γ) is weakly contained, in the sense of Elek, in every free continuous action of Γ on a zero-dimensional Polish space. This fact is analogous to the theorem of Abért and Weiss for probability measure-preserving actions and has a number of consequences in continuous combinatorics. In particular, we deduce that a coloring problem admits a continuous solution on Free (2 Γ) if and only if it can be solved on finite subgraphs of the Cayley graph of Γ by an efficient deterministic distributed algorithm (this fact was also proved independently and using different methods by Seward). This establishes a formal correspondence between questions that have been studied independently in continuous combinatorics and in distributed computing.
登录
查看更多内容
分布式算法、Lovasz 局部引理和描述性组合
影响因子：
3.1
作者：
Anton Bernshteyn
通讯作者：
Anton Bernshteyn
局部模型中随机复杂性和确定性复杂性之间的指数分离
影响因子：
1.6
作者：
Chang, Yi-Jun;Kopelowitz, Tsvi;Pettie, Seth
通讯作者：
Pettie, Seth
影响因子：
0.8
作者：
Su Gao;S. Jackson;Brandon Seward
通讯作者：
Brandon Seward
可数群 2 班的 Borel 结构化性
影响因子：
0.8
作者：
Brandon Seward;Robin D. Tucker
通讯作者：
Robin D. Tucker
Lovász 局部引理的分布式复杂性的尖锐阈值现象
DOI：
--
发表时间：
2019
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
S. Brandt;Yannic Maus;Jara Uitto
通讯作者：
Jara Uitto