大事记

本次讨论为第 20 期。讲者路宇轩围绕大语言模型与数学 Agent 的最新进展，介绍 AI 发展关键节点、编程工具工作流、自动形式化与 Lean 证明辅助，并讨论如何构建面向图论与组合数学的研究助手。

本次讨论为第 19 期。在上次介绍了利用概率方法处理 Hadwiger 猜想相关问题之后，本次深入使用 Lovász Local Lemma 和 Chernoff Bound 给出全色数的上界估计，向全染色猜想（Total Coloring Conjecture）推进。

本次讨论为第 18 期。主题聚焦图染色中的关键极值问题。第一部分讨论 Hadwiger 猜想相关问题，展示如何利用概率方法证明高平均度的图包含大团子式（clique minor）；第二部分研究全染色（total coloring），利用 Lovász Local Lemma 和 Chernoff Bound 估计全色数。

本周我们主要介绍随机图 G(n, c/n) 中的相变现象。以该随机图模型中的孤立点个数为例引入强阈函数的概念，并给出经典的一阶矩与二阶矩方法。主要内容是随机图巨大连通分支尺寸的相变现象，着重分析次临界态、超临界态与临界态下最大连通分支的大小与结构。

本次讨论是该系列的第 12 次讨论。本次主要通过讨论 Noga Alon 书上有关 r-uniform hypergraph 的覆盖问题，了解 Rödl’s Nibble 的原理与思路，通过参数计算了解其如何将问题划分为 O(1/ε) 步，以及如何通过概率方法得到 Nibble 结论。

本次讨论是该系列的第 11 次讨论。本次主要介绍如何利用 Szemerédi 正则引理证明 Erdős-Stone-Simonovits 定理。我们会首先介绍 Turán 数以及 Turán 问题的概念，并介绍著名的 Mantel 定理以及 Turán 定理。之后介绍 ESS 定理的内容以及多种证明。

本次讨论是该系列的第 10 次讨论。本次主要介绍 Szemerédi 定理的弱化版本——Roth 定理的证明，并继续加强对 Szemerédi 正则引理范式（Partition, Clean and Counting）的理解。

本次讨论是该系列的第 9 次讨论。本次继续介绍著名的 Szemerédi 正则引理，着重强调引理的运用。我们会介绍正则引理使用的经典范式，并且利用正则引理证明著名的 Erdős-Stone-Simonovits 定理。此外还会介绍 Szemerédi 定理的证明——这正是 Szemerédi 正则引理的源头。

本次讨论是该系列的第 8 次讨论。本次主要介绍著名的 Szemerédi 正则引理。我们会介绍 ε-regular pair、ε-regular partition 等概念，引理的证明以及简单的应用。

本周我们参考 Jacob Fox 和 Benny Sudakov 的文章《Dependent Random Choice》，介绍依赖随机选择这一概率方法，并给出其在二部图的 Turán 数、立方体的 Ramsey 数的上界估计以及完全图的 1-subdivision 嵌入等问题上的应用。

本次讨论是该系列的第 6 次讨论。今天介绍一篇 2025 年挂在 arXiv 上的论文 “Many Pentagons in linear triple system”。通过阅读该论文，旨在让各位参与者了解现代图论中出现的概念、定理与证明思路，并看到之前所讲的概率方法如何应用在具体的科研中。

本次讨论是该系列的第 5 次讨论。我们开始介绍二阶矩方法，本次讨论着重考虑一个著名的概率技巧：Rödl Nibble 方法。具体而言，我们会考虑覆盖数 M(n,k,l) 的上界估计，证明 M(n,k,l) ≤ (1+o(1))·(n choose l)/(k choose l)。

本次讨论是该系列的第 4 次讨论。首先介绍期望方法在独立集数、团数、Turán 定理以及超图上的 Turán 问题的应用；之后正式开始介绍 Alternation 方法，以支配集的例子作为引入，再介绍 sum-free 子集问题；最后进行第一章习题的讨论。

本次讨论是该系列的第 3 次讨论。我们首先仔细介绍概率方法在超图的 2-染色（Property B）以及 K_{n,n} 上的列表染色问题中的应用；随后开始介绍期望方法（一阶矩方法）在各种图论问题上的应用，包括 n 维欧氏空间上向量的线性组合问题、开关灯问题等；最后处理第一章的课后习题。

本次讨论是该系列的第 2 次讨论。我们首先处理上次讨论预留的两个小问题：EKR 定理的完整证明以及渐进上界的求法；之后继续介绍概率方法在超图的 2-染色以及 K_{n,n} 上的列表染色问题中的应用。随后开始介绍期望方法（一阶矩方法）在各种图论问题上的应用。