Problem 1
设 $ H = (V, \mathcal{F}) $ 是一个没有孤立点的超图，满足每条超边至少包含 3 个顶点，且任意两条超边恰好共享一个顶点。假设 $ H $ 不是 2-可着色的（即不能用两种颜色对顶点染色使得每条超边内都有不同颜色的点）。
(1)
证明每个顶点 $ v $ 至少属于 $ \mathcal{F} $ 中的两条超边。
证
假设存在一个顶点 $ v $ 满足 $ d(v)< 2 $。由于没有孤立顶点，因此 $ d(v)=1 $，恰好属于一条超边，记为 $ E $。
我们将顶点 $ v $ 染成红色，将 $ E $ 中的其他点染成蓝色，再将图中除了 $ E $ 之外的所有点染成红色。由于任意两条超边恰好共享一个顶点，并且 $ v $ 只在 $ E $ 中，所以任意一条超边必然和 $ E $ 存在蓝色交点，存在颜色不同的点。因此我们就构造出了一个合法的 2-着色方案，与题设矛盾。
因此每个顶点至少属于两条超边。证毕。
(2)
证明任意两个顶点 $ u, v $ 恰好共同属于 $ \mathcal{F} $ 中的一条超边。
证
假设存在两个顶点 $ u,v $，它们不共同属于任何一条超边。定义 $ N_{u} $ 为与 $ u $ 在同一条超边上的邻居，那么 $ v\not\in N_{u} $。
我们构造染色方案，首先将 $ u $ 染为红色，$ N_u $ 中的所有点染为蓝色，其余顶点（包括 $ v $）染为红色。
首先检查是否存在全红边。经过 $ u $ 的边包含 $ u $（红）和 $ N_u $ 中的点（蓝），非单色和边。对于不经过 $ u $ 的任意边 $ E $，根据 $ (1) $ 有 $ d(u)>1 $，$ u $ 至少被两条边经过，设为 $ L_1, L_2 $，则 $ E $ 必与 $ L_1, L_2 $ 分别交于 $ x, y $。由于 $ u \notin E $，交点 $ x, y $ 必然都在 $ N_u $ 中且 $ x \neq y $。因此，任何不经过 $ u $ 的边起初至少包含两个蓝色点，不可能为全红。
其次检查是否存在全蓝边。若存在全蓝边 $ F \subseteq N_u $，则 $ u $ 的度数 $ d(u)=|F| \ge 3 $，这使得任意不经过 $ u $ 的边在 $ N_u $ 中初始至少拥有 3 个蓝色顶点（即 $ u $ 的每个分支各贡献一个）。由于全蓝边集两两相交，根据几何性质，至多只需将 2 个公共顶点改染红色即可破坏所有全蓝边。因为 $ 3 > 2 $，任何不经过 $ u $ 的边在染色修正后仍保留至少一个蓝点；而经过 $ u $ 的边因包含 $ u $ 且未翻转其所有邻居，也绝非全红，故矛盾成立。
同时检查这时是否新产生了全红边：任何包含 $ w $ 的新红边，若经过 $ u $，则除 $ u, w $ 外必有第三点属于 $ N_u $（仍为蓝）；若不经过 $ u $，该边原先至少有两个蓝点，翻转 $ w $ 后仍剩至少一个蓝点。
综上，我们总能构造出合法的 2-染色，这与题目条件矛盾，故假设不成立，任意两点必须共边。
Problem 2
证明每一个拥有 $ m $ 条边的图，都包含一个至少拥有 $ (1 - 1/k)m $ 条边的 $ k $-可着色子图。
证
我们对图中每个点独立均匀随机地染成 $ k $ 种颜色中的一种，记这 $ k $ 种颜色为 $ \{ 1,2,\dots,k \} $，顶点 $ v $ 的颜色为 $ X_{v} $，那么 $$ \mathbb{P}(X_{v}=u)=\frac{1}{k} $$ 再对每条边 $ e=(u,v) $ 定义指示变量 $ Y_{e}=\mathbb{I}[X_{u}\neq X_{v}] $。从而 $$ \mathbb{P}(Y_{e}=0)= \sum_{i=1}^{k} \frac{1}{k^{2}} = \frac{1}{k} $$ 从而 $$ \mathbf{E}[Y_{e}] = 1\cdot \mathbb{P}(Y_{e}=1) + 0 \cdot \mathbb{P}(Y_{e}=0) = 1- \frac{1}{k} $$ 当 $ Y_{e}=1 $ 说明一条边两端点颜色不同，可以被保留进需要的 $ k $-可着色子图。我们计算最终保留的总边数 $ Y $，为所有指示变量之和 $$ Y=\sum_{e\in E}Y_{e} $$ 那么 $$ \mathbf{E}[Y] = \sum_{e\in E}\mathbf{E}[Y_{e}] = m\left( 1-\frac{1}{k} \right) $$ 由于 $ Y $ 的取值不可能总是小于 $ \mathbf{E}[Y] $，因此必然存在一种方案使得保留下的边数满足 $$ Y \geq \mathbf{E}[Y]=m\left( 1-\frac{1}{k} \right) $$ 由于留下的每一条边端点颜色都不同，因此这是一个 $ k $-着色子图。
Problem 3
设 $ n \ge 4 $ 且 $ t \ge 3\sqrt{n} $。证明：对于任意元素互不相同的 $ n \times n $ 实数矩阵 $ A $，我们可以通过重排其列得到一个新矩阵 $ B $，使得在 $ B $ 中没有任何一行包含长度为 $ t $ 的单调子序列。
证
设矩阵 $ A $ 的列下标集合为 $ \{1, 2, \dots, n\} $。我们在所有可能的列排列（共 $ n! $ 种）中，均匀随机地选取一种排列 $ \sigma $，按照该排列重排 $ A $ 的列得到新矩阵 $ B $。
记事件 $ E $ 为“矩阵 $ B $ 中至少有一行包含长度为 $ t $ 的单调子序列”。如果能证明 $ \mathbb{P}(E) < 1 $，则根据概率法的原理，满足条件的排列必然存在。
题目条件为 $ n \ge 4 $ 且 $ t \ge 3\sqrt{n} $。我们首先考察 $ n $ 较小的情况。当 $ 4 \le n < 9 $ 时 $$ \sqrt{n} < 3 \implies 3\sqrt{n} > n $$ 由于 $ t \ge 3\sqrt{n} $，此时有 $ t > n $。 在一个仅有 $ n $ 个元素的行中，显然不可能存在长度为 $ t $（且 $ t > n $）的子序列。 因此，当 $ n < 9 $ 时，事件 $ E $ 发生的概率为 $ \mathbf{0} $。结论显然成立。
当 $ n\geq 9 $ 时，考虑利用 Union Bound 估计上界。设 $ E_{i} $ 为第 $ i $ 行包含长度为 $ t $ 的单调子序列的事件。那么 $$ \mathbb{P}(E) = \mathbb{P}\left( \bigcup_{i=1}^{n}E_{i} \right) \leq \sum_{i=1}^{n} \mathbb{P}(E_{i}) = n\cdot \mathbb{P}(E_{1}) $$ 对于 $ E_{1} $，我们考虑从 $ n $ 个元素选择 $ t $ 个位置，共 $ \binom{ n }{ t } $ 中选法。对于选定 $ t $ 个元素，在 $ t! $ 种可能的排列中，只有 $ 2 $ 种是单调的，从而有上界 $$ \mathbb{P}(E_{1}) \leq \binom{ n }{ t } \frac{2}{t!} $$ 带入就有 $$ \mathbb{P}(E) \leq n\cdot \binom{ n }{ t } \frac{2}{t!} $$ 利用不等式 $ \binom{n}{t} \le \frac{n^t}{t!} $ 对上界进行放缩，可得 $$ \mathbb{P}(E) \leq n \cdot \frac{n^t}{t!} \cdot \frac{2}{t!} = \frac{2n^{t+1}}{(t!)^2} $$ 由条件 $ t \ge 3\sqrt{n} $ 可知 $ n \le \frac{t^2}{9} $。将此不等式代入上式，我们将变量统一为 $ t $。记该上界函数为 $ f(t) $，则 $$ \mathbb{P}(E) \leq \frac{2(t^2/9)^{t+1}}{(t!)^2} = f(t) $$
由于 $ n \ge 9 $，故 $ t \ge 3\sqrt{9} = 9 $。我们首先验证 $ t $ 取最小值 $ 9 $ 时的情况： $$ f(9) = \frac{2 \cdot (9^2/9)^{10}}{(9!)^2} = \frac{2 \cdot 9^{10}}{(362880)^2} \approx \frac{6.97 \times 10^9}{1.31 \times 10^{11}} \approx 0.053 < 1 $$
接下来考察 $ f(t) $ 随 $ t $ 增大的变化趋势。利用 Stirling 公式 $ t! \approx \sqrt{2\pi t}(t/e)^t $ 估算其量级，分母 $ (t!)^2 $ 的增长主要由 $ t^{2t} $ 主导，而分子的增长主要由 $ (t^2)^t = t^{2t} $ 以及常数底数因子主导。具体观察其底数比率 $$ \frac{n^{t+1}}{(t!)^2} \approx \frac{(t^2/9)^t}{(t/e)^{2t}} = \left( \frac{t^2}{9} \cdot \frac{e^2}{t^2} \right)^t = \left( \frac{e^2}{9} \right)^t $$ 由于 $ e^2 \approx 7.39 < 9 $，该底数小于 $ 1 $，因此 $ f(t) $ 以指数级速度趋于 $ 0 $。
综上所述，对于所有 $ n \ge 9 $ 且 $ t \ge 3\sqrt{n} $，都有 $ \mathbb{P}(E) \le f(t) \le f(9) < 1 $。这表明在所有 $ n! $ 种排列中，必然存在一种排列，使得生成的矩阵 $ B $ 中没有任何一行包含长度为 $ t $ 的单调子序列。
证毕。
Problem 4
设 $ v_1, \dots, v_n $ 是 $ \mathbb{R}^n $ 中的 $ n $ 个单位向量。证明存在一组符号 $ \epsilon_i = \pm 1 $，使得 $ \|\epsilon_1 v_1 + \dots + \epsilon_n v_n\| \le \sqrt{n} $，并且证明 $ \sqrt{n} $ 这个界限是不可改进的。
证
首先证明存在性。明存在一组符号 $ \epsilon_i \in \{+1, -1\} $，使得 $ \|\sum \epsilon_i v_i\| \le \sqrt{n} $。假设 $ \epsilon_1, \epsilon_2, \dots, \epsilon_n $ 是独立同分布的随机变量，且取值概率满足 $$ \mathbb{P}(\epsilon_i = 1) = \frac{1}{2}, \quad \mathbb{P}(\epsilon_i = -1) = \frac{1}{2} $$ 这意味每个 $ \epsilon_i $ 的期望值为 $ E[\epsilon_i] = 0 $，方差为 $ E[\epsilon_i^2] = 1 $。
考察向量和模长的平方。设随机变量 $ X $ 为 $$ X = \left\| \sum_{i=1}^n \epsilon_i v_i \right\|^2 $$ 展开得到 $$ \begin{aligned} X &= \left\langle \sum_{i=1}^n \epsilon_i v_i, \sum_{j=1}^n \epsilon_j v_j \right\rangle \\ &= \sum_{i=1}^n \sum_{j=1}^n \epsilon_i \epsilon_j \langle v_i, v_j \rangle \end{aligned} $$ 根据期望的线性性，有 $$ \mathbf{E}[X] = \sum_{i=1}^n \sum_{j=1}^n \mathbf{E}[\epsilon_i \epsilon_j] \langle v_i, v_j \rangle $$ 我们需要计算 $ E[\epsilon_i \epsilon_j] $。分别考虑 $ i=j $ 和 $ i\neq j $，有 $$ \mathbf{E}[\epsilon_{i}^{2}]=1,\quad \mathbf{E}[\epsilon_i \epsilon_j] = \mathbf{E}[\epsilon_i] \cdot \mathbf{E}[\epsilon_j] = 0 \cdot 0 = 0 $$ 从而 $$ \mathbf{E}[X] = \sum_{i=1}^n 1 \cdot \langle v_i, v_i \rangle = \sum_{i=1}^n \|v_i\|^2=n $$ 由于一个随机变量的取值不可能严格大于它的期望，因此执照存在一组特定的符号使得 $$ \left\| \sum_{i=1}^n \epsilon_i v_i \right\|^2 \le n $$ 从而就证明了 $$ \left\| \sum_{i=1}^n \epsilon_i v_i \right\| \le \sqrt{n} $$ 接着我们证明 $ \sqrt{ n } $ 是紧的。取 $ \mathbb{R}^{n} $ 中的一组标准正交基，那么这时无论如何选择符号，模长都恒等于 $ \sqrt{ n } $，从而不可能存在比 $ \sqrt{ n } $ 更小的上界。