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

为什么这么奇怪？考虑 k=100, $K_{100}+K_{100}$ 即可没有 $2k+1$ path 且无 H.C.

Hamilton Cycle

无需连通，因为如果 $d(u)+d(v)\geq n$, 那么一定有公共邻居.

Pf. of Dirac

$C_t(t\lt n)\to P_{t+1}$

$P_{t}(t\leq 2k)\to P_{t+1}\text{ or }C_t$

$C_t$ 要从已知的 $P_t$ 中选出，由于 $t\leq 2k$, 有集合 $A=\{i:v_1v_i\in E\},B=\{j:v_{j-1}v_t\in E\}\subseteq[2,t]$, 因此两个集合一定有重复的，这样就有 $C_t$.

Proof of Erdös-Sós Conjecture

$\overline{d}\geq k$ 等价于 $m\geq\frac{nk}{2}$, 去掉度数 $\leq k/2$ 扔掉（它和连接它的所有边）之后, 得到子图 $H$, $\delta(H)>\frac{k}{2}$. 去掉点的过程平均度数不减, 就是一直满足 $\overline{d}\geq k$.

若得到 $H$ 不连通，选一个连通分量即可，最小度数不会变小, 有 $\delta(H^\prime)>\frac{k}{2}$, 根据 Dirac, $H^\prime$ 中存在 $P_{k+1}$ 或一个 Hamilton Cycle. 如何解决 H.C. ?

这个连通分量满足 $\overline{d}\geq k$, 因此存在一个点 $d(v)\geq k$, 故连通分量中必有 $k+1$ 个点. 这样我们不怕Hamilton Cycle, 因为即使有, 它长度 $\geq k+1$, 自然包含 $P_{k+1}$.

染色：另一种视角

$\chi$ 染色，就是把 $G$ 分割成 $\chi$ 个独立集. 全部边都是国际边 (k部图).

$n=100,\chi=10$ $\min m=45,\max m=4500$

根据定理 040702，$\chi=10$, 那么存在10个点 $\deg\geq 9$，握手

Nordhaus-Gaddum 关于补图染色的定理

Thm. (Nordhaus-Gaddum) $G,H$ 互为补图，那么 $\chi_1\chi_2\geq n$, $\chi_1+\chi_2\leq n+1$.

推论：$n\leq\chi_1\chi_2\leq\frac{(n+1)^2}{4}$, $2\sqrt{n}\leq\chi_1+\chi_2\leq n+1$

$\chi_1\chi_2=n,\chi_1+\chi_2=n+1$: $G=K_n,H=K_1\times n$

$\chi_1\chi_2=\frac{(n+1)^2}{4}$: 令 $n=2k-1$, 例子是 $G=K_{k}\cup k-1$ 个孤立点.

$\chi_1+\chi_2=2\sqrt{n}$: 令 $n=k^2$, 例子是 $G=K_{k}\times k$.

Pf.

$$\chi(G)\geq\frac{n}{\alpha(G)}=\frac{n}{\omega(H)}\geq\frac{n}{\chi(H)}$$

另: 对于最优染色 $\phi_G,\phi_H$, $\sigma:V\mapsto[\chi(G)]\times[\chi(H)]:\sigma(v)=(\phi_G(v),\phi_H(v))$, 是一个单射（uv存在于GH的至少一个中）, 这还可以推广到，将 $G$ 的边进行 $k$染色，$n\leq\chi_1\dots\chi_k$.

归纳，首先 $n=2$, $\chi(G)+\chi(H)=3$; 假设对所有比 $K_n$ 小的图都成立，那么去掉 $K_n$ 的一个点, $G,H$ 变成 $G^\prime,H^\prime$.

三个式子取等不可能同时发生，因为多染一种颜色需要 $v$ 在 $G,H$ 中分别有至少 $\chi(G),\chi(H)$ 个邻居, 加起来是 $n$. 但是 $d(v)=n-1$

另：G度数从大到小排，无脑染色，G从左往右染，H从右往左染，记录第一个出现$\chi$的地方, G->i, H->j

如果 $i\leq j$, $\chi_\pi(G)\leq i, \chi_\pi(H)\leq j, i+j\leq n+1$;

如果 $i>j$, $\chi_\pi(G)\leq d_G(v_i)+1,\chi_\pi(H)\leq d_H(v_j)+1=n-d_G(v_j),d_G(v_j)\geq d_G(v_i)$.

都有 $\chi_\pi(G)+\chi_\pi(H)\leq n+1$. 综合 $\chi\leq\chi_\pi$ 即可.

Ramsey Number

要证 $r(y,b)\leq N$ 即证任意 $K_N$ 二染色必有...

要证 $r(y,b)> M$ 即证存在 $K_M$ 二染色无...

$n\to(b,y)$

证明 $6\to(3,3)$ （定理1）

经典随便取点，存在3同色

证明 $9\to(3,4)$ （定理1.5）

• 存在 $v$ 有 4b, 那4个点要么 b$K_2$, 要么 y$K_4$
• 存在 $v$ 有 6y, 那6个点要么 b$K_3$, 要么 y$K_3$
• 任何点都是 3b5y, 考虑b色的图，发现违背 shaking hands lemma（3*9）

证明 $18\to(4,4)$ （定理2）

任取点存在同色9条出边

• 9出边同b色，那9个点要么 b$K_3$, 要么 y$K_4$
• 9出边同y色，那9个点要么 y$K_3$, 要么 b$K_4$

定理3 & 定理4

存在最小的

$r(y,b)\leq r(y-1,b)+r(y,b-1)$

$k\lt r(y,b)$, 当且仅当存在一个 $k$ 阶图 $\omega\lt y,\alpha\lt b$.