Problem 1
对于随机图 $ \mathcal{G}(n, p) $，属性“没有孤立点”具有一个锐阈值函数 $ p = \ln n / n $。
证
令 $ p=c\cdot \frac{\ln n}{n} $。设 $ X $ 为图中孤立点的数量。 $$ X = \sum_{i=1}^n I_i $$ 其中 $ I_i $ 是指示变量：若顶点 $ i $ 孤立，则 $ I_i=1 $，否则 $ I_i=0 $。我们需要计算 $ I_i $ 的期望 $$ \mathbf{E}[I_{i}] = (1-p)^{n-1} $$ 我们首先证明当 $ c>1 $ 时 $ \mathbb{P}(X > 0) \to 0 $。根据 Markov 不等式，有 $$ \mathbb{P}(X>0) = \mathbb{P}(X\geq 1) \leq \mathbf{E}[X] = \sum_{i=1}^{n} \mathbf{E}[I_{i}] = n(1-p)^{n-1} $$ 使用不等式 $ 1-x \le e^{-x} $ 近似 $$ \mathbf{E}[X] \le n e^{-p(n-1)} \approx n e^{-pn} = n e^{-c \ln n} = n \cdot n^{-c} = n^{1-c} $$ 因为 $ c > 1 $，所以 $ 1-c < 0 $。当 $ n \to \infty $ 时，$ n^{1-c} \to 0 $。
所以 $ P(X > 0) \to 0 $。
接着证明当 $ c< 1 $ 时 $ \mathbb{P}(X>0)\to 1 $，也就是 $ \mathbb{P}(X=0)\to 0 $。利用 Chebyshev 不等式，得到 $$ \mathbb{P}(X=0) \leq \frac{\text{Var}[X]}{\mathbf{E}[X]^{2}} = \frac{\mathbf{E}[X^{2}]}{\mathbf{E}[X]^{2}} - 1 $$ 考虑证明 $ \frac{\mathbf{E}[X^{2}]}{\mathbf{E}[X]^{2}}\to 1 $。计算 $ \mathbf{E}[X^{2}] $。首先 $$ X^{2} = \left( \sum_{i=1}^{n} I_{i} \right)^{2}= \sum_{i=1}^{n} I_{i} + \sum_{i\neq j}I_{i}I_{j} $$ 那么 $$ \mathbf{E}[X^{2}] = \mathbf{E}[X] + n(n-1)\mathbf{E}[I_{1}I_{2}] $$ 其中 $ \mathbf{E}[I_{1}I_{2}] $ 等于两个顶点同时孤立的概率，这一共涉及了 $ 2(n-2)+1=2n-3 $ 条边，因此 $$ \mathbf{E}[I_{1}I_{2}] = (1-p)^{2n-3} $$ 带入就有 $$ \frac{\mathbf{E}[X^{2}]}{\mathbf{E}[X]^{2}} = \frac{n(1-p)^{n-1}+n(n-1)(1-p)^{2n-3}}{n^{2}(1-p)^{2n-2}} \to \frac{1}{1-p} $$ 当 $ n\to \infty $ 时有 $ p\to 0 $，因此 $ \frac{1}{1-p}\to 1 $，所以就有 $ \mathbb{P}(X=0)\to 0 $，得证。
Problem 2
我们将在接下来的 3 天里在全市举办冰淇淋派对。城里有很多酒吧。每个人都提交了一份愿望清单，形式如下 $$ (P_1, d_1), (P_2, d_2), \dots, (P_{40}, d_{40}) $$ 其中 $ P_i $ 是不同的酒吧，且 $ d_i \in [3] $（即 $ d_i \in \{1, 2, 3\} $）。
如果一个人的愿望清单中至少有一个 $ (P_i, d_i) $ 满足“酒吧 $ P_i $ 在第 $ d_i $ 天举办派对”，那么这个人就是满意的。
这些愿望清单非常“友好”，每个酒吧最多出现在 2024 份清单上。
证明：我们可以安排派对（使得每个酒吧只在某一天举办一次派对），从而让所有提交清单的人都满意。
证
对每个酒吧，独立均匀地从 $ \{ 1,2,3 \} $ 中随机选出一天举办配对，从而每个酒吧选定特定一天的概率是 $ \frac{1}{3} $。
设总共 $ n $ 个人，对于第 $ i $ 个人，定义坏事件 $ A_{i} $ 为第 $ i $ 个人不满意。某个坏事件发生当且仅当这个人的愿望全部落空。由于清单上的 $ 40 $ 个酒吧是互不相同的，它们选日子的行为是相互独立的。因此，$ A_i $ 发生的概率为： $$ P(A_i) = \left( \frac{2}{3} \right)^{40} $$ 我们将这个概率上界记为 $ p $。即 $ p = (2/3)^{40} $。
我们需要确定每个坏事件 $ A_i $ 最多依赖于多少个其他的坏事件。这构成了依赖图的最大度数 $ \Delta $。由于每个酒吧至多出现在 $ 2024 $ 个清单，并且每个人愿望有 $ 40 $ 个酒吧，因此 $$ \Delta \leq 40 \times 2024 = 80920 $$ 利用对称 LLL 条件，带入数值可以验证验证 $$ e\cdot p \cdot (\Delta+1) < 1 $$ 从而一定存在方案能满足所有人。
Problem 3
设 $ k \ge 10 $ 为一个整数，$ H = (V, E) $ 是一个 $ k $-均匀、$ k $-正则的超图。 请证明：$ H $ 存在一个正常 $ 2 $-染色。
证
我们随机地对 $ H $ 的每一个顶点进行染色。每个顶点染成红色或蓝色的概率均为 $ 1/2 $，且相互独立。对于超图中的每一条边 $ e \in E $，定义坏事件 $ A_e $ 为边 $ e $ 是单色的。显然 $$ \mathbb{P}(A_{e}) = 2^{1-k} $$ 考虑一条边 $ e $ 最多与多少条其他边有依赖关系，也就是和其他边相交。根据 $ k $-均匀和 $ k $-正则的性质，显然依赖图的最大度数 $ \Delta $ 满足 $$ \Delta \leq k(k-1) $$ 从而利用对称版本的 LLL 条件，只需要验证 $$ e\cdot 2^{1-k}\cdot(k(k-1)+1) \leq 1 $$ 利用比值可以证明这关于 $ k $ 在 $ k\geq 10 $ 时递减，并且带入 $ k=10 $，满足 $$ e\cdot 2^{-9}\cdot 91 < 1 $$ 从而满足 LLL 条件，存在一种染色方案使得没有坏事件发生。
Problem 4
范德瓦尔登数 $ W(2, k) $ 定义为使得“对集合 $ \{1, 2, \dots, n\} $ 进行任意 $ 2 $-染色都必然包含一个长度为 $ k $ 的单色等差数列”的最小整数 $ n $。 证明：$ W(2, k) > \frac{2^k}{2ek} $。
证
要证明 $ W(2, k) > N = \lfloor \frac{2^k}{2ek} \rfloor $，等价于证明对于 $ n = N $，存在一种 $ 2 $-染色方案，使得其中不包含任何长度为 $ k $ 的单色等差数列。
对集合 $ \{1, 2, \dots, n\} $ 中的每个数字随机染红或蓝，概率各为 $ 1/2 $。设 $ S $ 是集合中的任意一个长度为 $ k $ 的等差数列。定义坏事件 $ A_S $ 为该等差数列是单色的。同样 $$ p = \mathbb{P}(A_{S}) = 2^{1-k} $$ 考虑两个坏事件的依赖关系，这当且仅当两个等差数列至少共享一个数字。由于一个等差数列可以由首项和公差确定，而公差至多只有 $ n $ 个取值，因此包含某个指定元素的等差数列至多只有 $ n $ 个。这样就得到了与选定等差数列相交的等差数列数量的一个宽松上界 $ \Delta\leq k\cdot n $。
带入 LLL 条件，我们需要找到最大的 $ n $ 使得 $$ e\cdot p\cdot (\Delta+1) \leq 1 $$ 带入就得到了 $$ e\cdot 2^{1-k}\cdot kn \leq 1 \implies n\leq \frac{1}{e\cdot k\cdot 2^{1-k}} = \frac{2^{k}}{2ek} $$ 从而只要 $ n\leq \frac{2^{k}}{2ek} $ 成立，就必然存在某种染色方案使得没有单色等差数列，因此这就证明了 $$ W(2,k) > \frac{2^{k}}{2ek} $$