Happy Ending Problem

April 27, 2025

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 不同色.

这样一来，可以看成 d~~kd(即 1~~k) 被 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}$

Combinatorics