讲义: 图论和加性组合

作者: 赵宇飞

译者: 刘程华, 武弘勋

原书地址: gtac

1绪论

目录

	1 Schur 定理
	2 加性组合的亮点
	3 然后呢?

2禁止子图

目录

	1 Mantel 定理: 禁止三角形
	2 Turán 定理: 禁止团 1
	3 超图上的 Turán 问题 2
	4 Erdős–Stone–Simonovits 定理: 禁止一般子图
	5 Kovári–Sós–Turán 定理: 禁止完全二分图
	6 下界: 随机构造
	7 下界: 代数构造
	8 下界: 随机代数构造
	9 禁止稀疏二分图

3Szemerédi 正则性引理

目录

	1 定理陈述和证明
	2 三角形记数和删除引理
	3 Roth 定理
	4 构造没有长度为 3 的等差数列的集合
	5 图嵌入、计数和删除引理
	6 导出子图的删除引理
	7 性能测试
	8 超图的删除引理
	9 超图的正则性
	10 Szemerédi 正则性引理的谱证明 4伪随机图 术语 “伪随机” 广泛指代了一系列的思想和现象. 它指的是一个并不随机的对象 (在某种意义下) 表现得像真正随机的情况一样. 比如说质数并不是随机分布的, 但是它的分布有许多和正整数的随机子集相似的性质. 著名的黎曼猜想就是一个典型案例, 它 (在某种意义上) 就是在断言质数具有伪随机性. 更准确地说, 我们具体的定义出一个 (真随机的对象满足的) 性质, 然后我们就可以问这样的问题: 一个给定的对象是否也具有相似的性质? 在这一章中, 我们就来研究图论中这样的问题, 并且我们将研究一个并不随机的图可以有哪些与随机图相似的性质.

目录

	1 拟随机图
	2 Expandermixing 引理
	3 拟随机 Cayley 图
	4 Alon–Boppana 界
	5 Ramanujan 图
	6 稀疏图正则性和 Green–Tao 定理

5图极限

目录

	1 主要结论的介绍和说明
	2 W-随机图
	3 正则性和计数引理
	4 Graphon 空间的紧致性
	5 紧致性的应用
	6 子图密度间的不等式

6Roth 定理

在 3.3 章中, 我们使用三角形删除引理和 Szemerédi 正则性引理证明了 Roth 定理. 在本章节, 我们将使用 Fourier 分析的方法研究 Roth 定理的原始证明. 首先, 让我们回顾一下 Roth 定理的陈述: 记 $r_3([N])$ 表示 $[N]$ 的 3-AP-free 子集大小的最大值, Roth 定理指出 $r_3([N])=o(N)$.

事实上, 使用 Szemerédi 正则性引理的缺点之一是证明所给出的上界类似于 $\frac{N}{{\log }^{\ast }N}$. 而 Roth 的 Fourier 分析版本的证明会给我们一个类似 $\frac{N}{\log \log N}$ 的上界, 这是一个更好的上界.

笔记 6.1. 目前已知的最佳上界是 Sanders 于 2011 年给出的 $r_3([N])\le N({\log }^{1-o(1)}N)$, 而已知的最佳下界是由 Behrend 于 2016 年给出的 $r_3(N)\ge N{e}^{-O(\sqrt{\log N})}$ . 一些证据似乎表明下界更接近真实值, 但缩小上下界之间的距离仍是一个悬而未决的问题.

目录

	1 有限域 Roth 定理
	2 Roth 对整数 Roth 定理的证明
	3 有限域 Roth 定理的多项式方法的证明
	4 Roth 定理与流行公差

7集合的加性结构

目录

	1 小倍增集合的结构
	2 Plünnecke–Ruzsa 不等式
	3 有限域上的 Freiman 定理
	4 Freiman 同态
	5 建模引理
	6 Bogolyubov 引理
	7 几何数论
	8 Freiman 定理的证明
	9 一般 Abel 群的 Freiman 定理
	10 非 Abel 群中的 Freiman 问题
	11 多项式 Freiman-Ruzsa 猜想
	12 加性能量和 Balog–Szémeredi–Gowers 定理

8Sum-Product 问题

本章节, 我们将考虑集合在加法和乘积下的特征. 具体的, 我们主要研究的是被称为 sum-product 的问题 (下文中简称为和积问题) : 是否存在集合 $A$, 使得 $A+A$ 和 $A\cdot A=\{ab:a,b\in A\}$ 都很小.

我们以 $A=[N]$ 为例, 我们有加法集 $|A+A|=2N-1$, 但乘法集很大, $|A\cdot A|=N^{2-o(1)}$. 探索乘法集大小的问题被称为 Erdős 乘法表问题. 我们还可以看出, 如果 $A$ 是等比数列, 则 $A\cdot A$ 很小, 而 $A+A$ 很大. 关于和积问题的主要猜想是说, 加法集或乘法集的大小非常接近一个极大值.

命题 8.1 (Erdős-Szemerédi 猜想 1983). 对于任意 $\mathbb{R}$ 上的有限子集 $A$, 我们有$$\max \{|A+A|,|A\cdot A|\}\ge |A{|}^{2-o(1)}$$

在本章, 你会见到和积问题下界的证明的两个版本. 作为铺垫, 我们先介绍一些工具.

目录

	1 交叉数不等式
	2 重合几何
	3 从积性能量看 Sum-product 问题

1.	^ 无向图中满足两两之间有边连接的顶点的集合, 称为该无向图中的团 (clique) .
2.	^ 超图 (Hypergraph) 是图的推广, 超图一个边可以连接任意数量的顶点. 相比之下, 在普通的图中, 一条边正好连接两个顶点.