imported>Etone |
imported>Etone |
| Line 1: |
Line 1: |
| == Problem 1== | | =Count Distinct Elements= |
| 一个<math>k</math>-超图 (<math>k</math>-uniform hypergraph) <math>\mathcal{H}\subset{[n]\choose k}</math> 的 '''blocking set''' 是这样一个集合 <math>T\subseteq[n]</math>，使每一个超边 (hyper-edge) <math>S\in\mathcal{H}</math> 都有 <math>T\cap S\neq\emptyset</math>。
| |
|
| |
|
| 注：当 <math>k=2</math> 的时候，<math>\mathcal{H}</math> 就是一个图，而 blocking set <math>T</math> 就是这个图的顶点覆盖（vertex cover）。因此，blocking set 就是顶点覆盖在超图（hypergraph）上的推广。我们知道最小定点覆盖（minimum vertex cover）问题是 NP-hard 问题，因此求最小 blocking set 也是难的。
| | == An estimator by hashing == |
|
| |
|
| 证明：任何 <math>\mathcal{H}\subset{[n]\choose k}</math>, <math>|\mathcal{H}|=m</math>，都存在一个不大于 <math>\left\lceil\frac{n\ln m}{k}\right\rceil</math> 的 blocking set。
| | ==Flajolet-Martin algorithm== |
|
| |
|
| == Problem 2== | | = Set Membership= |
| 一个图 <math>G(V,E)</math> 的'''支配集''' (dominating set) 是一个顶点集合 <math>D\subseteq V</math>，使得每个顶点 <math>v\in V</math> 要么属于 <math>D</math> 要么有邻居属于 <math>D</math>。最小支配集 (minimum dominating set) 是 NP-hard问题。
| |
|
| |
|
| 证明：任何一个 <math>n</math> 个顶点的 <math>d</math>-regular 图（每个顶点恰好有 <math>d</math> 个邻居），必然存在一个不大于 <math>\frac{n(1+\ln(d+1))}{d+1}</math> 的支配集。
| | == Perfect hashing== |
|
| |
|
| == Problem 3 == | | == Bloom filter == |
| <math>H(W,F)\,</math> 为一个图，<math>n>|W|\,</math> 为一个整数。已知存在一个图 <math>G(V,E)\,</math> 有 <math>|V|=n, |E|=m\,</math> 且<font color=red>不包含</font> <math>H\,</math> 子图。
| |
|
| |
|
| 证明：对于 <math>k>\frac{n^2\ln n}{m}</math>，存在一个对 <math>K_n\,</math>（<math>n</math>结点完全图）的<font color=red>边</font>的 <math>k</math> 着色，没有单色（monocharomatic）的<math>H\,</math>。
| | = Frequency Estimation= |
|
| |
|
| 注：令 <math>K_n</math> 的边集为 <math>E={V\choose 2}</math>，“对 <math>K_n</math> 的边的 <math>k</math> 着色"，就是一个映射 <math>f: E\rightarrow [k]</math>。
| | == Count-min sketch== |
| 即，每个边选择 <math>k</math> 种颜色之一进行着色，可以任意着色，无需考虑相邻的边是否同色。
| |
| | |
| == Problem 4 == | |
| 令 <math>\mathcal{H}\subseteq{[n]\choose k}</math> 为一个 <math>k</math>-uniform <math>k</math>-regular hypergraph，即 <math>\forall i\in[n]</math>，刚好有 <math>k</math> 个不同的 <math>S\in\mathcal{H}</math> 满足 <math>i\in S</math>。
| |
| | |
| 假设 <math>k\ge 10</math>。证明：存在一个对 <math>[n]</math> 的 2着色 <math>f:[n]\rightarrow\{0,1\}</math> 使得 <math>\mathcal{H}</math> 中不存在单色的集合 <math>S\in\mathcal{H}</math>。
| |
| | |
| == Problem 5 ==
| |
| 一个图<math>G</math> 的 independence number <math>\alpha(G)</math> 为 <math>G</math> 中最大的独立集 (independent set) 的大小。证明Turán定理的对偶（dual）版本：
| |
| {{Theorem|定理|
| |
| :如果图 <math>G</math> 有 <math>n</math> 个结点，<math>\frac{nk}{2}</math> 条边，<math>k\ge 1</math>，则 <math>\alpha(G)\ge\frac{n}{k+1}</math>。
| |
| }}
| |
| | |
| 要求至少给出两个版本的证明：
| |
| #用概率法证明。
| |
| #用Turán定理直接证明。
| |