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$.
问题:k还能再大吗?假设k=51,要求一个 $\delta\geq52$ 的诱导子图
左到右足够多的点排成一行,每个点到左边51点、右边51点连边,可以expect它平均度数大于100. 但是最左边的点度数51,去掉;因此按照这个方法会被全部去掉。
或者考虑 $K_{51,N},N\gg 51,\overline{d}=2\times\frac{51N}{51+N}\geq100$, 因此一个 $\delta\geq 52$ 的诱导子图一定不包含右边 $N$ 个点. 左边剩51个点,更不可能.
Lemma. $\delta(G)\geq k$, 那么任意一个 $k+1$ 阶树是 $G$ 的子图.
容易看到,一定存在k+1阶的星星图 or $P_{k+1}$. 树任选根,每个点由于存在至少 $k$ 个邻居,总是可以逐步拓展embedding. 如果挑到x,它的朋友都在已经选的集合中,那么已经完成.
Erdos-Sos Conjecture. $\overline{d}(G)\geq k\Rightarrow$ 任意一个 $k+1$ 阶树是 $G$ 的子图.
除了有限个反例,基本正确.
some hard problems in graph coloring

前三个解答见 Lecture 12
$\chi\geq\omega+k$ 用 k 个 $C_5$
最后一个见 girth,概率方法证明,用到了 Markov 不等式和 alteration
一些基础不等式
$$\omega\leq\chi\leq n$$$$\frac{n}{\alpha}\leq\chi\leq\Delta+1$$右边:归纳法假设30个点以下都满足 $\chi\leq\Delta+1$, 剩下一个点度数至多 29.
左边:每种颜色是一个独立集(k独立集$\iff$k染色),$n=\sum |D|\leq\sum\alpha=\chi\alpha$
问题:有没有图 $\chi\gg \frac{n}{\alpha}$?
第一反应:$K_n$ 的影子图,$n\gg \frac{2n}{n}$.
其实很容易做到,$K_n$ 再带上n个孤立点即可.
$\chi\ll\Delta+1$: star graph
$\chi=\Delta+1$: $K_n$, $C_{2k+1}$
奇妙的图 by xiaomin

定理 0407 系列
Thm 040701. $\chi(G)=k$, 则 $G$ 至少有一个点 $\deg\geq k-1$.
总有人被逼着染 k 色.
Thm 040702. $\chi(G)=100$, 则 $G$ 至少有 100 个点 $\deg\geq99$.
把度数 $\geq99$ 的点提到前面,如果有 $\lt 100$ 个这样的点,那么我可以拿着99种颜色,先给度数 $\geq 99$ 的点一人一个. 后面的点,因为度数 $\leq 98$, 用 99 个颜色一定可以染完, 得到 $\chi\leq99$, 矛盾.
归纳法:按照 $G$ 的阶数归纳,归纳起点是 $K_{100}$. 如果对任意 $|G|\lt n$ 成立,那么 $|G|=n,\chi(G)=100$ 时,若存在一个度数 $\deg v\leq98$, 那么 $\chi(G-v)=100$, $v$ 由于最多只看到98种颜色,它的染色不会影响 $G$ 的染色. 由归纳假设 $G-v$ 至少100个点 $\deg\geq k-1$.
Thm 040703’. $\chi(G)=100$, $\phi$ 最优,则 $G$ 每种颜色都有一个点 $\deg\geq 99$.
Thm 040703. $\chi(G)=100$, $\phi$ 最优,则 $G$ 每种颜色都有一个点和其他所有颜色相邻.
否则可以把这个颜色给分裂掉.
贪心染色
每次找最大独立集染色,并且去掉. 这个算法对应一种假设:
Conj. $W\subseteq G$ 为最大独立集,则有一个最优染色使 $W$ 同色.
显然错误,考虑 $P_4$.
Conj. 给定图 $G$, 存在最大独立集 $W\subseteq G$, 存在一个最优染色使 $W$ 同色.
$K_n$ 影子图
平面直线交点形成的图

$\Delta=4\Rightarrow\chi\leq 5$
四色定理$\Rightarrow\chi\leq4$ (大炮打蚊子)
Thm. (K. Wagner, 1936; I. Fáry, 1948; Sherman K. Stein, 1951, independently) 任意一个简单平面图总可以用直线段画出来.
或者 Brooks Thm
Thm. (Brooks) Connected graph in which every vertex has at most $\Delta$ neighbors, the vertices can be colored with only $\Delta$ colors, except for two cases, complete graphs and cycle graphs of odd length, which require $\Delta+1$ colors.
这启发我们,无脑染色时的“脑子”只需要保证每个点前面有足够少的邻居即可.