Probabilistic Method

Lecture Notes for CS477 combinatorics on 2025/04/28

"定理三"

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

回顾概率方法

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

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

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

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

Another Proof. (Erdős)

Gn=(V,E),V=([n]2),E={(ij,jk):i<j<k}G_n=(V,E),V={[n]\choose 2},E=\{(ij,jk):i\lt j\lt k\} 相当于将 KnK_n 的边看成顶点. 注意必须要 i<j<ki\lt j\lt k，因此这张图最小圈为 C4={02,23,12,24,02}C_4=\{02,23,12,24,02\}. 另有 C5={01,12,23,34,13,01}C_5=\{01,12,23,34,13,01\}.

由 Ramsey, 当 n>rk(3)n>r_k(3), KnK_n 的 k-染色必有同色三角形, 因此任意的 GG 中 k-染色都不合法（KnK_n 中有三角形同色，那么KnK_n 中有相邻的边同色， GnG_n 有相邻的顶点同色，由此看出 Ramsey 给出的条件较强）.

求 χ(G2025)\chi(G_{2025}). 思路：取 i,ji,j 二进制表示，φ(i,j)=\varphi(i,j)= 两者的相同前缀长度, 得到 11 染色. 如何证明 χ(G2025)=11\chi(G_{2025})=11?

Pf. (proposed by modist) 考虑 G2025G_{2025} 所有边的 c-染色，记 C(j)={ϕ(i,j):1≤i≤j−1}C(j)=\{\phi(i,j):1\leq i\leq j-1\}, 那么不同的 C(j)C(j) 一定互不相同, 但是颜色只有 cc 种. 得到 2025≤2c2025\leq 2^c, 即 c>10c>10. 剩下的就是说明 C(j)≠C(i)C(j)\not=C(i) for j>ij>i: 如果两个集合相等，那么 ϕ(i,j)∈C(j)\phi(i,j)\in C(j) 可以推导出 ϕ(i,j)∈C(i)\phi(i,j)\in C(i), 则存在一个 z<iz\lt i ϕ(z,i)=ϕ(i,j)\phi(z,i)=\phi(i,j), 矛盾.

求证 χ≥ω+2⇒∣G∣≥10\chi\geq\omega+2\Rightarrow|G|\geq 10 (finale de autumne 2023)

我们已经有 C5∪C5C_5\cup C_5 的例子, 两个 C5C_5 之间全部连边，χ=6,ω=4\chi=6,\omega=4. 往证 ∣G∣≤9|G|\leq 9 的图必定 χ≤ω+1\chi\leq\omega+1，如果 ∣G∣=9|G|=9 的图满足，那么任何小于 9 的图 GG 也满足（添加两个孤立点或者添加两个全连接点）. 因此讨论 ∣G∣=9|G|=9, 对 ω\omega 分类讨论，逐个证明 χ≤ω+1\chi\leq\omega+1.

否定 χ≥ω+k⇒∣G∣≥5k\chi\geq\omega+k\Rightarrow|G|\geq 5k

已有的例子: kk 个 C5C_5 互相两两全部相连. ω=2k,χ=3k,n=5k\omega=2k,\chi=3k,n=5k, 发现 χ=ω+k,∣G∣=5k\chi=\omega+k,|G|=5k.

但是这其实是错误的，用渐近分析. 我们在 [Lecture 11]({{\lt relref "post/2025-04-27-happy-ending.md" >}}) 证过 r(4,t)>O(t1.5−ϵ)r(4,t)>O(t^{1.5-\epsilon}), 也就是说，存在一个阶数小于 O(t1.5−ϵ)O(t^{1.5-\epsilon}) 的图 α<4,ω<t\alpha\lt 4,\omega\lt t. 因此 χ≥nα∼O(t1.5−ϵ)3\chi\geq\frac{n}{\alpha}\sim\frac{O(t^{1.5-\epsilon})}{3}，得到 χ−ω∼n3\chi-\omega\sim\frac{n}{3}, ∣G∣∼3(χ−ω)|G|\sim3(\chi-\omega).

Erdős: 存在大于等于边数一半的割

假设我们有一个分割. 每个点同向边大于对向边时，调整至另一侧，该操作一定会停止，因为每次操作后割变大. 最后，根据握手引理，每个点对向边大于同向边，总的来说也是这样，因此割 ≥m2\geq\frac{m}{2}.

另证. 排成一排，按顺序归到左边和右边，如果一个点到前面的邻居左>右，把这个点归为右边. 这里用计数一次的握手引理.

概率方法，相当于对顶点染色，每条边给一个随机变量，异色为1，同色为0. 则全图内异色边个数的期望为 m2\frac{m}{2}.