PS 11

Problem 1

考虑证明：对这样的 k，可以使用 k 个图 G 经过顶点映射 得到的结果填满 K_n 的所有边，进而将染色方式定位每个点在第 i 个这样的映射结果中第一次出现，则将其染为第 i 种颜色，由于每个颜色类是 G 的子图，所以不会在颜色类的内部出现 H。

证明：考虑使用期望方法，随机构造 k 个这样的映射，则对于 中的任意一条边，其没有被任何一个映射覆盖到的概率为

故所有边中有任何一条没被覆盖到的概率的上界（由 Union Bound）为

带入题目提供的 下界，欲证上式小于 1，只需证

令

则 ，且

故原式在 时严格小于 0 ，即知存在一种排列方式使得所有边都被覆盖，即能够构造出这样的 ，采用上面的染色方式知原问题得证

Problem 2

考虑构造性的证明：将 的点集分为 个大小为 的点集 。

接下来考虑建边

则 ，且显然 是一个大小满足题意的独立集。

下面只需证

注意到

故只需证

由于

证毕

Problem 3

本题考虑使用 alternation method

对给定的 m ，考虑以待定的 p 随机选取顶点，通过这种方式选取到的顶点为 X 个，所包含的超边为 Y 条，那么有

于是我们将每个包含的超边去除一个点，得到

下面分类讨论

1. ，则 可以取到，此时

故必然有大小不小于 的独立集，这表明可取 3. ，则如若 ，我们令 ，则 ，考虑令

则此时

另一方面，如果 ，化归 1 的情况，由 知成立

综上，实际上可定