Problem 1
图 $ G=(V,E) $ 有 $ n $ 个顶点和 $ m $ 条边，图 $ H $ 是较小的图，且 $ G $ 不包含 $ H $ 作为子图。证明当 $ k > n^2 \ln n / m $ 时，完全图 $ K_n $ 存在一种边 $ k $-染色方案，使得 $ K_n $ 中不存在单色的 $ H $。
证
令 $ V $ 为 $ K_{n} $ 的顶点集。随机选取 $ k $ 个 $ V $ 上的随机排列，将 $ G $ 映射到 $ V $，得到与 $ G $ 同构的 $ k $ 个图 $ G_{1},\dots,G_{k} $。
考虑 $ K_{n} $ 中的任意一条边 $ e $ 未被覆盖的概率。对于任意一个图，$ e $ 在这个图中的概率为 $$ p = \mathbb{P}[e\in E(G_{i})] = \frac{m}{\binom{ n }{ 2 } } $$ 从而 $$ \mathbb{P}\left[ e\not\in \bigcup_{i=1}^{k}E(G_{i}) \right] = (1-p)^{k} = \left( 1-\frac{m}{\binom{ n }{ 2 } } \right)^{k} $$ 我们证明存在一种方案使得 $ K_{n} $ 的所有边都被覆盖，等价于证明至少有一条边未被覆盖的概率小于 $ 1 $。设事件 $ A $ 表示至少有一条边未被覆盖，那么根据 Union Bound，有 $$ \mathbb{P}[A] \leq \sum_{e\in E(K_{n})}\mathbb{P}\left[ e\not\in \bigcup_{i=1}^{k}E(G_{i}) \right] = \binom{ n }{ 2 } \left( 1-\frac{m}{\binom{ n }{ 2 } } \right)^{k} $$ 带入不等式 $ 1-x< e^{ -x } $，我们尝试证明 $$ \binom{ n }{ 2 } \exp\left( -\frac{mk}{\binom{ n }{ 2 } } \right) < 1 $$ 化简就得到了在 $$ k > \frac{\binom{ n }{ 2 }}{m}\ln \binom{ n }{ 2 } $$ 时不等式成立。
由于 $$ k > \frac{n^{2}}{m}\ln n = \frac{n^{2} / 2}{m}\ln n^{2} > \frac{\binom{ n }{ 2 } }{m}\ln \binom{ n }{ 2 } $$ 因此必有 $ \mathbb{P}[A] < 1 $，从而一定存在一组副本 $ G_1, \dots, G_k $，它们的并集覆盖了 $ K_n $ 的所有边。于是我们定义我们定义边染色如下：对于 $ K_n $ 中的每条边 $ e $，定义其颜色 $ c(e) $ 为覆盖它的最小的副本索引 $$ c(e) = \min \{i \mid e \in E(G_i)\} $$ 在这种染色方案下，对于任意颜色 $ i $，所有颜色为 $ i $ 的边组成的集合 $ E_i $ 都是 $ E(G_i) $ 的子集，即 $ E_i \subseteq E(G_i) $。因为 $ G_i \cong G $，而已知 $ G $ 不包含 $ H $ 作为子图，所以 $ G_i $ 也不包含 $ H $，因此，它的子集 $ E_i $ 也不可能包含 $ H $。
综上所述，$ K_n $ 的这种 $ k $-边染色中不包含单色的 $ H $。得证。
Problem 2
证明对于任意 $ r $ 和 $ n $（为简化假设 $ n $ 能被 $ r $ 整除），存在一个定义在 $ [n] $ 上的 $ r $-一致超图 $ \mathcal{H} $，至少有 $ \binom{n}{r}/e^r $ 条超边，其独立数满足 $$ \alpha(\mathcal{H}) \geq n(1 - \frac{1}{r}) $$ 超图的独立集是指不包含任何完整超边的顶点子集。
证
我们将 $ n $ 个顶点均分成 $ r $ 个组，每组大小均为 $ \frac{n}{r} $。定义 $ \mathcal{H} $ 的边集 $ E $ 满足一个 $ r $ 元组 $ \{ v_{1},v_{2},\dots,v_{n} \} $ 为一条边当且仅当每个 $ v_{i} $ 来自不同的组。这样我们任意删掉一组边，剩下的顶点数为 $$ n - \left| V_{1} \right| = n\left( 1-\frac{1}{r} \right) $$ 构成了一个独立集。从而这个构造的独立数满足要求。
下面我们验证这个构造的边数符合要求。由于每组可以任取一个点形成边，因此 $$ \left| E \right| = \left| V_{1} \right| ^{r} = \left( \frac{n}{r} \right)^{r} $$ 因此我们只需要证明 $$ \left( \frac{n}{r} \right)^{r} > \dfrac{\binom{ n }{ r } }{e^{ r }} $$ 变形后等价于证明 $$ \binom{ n }{ r } < \left( \frac{ne}{r} \right)^{r} $$ 由于 $$ e^{ r } = 1 + r + \dots + \frac{r^{r}}{r!} + \dots > \frac{r^{r}}{r!} \implies \frac{1}{r!} < \frac{e^{r}}{r^{r}} $$ 那么 $$ \binom{ n }{ r } = \frac{n^{\underline{r}}}{r!} < \frac{n^{r}}{r!} < \frac{e^{r}}{r^{r}}\cdot n^{r} = \left( \frac{ne}{r} \right)^{r} $$ 证毕。
Problem 3
证明对于任意常数 $ c_1 > 0 $，都存在另一个常数 $ c_2 > 0 $，使得对于任意包含 $ n $ 个顶点、$ m $ 条超边的 $ 3 $-一致超图 $ \mathcal{H} $，只要满足 $ m \geq c_1 n $，就有 $$ \alpha(\mathcal{H}) \geq \frac{c_2 n \sqrt{n}}{\sqrt{m}} $$ 证
设 $ \mathcal{H} = (V, E) $ 是一个 $ 3 $-一致超图，顶点数 $ |V|=n $，边数 $ |E|=m $。 构造一个随机顶点子集 $ S \subseteq V $，其中每一个顶点 $ v \in V $ 被选入 $ S $ 的概率都是 $ p $，且各顶点是否被选是相互独立的。
令随机变量 $ X = |S| $ 表示 $ S $ 中的顶点数量，随机变量 $ Y $ 表示 $ S $ 中包含的完整超边的数量。计算它们的期望 $$ \mathbf{E}[X] = \sum_{v\in V}\mathbb{P}[v\in S] = n\cdot p $$ 由于一条超边包含三个独立选择的顶点，因此 $ \mathbb{P}[e\subseteq S]=p^{3} $，从而 $$ \mathbf{E}[Y] = \sum_{e\in E}\mathbb{P}[e\subseteq S] =m\cdot p^{3} $$ 我们现在考虑将随机选择的 $ S $ “修剪”成一个独立集。对于 $ S $ 中的每一条边，从 $ S $ 中移除这条边中的任意一个顶点，剩下的集合记为 $ S' $。最坏情况每条边都要删掉一个不同的点，所以 $$ \left| S' \right| \geq X-Y $$ 从而 $$ \mathbf{E}[\left| S' \right| ]\geq \mathbf{E}[X]-\mathbf{E}[Y] = np-mp^{3} = f(p) $$ 我们需要选出一个合适的 $ p $ 来最大化下界 $ f(p) $，经过简单的求导计算可知在 $$ p^{*}=\sqrt{ \frac{n}{3m} } $$ 时 $ \dfrac{\mathrm{d} f}{\mathrm{d}p}=0 $，带入题设条件 $ m\geq c_{1}n $，有 $$ p^{*} \leq \sqrt{ \frac{1}{3c_{1}} } $$ 如果 $ c_{1}\geq \frac{1}{3} $，那么 $ p^{*}\leq 1 $。从而直接取 $ p=p^{*} $，带入得到了 $$ \alpha(\mathcal{H}) \geq f(p^{*}) = \frac{2}{3\sqrt{ 3 }} \frac{n\sqrt{ n }}{\sqrt{ m }} $$ 这是取常数 $ c_{2}= \frac{2}{3\sqrt{ 3 }} $ 即可。
如果 $ c_{1}< \frac{1}{3} $，那么利用 $$ m\geq c_{1}n \implies \sqrt{ \frac{c_{1}n}{m} } \leq 1 $$ 带入 $ p=\sqrt{ \frac{c_{1}n}{m} } $，得到 $$ \begin{align*} \alpha(\mathcal{H}) & \geq f(p) \\ & = n\left( \sqrt{ c_{1} }\sqrt{ \frac{n}{m} } \right) - m\left( \sqrt{ c_{1} }\sqrt{ \frac{n}{m} } \right)^{3} \\ & = (\sqrt{ c_{1} }-c_{1}\sqrt{ c_{1} }) \frac{n\sqrt{ n }}{\sqrt{ m }} \end{align*} $$ 由于 $ c_{1}< \frac{1}{3}< 1 $，因此 $ \sqrt{ c_{1} }-c_{1}\sqrt{ c_{1} }>0 $，从而取 $ c_{2}=\sqrt{ c_{1} }-c_{1}\sqrt{ c_{1} } $ 即可。