Problem 1
设 $ n>rst $。证明 $ n $ 个数的实数列一定至少含有长度为 $ r $ 的严格上升子序列、长度为 $ s $ 的严格下降子序列、长度为 $ t $ 的常数列中的一个。
证
反证法，假设结论不成立。
我们为第 $ i $ 个元素 $ x_{i} $ 记下标签 $ (a_{i},b_{i}) $，其中 $ a_{i} $ 表示以 $ x_{i} $ 结尾的最长上升子序列长度，$ b_{i} $ 表示以 $ x_{i} $ 结尾的最长下降子序列长度。那么我们有 $ a_{i}\in[r-1],b_{i}\in[s-1] $。因此总共只有 $ (r-1)(s-1) $ 种标签，此时又有 $ n>t\cdot(r-1)(s-1) $，所以至少有 $ t $ 个元素的标签完全相同。
我们假设 $ a_{i}=a_{j},b_{i}=b_{j} $，可以证明 $ x_{i}=x_{j} $。如果不相等，不妨设 $ i< j $。若 $ x_{i}< x_{j} $，那么我们将 $ x_{j} $ 加到以 $ x_{i} $ 结尾的最长上升子序列之后，就得到了一个长度为 $ a_{i}+1 $ 的上升子序列，所以 $ a_{j}\geq a_{i}+1 $，与 $ a_{i}=a_{j} $ 矛盾；若 $ x_{i}>x_{j} $，同理可以得到 $ b_{j}\geq b_{i}+1 $，与 $ b_{i}=b_{j} $ 矛盾。所以一定有 $ x_{i}=x_{j} $。
所以这 $ t $ 个标签完全相同的元素本身也相同，我们就得到了一个长度为 $ t $ 的常数列，从而和我们的假设矛盾。证毕！
Problem 2
证明对于任意正整数 $ c $，存在 $ N=N(c) $ 满足对于 $ [N] $ 所有子集的任意的 $ c $-染色，存在不相交的非空集合 $ X,Y $ 满足 $ X,Y $ 和 $ X\cup Y $ 具有相同的颜色。
证
我们取 $ N(c)=R_{c}(3;2) $。对 $ [N] $ 是所有子集任意 $ c $-染色后，对于 $ K_{N} $ 中的任意一条边 $ (i,j) $，不妨设 $ i< j $，我们将它的颜色定义为集合 $ \{ i, i+1,\dots,j-1\} $ 的颜色。根据 Ramsey 定理，我们知道其中必然存在一个同色三角形，不妨设三个顶点为 $ u,v,w $，满足 $ u< v< w $，我们就知道了 $$ \{ u, \dots,v-1 \},\{ v, \dots,w-1 \}, \{ u, \dots, w-1 \} $$ 三个集合颜色相同，于是直接取 $$ \begin{align*} X & = \{ u, \dots,v-1 \} \\ Y & = \{ v, \dots,w-1 \} \\ X \cup Y & = \{ u, \dots, w-1 \} \end{align*} $$ 满足 $ X,Y,X\cup Y $ 具有相同的颜色。
Problem 3
对于任何正整数 $ c $ 和 $ l $，存在一个数 $ w = w(c, l) $，使得对集合 $ [w] = \{1, 2, ..., w\} $ 的任意 $ c $-着色，都存在一个单色的集合，其形式为 $ \{a, a + d, a + 2d, ..., a + ld\} \cup \{d\} $，其中 $ a $ 和 $ d $ 为某个正整数。
证
我们将对颜色数 $ c $ 使用数学归纳法来证明。
当 $ c=1 $，只有一种颜色，集合 $ [w] $ 中的所有整数都是同色的。我们需要找到一个单色的集合 $ \{a, a+d, ..., a+ld\} \cup \{d\} $。我们可以简单地取 $ d=1 $ 和 $ a=1 $。这样我们得到的集合是 $ \{1, 1, 1+1, 1+2, ..., 1+l\} = \{1, 2, ..., l+1\} $。为了确保这个集合包含在 $ [w] $ 中，我们只需令 $ w(1, l) = l+1 $。此时集合 $ \{1, 2, ..., l+1\} $ 中的所有元素都在 $ [l+1] $ 中，并且都是单色的。因此定理在 $ c=1 $ 时成立。
假设定理对于 $ c-1 $ 种颜色成立，即我们假设 $ w(c-1, l) $ 存在。现在我们需要证明定理对于 $ c $ 种颜色也成立。
令 $ w' = w(c-1, l) $。根据归纳假设，这个数是存在的。令 $ W = W(c, l \cdot w' + 1) $，其中 $ W(c, k) $ 保证了任何对 $ [W] $ 的 $ c $-着色都包含一个长度为 $ k $ 的单色等差数列。我们将证明 $ w(c, l) \le W $。考虑对集合 $ [W] $ 的任意一个 $ c $-着色 $ \chi $。根据定义，在 $ [W] $ 中必定存在一个长度为 $ l \cdot w' + 1 $ 的单色等差数列，我们设为 $ A = \{b, b+d', b+2d', ..., b+(l \cdot w')d'\} $，并假设它的颜色为 $ C_1 $。
现在我们考虑公差 $ d' $ 的颜色 $ \chi(d') $。分以下几种情况讨论
若 $ \chi(d') = C_1 $，在这种情况下，我们令 $ a = b $ 且 $ d = d' $。那么集合 $ \{d, a, a+d, ..., a+ld\} $ 就等于 $ \{d', b, b+d', ..., b+ld'\} $。因为 $ \{b, b+d', ..., b+ld'\} $ 是等差数列 $ A $ 的一个子集，它们的颜色都是 $ C_1 $。同时我们已知 $ \chi(d') = C_1 $。因此，我们找到了一个颜色为 $ C_1 $ 的目标单色集合。
若 $ \chi(d') \ne C_1 $ ，虑集合 $ S = \{d', 2d', 3d', ..., w'd'\} $。
如果在集合 $ S $ 中，存在某个元素 $ kd' $ 的颜色为 $ C_1 $，即 $ \chi(kd')=C_1 $。那么我们令 $ d = kd' $ 且 $ a = b $。考虑集合 $ \{d, a, a+d, ..., a+ld\} = \{kd', b, b+kd', ..., b+lkd'\} $。由于 $ k \le w' $，数列 $ \{b, b+kd', ..., b+lkd'\} $ 是原始等差数列 $ A $ 的一个子数列（因为 $ lk \le lw' $），因此它的所有元素颜色都是 $ C_1 $。又因为 $ \chi(d)=\chi(kd')=C_1 $，我们再次找到了一个颜色为 $ C_1 $ 的目标单色集合。
如果对于所有的 $ k \in \{1, 2, ..., w'\} $，颜色 $ \chi(kd') $ 都不是 $ C_1 $。这意味着对集合 $ S=\{d', 2d', ..., w'd'\} $ 的着色 $ \chi $ 只使用了 $ c-1 $ 种颜色（颜色 $ C_1 $ 被排除了）。现在我们在集合 $ [w']=\{1, 2, ..., w'\} $ 上定义一个新的着色 $ \chi' $，规则为 $ \chi'(k) = \chi(k \cdot d') $。这个新的着色 $ \chi' $ 最多只使用 $ c-1 $ 种颜色。根据我们的归纳假设，在 $ [w'] $ 上进行 $ \chi' $ 着色，必定存在一个单色的集合 $ \{d^*, a^*, a^*+d^*, ..., a^*+ld^*\} $。假设这个集合在 $ \chi' $ 着色下的颜色为 $ C_2 $ (其中 $ C_2 \ne C_1 $)。根据 $ \chi' $ 的定义，这意味着 $$ \begin{align*} \chi(d^{*}\cdot d') & = C_{2} \\ \chi(a^{*}\cdot d') & = C_{2} \\ \chi((a^{*}+d^{*})\cdot d') & = \chi(a^{*}d' + d^{*}d') = C_{2} \\ & \dots \\ \chi((a^*+ld^*) \cdot d') & = \chi(a^*d' + l(d^*d')) = C_2 \end{align*} $$ 现在，我们令 $ d = d^*d' $ 且 $ a = a^*d' $。那么我们就找到了一个在原始着色 $ \chi $ 下的单色集合 $ \{d, a, a+d, ..., a+ld\} $，其颜色为 $ C_2 $。
在所有可能的情况下，我们都能够找到所要求的单色结构。因此，归纳步骤完成，定理得证。
Problem 4
证明任何图 $ G $ 至少有 $ \binom{\chi(G)}{2} $ 条边。
证
设 $ k=\chi(G) $，我们使用 $ k $ 中颜色 $ \{ c_{1},c_{2},\dots,c_{k} \} $ 对 $ G $ 进行染色。每种颜色的点都形成了一个非空独立集，对于颜色 $ i $，我们称所有颜色为 $ c_{i} $ 的点的集合为颜色类 $ V_{i} $。对于两个不同的颜色类 $ V_{i},V_{j} $，我们证明 $ V_{i},V_{j} $ 之间至少有一条边，否则合并 $ V_{i},V_{j} $ 可以得到一个更大的独立集，从而可以只用 $ k-1 $ 中颜色染色，与最小染色矛盾。从而一共 $ k=\chi(G) $ 个颜色类，至少需要 $ \binom{ \chi(G) }{ 2 } $ 条边，因为两两之间都需要有边相连。
Problem 5
假设 $ G = (V, E) $ 是一个包含 $ n $ 个顶点和 $ m $ 条边的图。对于一条边 $ e = \{u, v\} $，令 $ t(e) $ 为包含 $ e $ 的三角形数量，并令 $ t(G) $ 为图 $ G $ 中的三角形总数。
- 证明对于每一对相邻顶点 $ (u, v) $ ，$ \deg(u) + \deg(v) - t(\{u, v\}) \leq n $ 。
- 证明 $ t(G) \geq \frac{m}{3n}(4m - n^2) $ 。
证
(1)
设 $ N(u) $ 表示与 $ u $ 相邻的点的集合，$ t(\{ u,v \}) $ 即为同时与 $ u,v $ 相邻的点的个数，为 $ \left| N(u)\cap N(v) \right| $，因此我们有 $$ \left| N(u)\cup N(v) \right| = \left| N(u) \right| + \left| N(v) \right| - \left| N(u)\cap N(v) \right| = \text{deg}(u) + \text{deg}(v) - t(\{ u,v \}) $$ 显然 $ \left| N(u)\cup N(v) \right|\leq \left| V \right|=n $，于是就得到了 $$ \deg(u) + \deg(v) - t(\{u, v\}) \leq n $$ (2)
根据 $ (1) $，我们得到 $$ t(\{ u,v \}) \geq \text{deg}(u) + \text{deg}(v) - n $$ 我们考虑 $ \sum_{e\in E}t(e) $，每个三角形包含 $ 3 $ 条边，会被统计 $ 3 $ 次，因此 $$ \sum_{e\in E}t(e) = 3t(G) $$ 同时左侧我们有 $$ \begin{align*} \sum_{e\in E}t(e) & = \sum_{\{ u,v \}\in E}t(\{ u,v \}) \\ & \geq \sum_{\{ u,v \}\in E}(\text{deg}(u)+\text{deg}(v) - n) \\ & = \sum_{u\in V}\text{deg}^{2}(u) - mn \end{align*} $$ 其中利用 Cauchy 不等式， $$ \begin{align*} \left( \sum_{u\in V}1^{2} \right)\left( \sum_{u\in V}\text{deg}^{2}(u) \right) & \leq \left( \sum_{u\in V}\text{deg}(u) \right)^{2} \\ & = 4m^{2} \\ \implies \sum_{u\in V}\text{deg}^{2}(u) & \leq \dfrac{4m^{2}}{\sum_{u\in V}1} = \dfrac{4m^{2}}{n} \end{align*} $$ 带入得到 $$ t(G) \leq \dfrac{1}{3}\left( \dfrac{4m^{2}}{n} - mn \right) = \dfrac{m}{3n}(4m - n^{2}) $$