When does the K4‐free process stop?
When does the K4‐free process stop?
复制标题
无 K4 进程何时停止？
DOI：
10.1002/rsa.20444
复制
发表时间：
2010
影响因子：
1
通讯作者：
L. Warnke
中科院分区：
文献类型：
--
作者：
L. Warnke
无 K4 过程从 n 个顶点上的空图开始，并在每一步添加从未完成 K4 副本的所有剩余边中均匀随机选择的新边。令 G 为过程结束时获得的随机最大无 K4 图。我们证明，对于某个正常数 C，当 n→∞ 的概率较高时，G 中的最大次数最多为 Cn3/5logn5 。这解决了 Bohman 和 Keevash 对于无 K4 过程的猜想，并改进了 Bollobás 和 Riordan 以及 Osthus 和 Taraz 先前获得的界限。结合 Bohman 和 Keevash 的结果，这表明 G 具有 θ(n8/5logn5) 条边的概率很高，并且“接近规则”，即每个顶点的度数为 θ(n3/5logn5) 。这回答了 Erdős、Suen 和 Winkler 关于无 K4 过程的问题。我们进一步推导出一个额外的结构属性：我们证明 G 的独立数至少为 Ω(n2/5(logn)4/5/loglogn) ，这与 Bohman 获得的上限匹配，最高可达 θ(loglogn) 因子。我们对无 K4 过程的分析也产生了 Ramsey 理论的新结果：对于 Erdős 和 Rogers 引入的经过充分研究的函数的特殊情况，我们稍微改进了最著名的上限。版权所有 © 2012 Wiley periodicals, Inc. Random Struct。阿尔格., 44, 355‐397, 2014
The K4‐free process starts with the empty graph on n vertices and at each step adds a new edge chosen uniformly at random from all remaining edges that do not complete a copy of K4. Let G be the random maximal K4‐free graph obtained at the end of the process. We show that for some positive constant C, with high probability as n→∞ , the maximum degree in G is at most Cn3/5logn5 . This resolves a conjecture of Bohman and Keevash for the K4‐free process and improves on previous bounds obtained by Bollobás and Riordan and by Osthus and Taraz. Combined with results of Bohman and Keevash this shows that with high probability G has Θ(n8/5logn5) edges and is ‘nearly regular’, i.e., every vertex has degree Θ(n3/5logn5) . This answers a question of Erdős, Suen and Winkler for the K4‐free process. We furthermore deduce an additional structural property: we show that whp the independence number of G is at least Ω(n2/5(logn)4/5/loglogn) , which matches an upper bound obtained by Bohman up to a factor of Θ(loglogn) . Our analysis of the K4‐free process also yields a new result in Ramsey theory: for a special case of a well‐studied function introduced by Erdős and Rogers we slightly improve the best known upper bound.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 355‐397, 2014