Stability results for random discrete structures
Stability results for random discrete structures
复制标题
随机离散结构的稳定性结果
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Wojciech Samotij
中科院分区：
文献类型：
--
作者：
Wojciech Samotij
两年前，康伦、高尔斯和沙赫特证明了一般定理，这些定理允许人们将一大类极值组合结果从确定性转移到概率性。尽管这两篇论文解决了概率组合学中同一组长期存在的开放问题，但其中使用的方法差异很大，因此在某些方面产生的结果不具有可比性。特别是沙赫特定理产生了更强的概率估计，而康伦和高尔斯的定理也暗示了一些结构陈述的随机版本，如著名的埃尔德什和西蒙诺维奇稳定性定理。在本文中，我们弥合了这两个迁移定理之间的差距。建立在沙赫特的方法，我们证明了一个一般定理，允许一个确定性的稳定性结果转移到概率设置。然后，我们使用这个定理导出几个新的结果，其中包括任意图的Erdens-Simonovits稳定性定理的随机版本，扩展了Conlon和Gowers的结果，他们证明了所谓的严格2平衡图的这种陈述。主要的新想法，一个完善的方法，以多重曝光时，考虑的子集二项式随机集，可能是独立的利益。版权© 2012威利期刊，公司。随机结构算法，44，269 - 289，2014
Two years ago, Conlon and Gowers, and Schacht proved general theorems that allow one to transfer a large class of extremal combinatorial results from the deterministic to the probabilistic setting. Even though the two papers solve the same set of long‐standing open problems in probabilistic combinatorics, the methods used in them vary significantly and therefore yield results that are not comparable in certain aspects. In particular, the theorem of Schacht yields stronger probability estimates, whereas the one of Conlon and Gowers also implies random versions of some structural statements such as the famous stability theorem of Erdős and Simonovits. In this paper, we bridge the gap between these two transference theorems. Building on the approach of Schacht, we prove a general theorem that allows one to transfer deterministic stability results to the probabilistic setting. We then use this theorem to derive several new results, among them a random version of the Erdős‐Simonovits stability theorem for arbitrary graphs, extending the result of Conlon and Gowers, who proved such a statement for so‐called strictly 2‐balanced graphs. The main new idea, a refined approach to multiple exposure when considering subsets of binomial random sets, may be of independent interest.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 269‐289, 2014