June 9, 2025

Combinatorics

au printemps 2025

Outline

Lecture 01 (2025/02/17): Sets and their operations.
Lecture 02 (2025/02/24): Binomial numbers: basics.
Lecture 03 (2025/03/10): Binomial numbers identities. Definition of graphs.
Lecture 04 (2025/03/12): More binomial numbers identities and more definitions about graphs.
Lecture 05 (2025/03/17): Basic graph theory, unit distance problem, and Mantel theorem.
Lecture 06 (2025/03/24): Proofs of Turan theorem. Introduction to trees.
Lecture 07 (2025/03/31): More on Turan’s theorem and more on trees. Definition of graph colouring.
Lecture 08 (2025/04/07): Embedding of the trees, Erdos-Sos conjecture. More on graph colouring.
Lecture 09 (2025/04/14): Graph colouring. Long paths and cycles in graphs. (Beginning of ) introduction to Ramsey theory.
Lecture 10 (2025/04/21): Ramsey theory on graphs and integers.
Lecture 11 (2025/04/27): Ramsey theory and happy ending problem.
Lecture 12 (2025/04/28): Graph colouring, Ramsey, and the probabilistic method.
Lecture 13 (2025/05/19): The probabilistic method, alteration, crossing lemma, and its applications.
Lecture 14 (2025/05/21): Distinct distances, property B.
Lecture 15 (2025/05/26): Linear algebra methods.

May 26, 2025

Linear Algebra Methods

Lecture Notes for CS477 combinatorics on 2025/05/26

组合中的线性代数方法

Maybe this link is useful: Linear Algebra Methods in Combinatorics

d维中每一对点距离为奇数，最大个数

n维点有2种距离，最大个数

d 维最大 joint 数

d维n条线，最大joint个数（要求joint必须是d个线性无关的线交点）

intuition：考虑 d 维中 $dk^{d-1}$ 条线，交点是一个点阵 $k^d$，因此 $\Omega(n^{\frac{d}{d-1}})$

先考虑三维空间，如果 $|J|=m\lt {d+3\choose3}$ 存在一个 d 次非平凡多项式 $P$ 使得 $J$ 在零点集中. ($\mathbb{R}^d[x_1,x_2,x_3]$ 有 ${d+3\choose3}$ 自由度)

Finite Kakeya conjecture

(to be completed)

May 21, 2025

Distinct Distances and Property B

Lecture Notes for CS477 combinatorics on 2025/05/21

cont’d: distinct distances

目标：有一个点能看到 $\geq n^{0.8}$ 的距离，反设每个点看到的距离数量都小于 $n^{0.8}$，假设这个数 $\leq M=\epsilon n^{0.8}$, 欲导出矛盾.

每个点往外画 $M$ 个圆，其他所有点都在圆组上，圆上点相邻的连边形成 $H$，每个圆心导出 n-1 个边，包括自环和二边形；去掉坏的圆，边数-2nM，最后 $H$ 边数大于 $n^2-o(n^2)$

交点数最多 ${n\choose 2}\times 2M^2$

$n^2 M^2\geq \text{Cr}\geq\frac{m^3}{4000kn^2}\sim\frac{n^4}{4000k}$

要在 $M\leq n^{0.8}$ 导出矛盾, 需证 $k\leq n^{0.4}$, $k$ 其实是每两点中垂线上点的个数. 然而这并不一直都成立.

思路如果有大于 $Cn^{0.4}$ 个点在线上，那么去掉这些和坏线相交的边。需证明这些坏线导致去掉的边数量为 $o(n^2)$

一条坏线可能会导致重边数量超过 $Cn^{0.4}$，因此考虑坏线上点产生的弧线（这些弧线段其实是$H$ 的边），去掉它们。假设 $s$ 个点，每个点 $M$ 个圆，最多扔掉 $2sM$ 条边。同时 $s\leq M+1$，因为否则，最左边的点看到距离数量就大于 $M$，矛盾了.

组合方法

为了解决这个问题，有 Szemeredi-Trotter 定理，它限制了坏线的个数.

Thm. (Szemeredi-Trotter, another form) $2\leq k\leq \sqrt{n}$, $|G|=n$, 如果 $\geq k$ 个点共线，计入这条线，最终的线数量 $\leq O\big(\frac{n^2}{k^3}\big)$

April 28, 2025

Crossing Lemma

Lecture Notes for CS477 combinatorics on 2025/05/19

Crossing number

平面图 $m\geq 3n-6$

规定不能三边交叉于一点，$G$ 的 crossing number 定义为最小交叉数量，例如 $K_5$ 至少一个，$\text{Cr}(K_5)=1$.

Thm. $\text{Cr}(G)\geq m-3n$

证1. 交点变成点，点+1，边+2，得到平面图
证2. 一个交点去一条边，至少少一个交点，因此至多去掉 $\text{Cr}$ 条边

Somehow when $m\geq 4n, \;\text{Cr}\geq\frac{3}{64}{n\choose 4}\Big(\frac{m}{n\choose 2}\Big)^3$

Thm. (1980, Crossing Lemma) $\text{Cr}(G)\geq\frac{m^3}{64n^2}(m\geq 4n)$

$\text{Cr}(K_n)$: 每5个点有1个交点；每个交点被算 $n-4$ 次

归纳法 $W\subseteq V,H=G[W],X(H)=n,Y(H)=m,Z(H)=(H\text{在}G\text{的最优画法下的交点个数})$
有 $Z\geq \text{Cr}\geq Y-3X$. 将 $V$ 中的点以概率 $p$ 选入 $W$, 算期望 $p^4\text{Cr}(G)\geq p^2m-3pn$, 取 $p=\frac{4n}{m}\leq1$ 即可

crossing lemma 应用: 好边

Thm. (Szemeredi-Trotter) $n$ points $\in\mathbb{R}^2$, 定义一条直线为好边当且仅当线上有 $\geq k\;(2\leq k\leq \sqrt{n})$ 个点. 这样的好边最多 $O\big(\frac{n^2}{k^3}\big)$ 个.

April 28, 2025

Probabilistic Method

Lecture Notes for CS477 combinatorics on 2025/04/28

“定理三”

给定最优染色，对于每种颜色一定存在一个该颜色的顶点，它与所有其他颜色相邻.（反之这种颜色可以不使用）

回顾概率方法

我们称同色 $K_k$ 为坏集合. 考虑 $\# \text{\{bad k-sets\}}$ 的期望 $\mathbb{E}[X]={n\choose k}2^{1-{k\choose 2}}:=f(n)$. 若固定 $n$, 对每个 $G$ 都有一个 bad k-sets 个数, 它们平均下来有 $f(n)$ 这么多. 其中有一个 $G$ 同色，bad k-sets 有 ${n\choose k}$ 个.

Alteration 方法. 固定 $k=20$，用有一张表格记录 $f(n)$，用于证明 $r(20,20)$ 的下界. 对 $n$ 阶图，一定能找到一种黄蓝染色，bad k-sets 有小于 $f(n)$ 个. 去掉每个 set 中的一个顶点即可得到无同色 k-sets 的图，故 $r(k,k)>n-f(n)$.

无三角形图可拥有任意大染色数

Mycielski 的影子图，Tutte 抽屉原理，Zykm 编码原理, Erdős line graph

April 27, 2025

Happy Ending Problem

Lecture Notes for CS477 combinatorics on 2025/04/27

Ramsey equation

Def. 整数方程 $E$ 是 Ramsey 的，当且仅当 $\forall c\;\exists N\;\forall \phi:[N]\to[c]\;\exists$ 一个 $E$ 的同色解

Trivially, $x+2y=3z$ 等等是 Ramsey 的；$x=py$ 不是.

首先 $x_1+\dots+x_{k-1}=x_k$ 一定是 Ramsey 的，因为对任意 $c$ 考虑 $r(k,\dots,k)$, c个k，相当于这么大的图, c染色必有同色 $K_k$, 而同色 $K_k$ 自然包含了一组解（每条边的差值对应了某个 $x_i$）。

$x+ty=z$ 是 Ramsey 方程

从 $x+6y=z$ 开始, 我们想到了 van der Waerden 定理：

Thm. (van der Waerden) $\forall c,k\;\exists N\;\forall\phi:[N]\to[c]\;\exists$ a monochromatic AP of length $k$ in $[n]$. The least $N$ is $W(c,k)$.

April 21, 2025

Ramsey Theory and Probabilistic Method Intro

Lecture Notes for CS477 combinatorics on 2025/04/21

证明 $r(4,4)=18$

即证，存在 $K_{17}$ 的 b/y 染色不存在同色 $K_4$. 每个点连16条边，如果9b+7y，9个点二染色必有3b or 4y, 都会形成同色 K4. 因此每个点都是 8b+8y

正17边形排在圆上，距离1248->b, 3567->y. 先考虑同色三角形，8+8=1，1+1=2，2+2=4，4+4=8，3+3=6，5+5=7，6+6=5，7+7=3，因此等腰。

证明 $r(3,3,3)=17$

K16，每个点15条边，如果出现一个点连6条同色边，假设同r色，由 $r(3,3)=6$, 1.6点的边有r，有同色K3；2.6点的边无r，因此b/y染色，必有同b/y色K3.

法1

法2 考虑 $V=\{0,1\}^5$

多染色

$r(a_1,a_2,a_3,a_4,a_5)\leq 5^{(a_1-1)+(a_2-1)+(a_3-1)+(a_4-1)+(a_5-1)+1}:=n$

每个点来说，存在一种颜色b，这个点连接的b色边有大于n/5条，因此去掉所有剩下的边和点。这个游戏最多可以进行 $(a_1-1)+(a_2-1)+(a_3-1)+(a_4-1)+(a_5-1)+1$ 轮，剩下同样数量的点，其中每个点到其他点的边都是同色的. 因此存在a1个c1，或a2个c2，或…, 这些存在每个都会形成一个同色 $K_{c_k}$.

证明 $r(k,k)=\Omega(k^2)$

$(k-1)\times K_{k-1}$ 内部染y，国际边染b

(1971, 构造性证明) $r(k,k)=\Omega(k^3)$

(Erdős, 1947) $r(k,k)>2^{k/2},k\geq3$

$n\leq 2^{k/2}$ yb染色每k个点形成一个点集 $T$, 坏集合的概率为 $2^{1-{k\choose 2}}$, 则随机染色，坏集合个数的期望 ${n\choose k}2^{1-{k\choose 2}}$

列表：row—染色方案；col—k元子集，如果第i个k元子集在第j个染色下同色，打✔. 按col统计，每个k元子集有$2^{1+{n\choose 2}-{k\choose 2}}$个✔，共计${n\choose k}2^{1+{n\choose 2}-{k\choose 2}}$. 平均下来，每个染色方案平均有${n\choose k}2^{1-{k\choose 2}}$个✔.

April 14, 2025

Graph Coloring and Intro to Ramsey

Lecture Notes for CS477 combinatorics on 2025/04/14

Independent Set and Chromatic number

考虑 $K_n$ 的影子图，$\alpha(G)=n$

染色的脑子

对顺序不敏感：$K_n,K_{a_1,a_2,\dots,a_k}$，$C_{2k+1}$ （由于度数2，不可骗到3以上）

敏感：$C_{2n}(n>2)$,——先染一个，再染和它距离是3的点，被骗了

如果 $\chi=2$, $\chi_\pi$ 可以任意大（点数也随着它变大）

$T_k$ 为有根树，满足存在一种顺序使得根会被染色为 $k$. $T_{k+1}$ 是一个根节点连所有 $T_1\sim T_k$ 的根

$\chi=2$, 要求 $\chi_\pi=50$, 最少需要几个点？考虑二分图，每个点除了自己对应的点不连，其他都连接。每个点依次被骗，如果点数100，可以做到50. 去掉最后两个点，连接，可做到 $2\chi_\pi-2$. 可证明至少需要 $2\chi_\pi-2$. （How?）

$\exists \pi, \;\chi_\pi=\chi$, 将每个颜色按顺序排即可，可得到 $\chi_\pi\leq\chi$ 或者 $\forall v\;\phi_\pi(v)\leq\phi(v)$

字典序最小：按照颜色1,2,3顺序比较大小

“脑子"的经典应用：regalloc(SSA) 中, 染色数=最大活跃变量数

考虑干涉图，按照时间顺序对每个变量染色，$v_i$ 和前面哪些变量干涉取决于活跃区域是否相交，因此 $\{v_j:v_iv_j\in E, j\lt i\}$ 一定构成一个完全图，$d_\pi(v)\lt \omega(G)$, 归纳可得每个染色都 $\phi(v)\leq\omega(G)$, 即 $\chi(G)=\omega(G)$.

Erdös-Sós: 证明 $\overline{d}\geq k\Rightarrow \exists P_{k+1}$

Thm. (Dirac) 连通且 $\delta\geq k\Rightarrow \exists P_{2k+1}$ 或 Hamilton Cycle

April 7, 2025

Tree Embedding and Erdos-Sos

Lecture Notes for CS477 combinatorics on 2025/04/07

a combinatorial equality

$$\sum_{r=0}^{50}(-1)^r{101\choose 51+r}{50+r\choose 50}=1$$

寻找一种组合方法，其代数做法在 Lecture 06 中.

101选51+r打勾，最后一个画圈，前面50+r个分方块三角，有 ${101\choose 51+r}{50+r\choose 50}$ 种方法.

换顺序，先选50个三角+1个圈，按顺序；再在圈前面任意选r个方块，r奇数，那么是坏的，偶数是好的。按照圈的位置分，如果圈前面选完三角还有空，那么r奇偶抵消；否则好的比坏的多1.

$\sum_{r=0}^{50}(-1)^r{101\choose 51+r}{50+r\choose 50}=\sum_{k=51}^{101}\sum_{r=0}^{k-1-50}(-1)^r{k-1\choose 50}{k-1-50\choose r}$

flipping a coin

$p\in(0,1)$ 均匀分布，求100次中50次成功的概率

传统：微积分

成功=$X(\omega)\lt p$, 因此这个概率等价为 rand 101 个数字，第一个数字排在第51位（or 任意位）的概率：1/101

tree embedding

Thm. $\overline{d}(G)\geq 2k-2\Rightarrow$ 任意一个 $k+1$ 阶树是 $G$ 的子图.

Lemma. $\overline{d}(G)\geq 2k-2$ 那么存在 $\delta(H)\geq k$ 的诱导子图.

$m\geq n(k-1)$, 每次去掉度数 $\leq k-1$ 的点和它的邻边, $m-d(v)\geq m-(k-1)\geq(n-1)(k-1)$. 去掉的过程中，$m\geq n(k-1)$ 一直保持. 停止的时候，没有度数 $\leq k-1$ 的点，因此 $\delta(G)\geq k$.

March 31, 2025