Independent sets in hypergraphs
Independent sets in hypergraphs
复制标题
DOI：
10.1090/s0894-0347-2014-00816-x
复制
发表时间：
2012-04
影响因子：
3.9
通讯作者：
J. Balogh;R. Morris;Wojciech Samotij
中科院分区：
文献类型：
--
作者：
J. Balogh;R. Morris;Wojciech Samotij
组合数学中的许多重要定理和猜想，如关于算术级数的Szmeredi定理和极值图论中的Erd˝OS-Stone定理，都可以表述为关于某些一致超图中的独立集族的陈述。近年来，该领域的一个重要趋势是将这些经典结果推广到所谓的“稀疏随机环境”。这一系列的研究最近在Conlon和Gowers以及Schacht的突破中达到顶峰，他们开发了解决这类问题的通用工具。尽管这两篇论文解决了一组非常相似的长期悬而未决的问题，但所使用的方法彼此非常不同，有不同的优点和缺点。在这篇文章中，我们提供了第三种完全不同的方法来证明稀疏随机集上的极值和结构结果，并给出了它们的自然‘计数’部分。我们给出了一大类一致超图中独立集的结构特征，证明了每个独立集几乎都包含在少数相对稀疏集中。然后，我们得到许多有趣的结果，作为这一抽象定理的相当直接的结果。特别地，我们证明了Kohayakawa，Luczak和Rodl的猜想，这是稀疏图的一个概率嵌入引理，对于所有的2-平衡图。我们还给出了Conlon、Gowers和Schacht的许多结果的另一种证明，例如Szmeredi定理的稀疏随机版本、Erd˝os-Stone定理和Erd˝os-Simonovits稳定性定理，并得到了它们的自然‘计数’形式，在某些情况下，它们的自然‘计数’形式相当强。我们还得到了一些新的结果，例如关于无H图的个数的Erd-˝定理的一个稀疏版本，并且作为K-LR猜想的结果，我们将Rodl和Rucinski关于稀疏随机图中Ramsey性质的一个结果推广到一般的非对称环境。萨克斯顿和托马森也独立发现了类似的结果。
Many important theorems and conjectures in combinatorics, such as the the- orem of Szemeredi on arithmetic progressions and the Erd˝os-Stone Theorem in extremal graph theory, can be phrased as statements about families of independent sets in certain uniform hypergraphs. In recent years, an important trend in the area has been to extend such classical results to the so-called 'sparse random setting'. This line of research has recently culminated in the breakthroughs of Conlon and Gowers and of Schacht, who de- veloped general tools for solving problems of this type. Although these two papers solved very similar sets of longstanding open problems, the methods used are very different from one another and have different strengths and weaknesses. In this paper, we provide a third, completely different approach to proving extremal and structural results in sparse random sets that also yields their natural 'counting' coun- terparts. We give a structural characterization of the independent sets in a large class of uniform hypergraphs by showing that every independent set is almost contained in one of a small number of relatively sparse sets. We then derive many interesting results as fairly straightforward consequences of this abstract theorem. In particular, we prove the well- known conjecture of Kohayakawa, Luczak, and Rodl, a probabilistic embedding lemma for sparse graphs, for all 2-balanced graphs. We also give alternative proofs of many of the results of Conlon and Gowers and Schacht, such as sparse random versions of Szemeredi's theorem, the Erd˝os-Stone Theorem and the Erd˝os-Simonovits Stability Theorem, and ob- tain their natural 'counting' versions, which in some cases are considerably stronger. We also obtain new results, such as a sparse version of the Erd˝os-Frankl-Rodl Theorem on the number of H-free graphs and, as a consequence of the K LR conjecture, we extend a re- sult of Rodl and Rucinski on Ramsey properties in sparse random graphs to the general, non-symmetric setting. Similar results have been discovered independently by Saxton and Thomason.