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)$.
$\forall c\;\exists N\;\forall\phi:[N]\to[c]\;\exists x,d$, 所有 $x,x+d,\dots,x+6kd$ 同色. 如果 d 也同色,done;否则看 2d;最后假设所有 d~kd 都和 x+id 不同色.

这样一来,可以看成 dkd(即 1k) 被 c-1 染色. 如果 k 足够大,也一定存在 $x+6y=z$ 的同色解. 设使得任意 c-染色均存在 $x+6y=z$ 同色解的最小 $N=f(c)$. 这样一来,我们要求等差数列长度至少是 $6f(c-1)+1$, 因此 $f(c)\leq W(c,6f(c-1)+1)$. $\blacksquare$
推论:$x+2y+4z=w$ 是 Ramsey 方程

Rado Theorem
$4x+7y+2z=2a+21b+3c$ 每个数可以拆成 $a=101^rq,101\not|\;q$, $\phi(a)=q\mod 101$ 即可(100染色)
假设有一个同色q解,两边约去等量的101因数,至少剩一个,假设剩余x,y,b,再模101,得到 $4q+7q=21q$, 得到 $q=0$,矛盾. (这里已经证了必要性)
Thm. (Rado) 存在 $I\subseteq[n],J\subseteq[m]$, $\sum_Ia_i=\sum_Jb_j$, 当且仅当方程 $\sum_{i=1}^n a_ix_i=\sum_{j=1}^m b_jy_j$ 是 Ramsey 的.
充分性:每次假定两个变量相等,用其中一个替换另一个. 示例:$3x+2y+5z=a+6b+4c\to^{x=y,a=c}5x+5z=5a+6b\to^{z=b}5x=5a+b$, 如果 $5x=5a+b$ 有同色解,那么原方程也有同色解.

r-regular Ramsey
$R(a_1,\dots,a_k;1)=\sum_{[k]}(a_i-1)+1$
我们估计 $R(15,26,31,17;5)$, 目标:给出的图对于任意5染色$\phi$存在15大小的同1色5子集,或者26大小的同2色5子集,…,或者存在17大小的同4色5子集。
假设挑出一个 $v$,剩下 $n-1$ 个点的4子集进行4染色,要求这个4染色是induced,i.e. $\sigma(\{a,b,c,d\})=i\iff\phi(\{v,a,b,c,d\})=i$,如果要求存在 $R(14,26,31,17;5)$ 个同1色,或…或 $R(15,26,31,16;5)$ 同4色, 那么对于这个4-子集同1色的完全图,或者同1色5子集至少14,或者同2色5子集至少26…如果加上v,由于4子集同1色完全图中,任意4-子集加上v就是同1色5子集,因此这个完全图加上v就是5子集同1色完全图。其他同理,满足条件。$R(15,26,31,17;5)\leq R(R(14,...;5),R(...,25,...;5),R(...,30,...;5),R(...,15;5);4)$
Happy Ending Problem
Thm. (Esther Klein $\to$ Esther Szekeres) 平面上不三点共线的5个点必有4个点构成凸四边形.
考虑convex hull的形状
Thm. (Erdos-Szekeres 1935) 任意k,存在足够大的n,平面上任意n个不三点共线的点,存在k点是convex的. 最小的n定义为 $N(k)$.
Pf. by Szekeres, 1931
Lem. In $\mathbb{R}^2$, k pts (no 3 pts share a line) convex $\iff$ all 4 pts subset is convex.
用一个点对凸包其他顶点连线,进行三角形划分,每个点总在一个三角形内部.
因此考虑4超图的染色,四个点是凸的染y,非凸染b,$N\geq R(k,5;4)$ 即可. 意思是,对 $N$ 点的4超图进行2染色,必有k大小的同y色4子图,或者5大小的同b色4子图,但是我们知道5个点必有凸的四边形,因此第二种情况不可能,一定存在k大小的同y色4子图. $\blacksquare$
Pf. by Taski, 1971, 于某一次组合数学考试中憋出来
旋转使得没有两个点同x,左到右编号. 任意3个点 $i\lt j\lt k,a_i,a_j,a_k$ 有两种形态: 左转y/右转b,对这个3超图染yb色. $N\geq R(k,k;3)$, k个点中任意三个转向相同即可 $\blacksquare$
Pf. 1978
任意三个点连成三角形,内部奇数个点染y,偶数个点染b. $N\geq R(k,k;3)$, 意味着对这种染色,存在k个点,任意3子集都是y色或者任意3子集都是b色. 这k点中,不存在4点非凸子集,因为 $奇+奇+奇+1=偶$,$偶+偶+偶+1=奇$. 因此k点是凸的 (别忘了加上中间的点!).
Pf. by Erdos and Szekeres, 1935 
$N(p,q)$ 表示最小的 $N$, 平面上N个点(不共线,不共x)总存在p+2个上凸或者q+2个下凸. $N(0,\_)=2$, $N(n,1)=n+2$
$N_1+1=N(p-1,q),N_2+1=N(p,q-1)$. 考虑 $N_1+N_2+1$ 个点, 即证存在p+2个上凸或者q+2个下凸. 首先抓前 $N_1$ 个,如果存在q+2下凸,done; 如果存在p+1上凸,还差1; 如果运气够好可以加点,done;
(如果运气好,阴影部分存在点,就可以加上) 
如果没得加,我们反复对前$N_1+1$个点取存在p+2个上凸或者q+2个下凸。注意每次取完,把最后一个点从待取的list中去掉,如果满足前两个的条件就返回;假设取出来的序列都不满足条件,也就是说,都是p+1上凸,且每个都不一样(指存在不同的点, 但是可能有重复的点被用到),最终挑出来 $N_2+1$ 个这样的上凸链和(被去掉的)点. 如果运气够好,这 $N_2+1$ 个点中存在p+2上凸,done;
考虑这 $N_2+1$ 个点中存在q+1下凸,从左到右$v_1,\dots,v_{q+1}$, 回想 $v_1$ 是某一条上凸链的最后一个,而且这条上凸链运气不够好. 那么有q+2下凸,done.

$N(p,q)-1\leq N_1+N_2=N(p-1,q)-1+N(p,q-1)-1\Rightarrow N(p,q)\leq{p+q\choose p,q}+1$
存在k个点上凸/下凸即可保证存在k个点凸。因此 $N(k)\leq N(k-2,k-2)\leq{2k-4\choose k-2}+1\sim 4^k$ (忽略这里的符号混用,你应该知道函数重载)
这个N(p,q)的上界还是紧的:对于 ${p+q\choose p,q}$ 个点,分裂成 ${p+q-1\choose p,q-1}+{p+q-1\choose p-1,q}=C_1+C_2$ 两个点集,其中 $C_1$ 没有p+2上凸也没有q+1下凸,$C_2$ 没有p+1上凸也没有q+2下凸(归纳假设),那么把这两个集合压扁,呈45度摆放足够远,$C_1$ 在下,$C_2$ 在上即可. 因此 $N(p,q)={p+q\choose p,q}+1$. 下面我们用这个思路证 $2^{k-2}+1\leq N(k)\leq N(k-2,k-2)$. 只需将2次幂化成组合数的和即可, 然后用上面的归纳.


https://combinatorica.hu/~p_erdos/1935-01.pdf
ramsey 数的下界
$r(k,m)> (m-1)(k-1)$, 这是 Turan 定理的直接推论
考虑 $r(k,4)$, 随便 $p$-$1-p$ yb 染色, 按照 Erdos 的策略 $X_T$ for $|T|=k$, $Y_S$ for $|S|=4$, $Z=\sum X_T+\sum Y_S$.
$$\mathbb{E}[Z]={n\choose k}(1-p)^{{k\choose 2}}+{n\choose 4}p^{6}$$我们可以期望这两项都小于1/2. 要使第二项满足,只需 $\frac{n^4}{4!}p^6\lt \frac{1}{2},\;\text{i.e. }p\lt \Big(\frac{12}{n^4}\Big)^{1/6}\sim n^{-2/3}$, 要使左边小于 1/2, 只需 ${n\choose k}e^{-p{k\choose 2}}\lt \frac{n^k}{k!}e^{-p(k-1)^2/2}\lt 1/2$, 即只需 $k\ln n-k\ln k-\frac{p(k-1)^2}{2}+\ln 2\lt 0$.
如果 $\epsilon>0$, 令 $n\sim k^{1.5-\epsilon}$, $p\sim n^{-2/3}\sim k^{-1+2\epsilon/3}$, 上式化为 $(0.5-\epsilon)k\ln k-k^{1+2\epsilon/3}\lt 0$ 我们证明了 $n\sim k^{1.5-\epsilon}$ 存在没有坏集合的染色,即 $r(k,4)>k^{1.5-\epsilon}$