组合数学之Ramsey理论

1 Ramsey定理

1.1 图论Ramsey定理

双色版本

定理: 令$k,l$是正数. 那么存在一个整数$R(k,l)$满足: 如果$n\ge R(k,l)$, 对于图$K_n$的任意红蓝2着色, 要么存在红色$K_k$, 要么存在蓝色$K_l$. (即罗素数是有限的.)
证明:
对于$k+l$ 数归:

  1. $R(k,1)=R(1,l)=1$
  2. 对于一般的$k,l$, 证明$R(k,l)\le R(k,l-1)+R(k-1,l)$:
    对于$K_n$的’一个2着色, $n=R(k,l-1)+R(k-1,l)$. 对于任意点$v$, 将$V\setminus\{v\}$分成两部分: $S=\{u\in V\setminus \{v\}|uv\text{ is blue}\}$, $T=\{u\in V\setminus \{v\}|uv\text{ is red}\}$.
    因为$|S|+|T|+1=n=R(k,l-1)+R(k-1,l)$, 所以要么$|S|\ge R(k,l-1)$, 要么$|T|\ge R(k-1,l)$.
    根据对称性, 不妨设$|S|\ge R(k,l-1)$. 根据假设, $S$上的完全图要么有红色的$K_k$, 要么有蓝色的$K_{l-1}$; 如果有蓝色的$K_{l-1}$, 加上$\{v\}$就是$K_l$, 在$S\cup \{v\}$上定义的完全图中有蓝色$K_l$或者红色$K_k$.

多色版本

定理: 令$r,k_1,k_2,\cdots,k_r$是正整数. 则存在整数$R(r;k_1,k_2,\cdots,k_r)$满足任意$n\ge R(r;k_1,k_2,\cdots,k_r)$的完全图上的$r$着色, 存在同色的第$i$个颜色的$k_i$团块.

引理(the “mixing color” trick):

将最后两种颜色看做一种颜色. 如果$n\ge R(r-1;k_1,k_2,\cdots,k_{r-2}, R(2;k_{r-1},k_r))$, 对于任意$K_n$的$r$着色

  • 要么存在$i\in \{1,2,\cdots,r-2\}$和一个$k_i$大小的第$i$种颜色的团块;
  • 要么存在$R(2;k_{r-1},k_r)$个点的第$r-1$种和第$r$中颜色的团块, 而其中要么有大小为$k_{r-1}$的第$r-1$种颜色的团块, 要么有大小为$k_{r}$的第$r$种颜色的团块.
    得证.

有了这个引理后, 易证多色版本的罗素定理.

1.2 Ramsey数

最小的满足罗素定理中条件的$R(k,l)$称为罗素数. 罗素定理即$R(k,l)$是有限的.
上界: 类似上面证明中的数归易证

下界: 用概率法中的LLL可证: 存在某个常数$C$,

证明见概率法部分笔记.
因此有

1.3 超图的Ramsey定理

定理: 令$r,k_1,k_2,\cdots,k_r$是正整数. 则存在整数$R_t(r;k_1,k_2,\cdots,k_r)$满足任意$n\ge R_t(r;k_1,k_2,\cdots,k_r)$的$\binom{[n]}{t}$上的$r$着色, 存在$i\in \{1,2,\cdots,r\}$和一个满足$|X|\ge k_i$的子集$X\subseteq [n]$, $\binom{X}{t}$的所有元素都是第$i$中颜色的.

注释:

  • 之前边的$r$着色, 是$f:\binom{n}{2}\to \{1,2,\cdots,r\}$, 是每两个点对应一个颜色;

  • 现在超图中是 是$f:\binom{n}{t}\to \{1,2,\cdots,r\}$, 是每$t$个点对应一个颜色.

  • 表示为Erdős-Rado partition arrow: $n\to (k_1,k_2,\cdots,k_r)^t$

Lemma (the “mixing color” trick):

证明和上面多色图完全一样. 要证明罗素定理, 只需要证这个引理; 而证明这个引理, 只需要证明$R_t(k,l)=R_t(2;k,l)$是有限的, 而这可以通过下面的引理证明.

引理:

引理证明:

令$n=R_{t-1}(R_t(k-1,l), R_t(k,l-1))+1$, 令$f:\binom{[n]}{t}\to \{\text{red, blue}\}$, 为任意一种$\binom{[n]}{t}$的二着色. 下面证明要么存在$X\subseteq [n]$, $|X|=k$, 所有的$\binom{X}{t}$中的元素都是红色的; 要么存在$X\subseteq [n]$, $|X|=l$, 所有的$\binom{X}{t}$中的元素都是蓝色的.

从$[n]$中去掉$n$, 且定义新的着色方式: $f’:\binom{[n-1]}{t-1}\to \{\text{red, blue}\}$, 对于任意$A\in\binom{[n-1]}{t-1}$, $f’(A)=f(A\cup \{n\})$.

因为$n$的取值,

  • 要么存在子集$S\subseteq [n-1]$, $|S|=R_t(k-1,l)$, $\binom{S}{t-1}$中所有元素被$f’$着色为红色;
  • 要么存在子集$T\subseteq [n-1]$, $|T|=R_t(k,l-1)$, $\binom{T}{t-1}$中所有元素被$f’$着色为蓝色.

根据对称性, 不妨设前者成立. 则

  • 要么存在$X\subseteq S$, $|X|=k-1$, $\binom{X}{t}$中所有元素被$f$染色为红色. 因为所有的$A\in\binom{S}{t-1}$都被$f’$染色为了红色, 根据$f’$的定义, 对于所有的$A\in\binom{X}{t-1}\in\binom{S}{t-1}$, $f(A\cup \{n\})=\text{red}$. 因为$\binom{X}{t}$被$f$染色为红色, 所以$\binom{X\cup \{n\}}{t}$中所有元素被$f$染色为红色. (注: $X\cup \{n\}$中选$t$个有两种方法, 一个是$X$中选$t$个, 一种是$X$中选$t-1$个再加上$\{n\}$).
  • 要么存在$Y\subseteq S$, $|Y|=l$, $\binom{Y}{t}$中所有元素被$f$染色为蓝色, 符合要求;

得证.

2 Ramsey定理应用

2.1 The “Happy Ending” problem

The happy ending problem: 平面上任意5个点, 任意三个不共线, 则一定有四个点构成的一个凸四边形.

定理(Erdős-Szekeres 1935): 任意正整数$m\ge 3$, 总存在$N(m)$, 满足任意至少$N(m)$个点的三点不共线(general position)的平面上的点集, 都包含$m$个点构成凸$m$边形.

凸多边形的充要条件: 任意三个顶点连起来, 三角形内部不会出现其他顶点.

证明:

$N(m) = R_3(m,m)$. 令$X$为平面内的任意$n$点集, 三点不共线, $|X|=n\ge N(m)$.

如下定义3子集的2着色$f:\binom{X}{3}\to \{0,1\}$: 任意$\{a,b,c\}\in\binom{X}{3}$, 令$\triangle_{abc}\subset X$为三角形$abc$内部的点的个数. 而$f(\{a,b,c\})=|\triangle _{abc}|\mod 2$, 也就是$f(\{a,b,c\})$为三角形$abc$覆盖的点的数量的奇偶性.
因为$|X|\ge R_3(m,m)$, 所以存在$Y\subseteq X$, 满足$|Y|=m$且$\binom{Y}{3}$的所有元素都被$f$染为同色.
如果$Y$中的$m$个点不是一个凸多边形, 则存在四个点$\{a,b,c,d\}\subseteq Y$, 且$d\in \triangle_{abc}$. 因为没有三点共线, 所以

这些都是不相交的, 所以

因此$f(\{a,b,c\}), f(\{a,b,d\}),f(\{a,c,d\}),f(\{b,c,d\})$并不全相等, 和所有的$\binom{Y}{3}$中的元素都同色矛盾.
所以$Y$中的$m$个点是一个凸多边形.

2.2 Yao’s lower bound on implicit data structures

问题: 是否有$x\in S$?

排序表

引理: 令$n\ge 2$为2的幂, $N\ge 2n$. 假设全集为$[N]$, 集合的大小为$n$. 如果数据结构为排序表, 最坏情况下任何搜索算法需要至少$\log n$次数据结构的访问.

证明(归纳法+对手策略):
$n=2$且$N\ge 3$时, 最坏情况必须访问两次.

当$n>2$时, 假设对于更小的$n$都成立; $N\ge 2n$且$x=n$.
假设第一次访问在表格中的位置是$k$. 对手策略构造该位置的值$T[k]$:

根据对称性, 假设是第一种情况$k\le n/2$, 则关键字$x=n$的位置为$n/2+1$到$n$之间. 则$T[n/2+1]$到$T[n]$是一个新的排序表, 大小$n’=n/2$, 元素范围$\{n/2+1,n/2+2,\cdots,N\}$

因此最坏情况下没有搜索算法能超过二分搜索.

implicit data structure

问题: 有没有除了递增序以外的其他序, 在上面有更好的搜索算法?

定义 implicit data structure:

每个$S\in\binom{[N]}{n}$作为一个$S$的排列存储$f:\binom{[N]}{n}\to[n!]$. 如果$f(S)=\pi$, 数据集为$x_1<\cdots<x_n$, 则表为$x_{\pi(1)},\cdots, x_{\pi(n)}$.

定理(Yao 1981):

对于足够大的$N$, 在任意implicit data structure上, 任何搜索算法最坏情况下需要$\Omega(\log n)$次访问.

证明:

因为$N\ge R_n(n!;2n,\cdots,2n)$, 所以存在$X\subseteq [N]$, $|X|\ge 2n$, $\binom{X}{n}$是同色的(映射到相同的$\pi$), 那就和排序表一样, 最坏情况至少需要$\ge \log n$次访问.