A short nonalgorithmic proof of the containers theorem for hypergraphs
A short nonalgorithmic proof of the containers theorem for hypergraphs
复制标题
超图容器定理的简短非算法证明
DOI：
10.1090/proc/14368
复制
发表时间：
2019
影响因子：
1
通讯作者：
Bernshteyn A
中科院分区：
文献类型：
--
作者：
Bernshteyn A
最近，Balogh、Morris和Samotij独立开发的超图容器的突破性方法[J. Amer. Math. Soc. 28（2015），pp. 669-709]以及Saxton和Pastason [发明。201（2015），pp. 925-992]，已被用来研究稀疏随机模拟的各种经典问题，从组合和数论。以前已知的容器定理的证明使用了所谓的镰刀算法一种遍历超图顶点的迭代过程。（Saxton和Brachason）。可能吧Comput. 25（2016），pp. 448-459]也提出了一个替代的，随机结构的情况下，简单超图。在这里，我们提出了第一个已知的确定性证明的容器定理，不是算法，即，它不涉及迭代过程。我们的证明不到四页长，同时完全独立，概念上是透明的。虽然我们的证明是完全初等的，它的灵感来自于考虑超图在非标准分析的设置，其中有一个概念的尺寸捕捉有限集的对数增长率。在完整地展示证明之前，我们包括一个一页的非正式大纲，其中提到了维度的概念，并总结了论证的本质。引用
Recently the breakthrough method of hypergraph containers, developed independently by Balogh, Morris, and Samotij [J. Amer. Math. Soc. 28 (2015), pp. 669–709] as well as Saxton and Thomason [Invent. Math. 201 (2015), pp. 925–992], has been used to study sparse random analogs of a variety of classical problems from combinatorics and number theory. The previously known proofs of the containers theorem use the so-called scythe algorithm—an iterative procedure that runs through the vertices of the hypergraph.(Saxton and Thomason [Combin. Probab. Comput. 25 (2016), pp. 448–459] have also proposed an alternative, randomized construction in the case of simple hypergraphs.) Here we present the first known deterministic proof of the containers theorem that is not algorithmic, ie, it does not involve an iterative process. Our proof is less than four pages long while being entirely self-contained and conceptually transparent. Although our proof is completely elementary, it was inspired by considering hypergraphs in the setting of nonstandard analysis, where there is a notion of dimension capturing the logarithmic rate of growth of finite sets. Before presenting the proof in full detail, we include a one page informal outline that refers to this notion of dimension and summarizes the essence of the argument. References
登录
查看更多内容
模型理论及其在代数和分析中的应用：计数和维数
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
E. Hrushovski;F. Wagner
通讯作者：
F. Wagner
DOI：
--
发表时间：
1998
期刊：
影响因子：
--
作者：
R. Goldblatt
通讯作者：
R. Goldblatt
简单超图的简单容器
DOI：
--
发表时间：
2014
期刊：
Combinatorics, probability & computing
影响因子：
--
作者：
D. Saxton;A. Thomason
通讯作者：
A. Thomason
稀疏随机集中的组合定理
DOI：
--
发表时间：
2010
期刊：
影响因子：
--
作者：
D. Conlon;W. Gowers
通讯作者：
W. Gowers
相对于随机集的组合定理
DOI：
--
发表时间：
2014
期刊：
影响因子：
--
作者：
D. Conlon
通讯作者：
D. Conlon