Part 1 of 5. K₄ Ramsey–Turán II — Tools →
Part 1 of 5. K₄ Ramsey–Turán I — Survey →
报告之前
我按照论文的顺序从头到尾地把每个断言、引理和定理都好好地看了一遍，并按照文章的思路先重新写了一遍证明（报告里面的引理、断言、定理的顺序的编号我都按照原本的论文来写）。跟着文章的思路走的时候，我发现了论文在证明的时候跳步的地方还挺多的，而且有些都是我想了好一阵子才想出怎么补全这个证明的。此外，看的过程中我也有一些想法，有一些疑问，感觉想写的东西还挺多的，所以我用不同颜色来区分这个报告中到底是作者写的还是我的想法:
刚开始写的时候我是按照论文的证明顺序来写的，然后一开始还没发要求我就把原文的证明复现了一半，并补全了一些感觉不显然但没给出来的证明。后面老师说的要求是不要全部都写原文的证明，我想着我都写了一大半不如全部给他写完。当然我也按照具体的要求提出了我的一些质疑。如果觉得证明部分过于繁琐的话可以直接看 非黑色字体部分，这些主要是我的一些质疑理解与对文章命题的一些加强。}
普通的黑字是论文中作者写到的部分。
Remark 1.
这是我在看论文的过程中忽然冒出来的想法。
Note.
这是我对论文中不全或者作者说留给读者去想的证明进行的补充证明。
这是我对论文内容的质疑和对论文中的证明细节、命题的思考与改进，给出了几个命题放在了第四小节。
Part 2 of 5. ← K₄ Ramsey–Turán — Preface · K₄ Ramsey–Turán II — Tools →
综述
本文的研究方向和结果综述
Ramsey--Tur'an 问题最早由 S'os 提出，在 Tur'an 问题中我们研究的是在禁止某个子图出现的情况下能得到的图的最大边数，而在 Ramsey--Tur'an 问题研究的是此基础上加上了独立数的限制条件下能得到的图的最大边数 [Sos1969,SimonovitsSos2001]。
对给定图
H 和正整数 m，我们定义 Ramsey--Tur'an 数为
RT(n,H,m):=\max\bigl{e(G): |V(G)|=n,\ \alpha(G)<m,\ H\nsubseteq G\bigr}.
e(G)\ge \left(\frac18+\eta\right)n^2,
则 G 要么含有一个 K4，要么包含一个大小大于 \alpha0 n 的独立集。
Bollob'as 和 Erd\H os 构造出了 K_4-free 图族，满足
e(G)=\frac{n^2}{8}-o(n^2), \alpha(G)=o(n),
从而说明 1/8 正是该问题的在主项上的正确极限密度 [BollobasErdos1976]。因此，后续研究的重点不再是主项本身，而是当独立数 \alpha(G) 仍为线性量级、且 \alpha 很小时，边数上界在 n^2/8 之外还能精确增加多少。
更进一步，Fox、Loh 和 Zhao 在 [FoxLohZhao2015] 中给出了如下更为精细的结果：
Theorem 2.
%[Fox--Loh--Zhao，Theorem 1.6] \cite[Theorem 1.6]{FoxLohZhao2015} 存在绝对常数 \gamma>0，使得若图 G 满足 \alpha(G)=\alpha n、\alpha\le \gamma，且
e(G)\ge \frac{n^2}{8}+\frac32\alpha n^2,
则 G 必含 K_4。
与此同时，他们还给出了非常强的下界构造。令
\beta=\sqrt{\frac{(\log\log n)^3}{\log n}},
\frac{n^2}{8}+\left(\frac{\alpha-\alpha^2}{2}-o(\alpha^2)\right)n^2.
因此，在 \alpha 相对 \beta 足够大时，他们实际上确定了 \eta 的大致范围：
\frac{\alpha-\alpha^2}{2}-o(\alpha^2)\leq \eta \leq \frac32\alpha,
e(G)>\frac{n^2+n}{8}+\frac{\gamma-\gamma^2}{2}n^2, \alpha(G)\le \gamma n,
则 G 必含 K_4。
但是，由于该证明仍然建立在 Szemer'edi正则引理 [Szemeredi1976] 之上，可用常数\gamma^\ast极小。
回到我们所看的这篇论文，这篇论文说到底就是在讲一个如下的核心主定理[Csaba2025]：
Theorem 5.
取 \nu=1/500，并设
\gamma=\exp!\left(-\frac{10\log(1/\nu)}{\nu}\right), N=\exp!\left(\frac{10\log(1/\nu)}{\nu}\right).
\alpha=\frac{\alpha(G)}{n}\le \gamma
e(G)>\frac{n^2+n}{8}+\frac{\alpha-\alpha^2}{2}n^2,
\frac{\alpha-\alpha^2}{2}n^2
不仅对固定常数 \alpha 正确，而且在更广的“小 \alpha”区间里仍然给出本质最优的阈值。第二，本文完全避免使用 Szemer'edi正则引理 [Szemeredi1976]，而是使用了另一种偏向直接构造计数的方法，这样使得上界推广到了更宽的参数区间，而不是像前面(thm1.2)里面要求的\gamma^\ast\ll 1。
Remark 5.
我感觉这篇文章的创新性就在于他跳脱出使用 Szemer'edi正则引理 [Szemeredi1976]的范畴，而是直接用构造计数来给出更好的区间，而且纵观整篇文章的证明，感觉比较难想的就是证明最开始的那一部分构造，其他也都是目的性极强的代数运算，算就完了。
一开始看到 (thm1.3) 的取 \nu=1/500，我就在想为什么是取 \nu=1/500，有没有什么特殊含义？从后续的证明来看，这里的 \nu=1/500主要是起到控制误差项的作用，比如说控制 7\nu n,15\nu n,15\nu n,41\nu n然后最重要的是保证 \alpha\ll\nu^2 n,\nu^3 n。
我也对 \nu 的取值范围进行了进一步的探讨，最终发现如果按照论文中的不等式放缩关系，我们只需取 \nu<1/321 即可，具体的计算过程见 (prop4.1)。
近期相关结果
Remark 6.
我也查找了近期关于 的相关论文，没有看到在结论上继续推进 (thm1.3) 的后续论文。不过，对于更一般的 Ramsey--Tur'an 理论，近两年还是有几篇和这篇论文联系紧密，值得提一下。
Balogh、Chen、McCourt 和 Murley 在 2024 年的工作 [BaloghChenMcCourtMurley2024] 讨论了 在小独立数条件下的行为，他们主要研究的是 的 clique 情形。该文表明：当我们把独立数进一步压小，Ramsey--Tur'an 问题的极值结构会发生新的分段变化。
Gao、Jiang、Liu 和 Sankar 在 2025 年的论文 [GaoJiangLiuSankar2025] 研究了广义 Ramsey--Tur'an 函数。这里研究的对象已经不是边数，而是图中 出现的总次数。论文对所有 的 clique 情形给出了组合性的渐近刻画，虽然这个问题和本文并不完全在同一层面上，但它在方法上与本文有相通之处，都更强调直接把极值结构刻画出来，而不只是借助 Szemer'edi正则引理 [Szemeredi1976] 得到一个较粗的存在性结论。
Liu、Reiher、Sharifzadeh 和 Staden 在 2026 年的文章 [LiuReiherSharifzadehStaden2026] 则把重点放在更一般的 Ramsey--Tur'an 构造问题上。他们构造出了具有任意有理密度的 Bollob'as--Erd\H os 型图，并否定了这一方向中一个关于周期性的长期猜想，同时还给出了一些匹配的上界。我觉得，他们给出了一个很好的观点：针对于本文研究的问题，这个方向的发展并不只是不断打磨上界，也在产生新的构造方法和找到新的反例。从这个角度看，本文的工作更像是对经典 分支中结构上界方法的一次推进，而 [LiuReiherSharifzadehStaden2026] 则展示了构造方法在更一般框架下的展开。
Download the original write-up here.