个人思考
和现代图论课程内容的联系
本文与现代图论课程中的极值图论和正则性方法联系紧密。Tur'an 型问题研究禁止子图条件下的最大边数,而 Ramsey--Tur'an 问题在此基础上增加独立数限制。因此,其极值结构不再是单纯的 Tur'an 图,而呈现出近似二分、内部扰动受控的特征。
虽然本文不使用 Szemer'edi 正则引理 [Szemeredi1976],但仍保留了从复杂图中提取均匀结构的正则性思想。与全局正则划分不同,本文围绕证明所需结构直接进行局部、定向的提取。
我对这篇文章方法的一点总体判断
本文的方法围绕 情形进行针对性的结构分析,从而避免了正则引理带来的 tower-type 常数;相应地,证明对-free 图的局部结构依赖较强。特别是后面 两边的构造、短奇圈排除、以及最后调用 这一类内部图结论,都很难直接想象怎样推广到一般。
因此,这套方法目前更适合看作针对 的专门证明。若要推广到一般,需要新的多部结构提取工具和相应的内部边数控制结果。
我最感兴趣的后续问题
如果要从这篇文章继续往下想,我目前最感兴趣的是下面两个问题。
第一个问题是:能不能在不改变整体路线的前提下,把常数继续推进? 作者已经把依赖从 tower-type 降到了 single-exponential,但最后给出的 仍然很小。证明中的主要损失集中在 one-sided regular pair 的抽取和后续粗化,因此可以继续研究这些局部步骤能够将 和 改进到什么程度。
第二个问题是:能不能把最后的稳定性信息单独整理出来? 主定理证明的最后一步表明极值图必须接近一个平衡二分结构。可以进一步研究如下稳定性问题:当边数足够接近阈值时,图在编辑距离意义下是否接近某个 Bollob'as--Erd\H os 型构造?
最后一点个人感受
我自己写这份报告的时候,一个很直观的感受是:这篇文章并不是那种“定理一眼看过去很强,证明却主要是机械计算”的论文。它真正难的地方恰恰在于前面那几个结构步骤,而不是后面的大段代数整理。对我来说,最有收获的一点也在这里:很多时候一篇图论论文最重要的内容,不是某条不等式最后写成了什么样子,而是作者是怎样一步一步把原问题压成那个不等式的。把这个过程看懂,往往比把最后两页的计算抄完整更能学到东西。
Download the original write-up here.