用容器定理测试图的性质
Testing Graph Properties with the Container Method
本文对于检测一张图是否包含$\rho-clique$性质的判断建立了接近最优的采样复杂度。同时，本文也为$\epsilon-testing\ k-colorability$问题找到了新的采样复杂度上界。
以上两个结论的得出都依赖于$graph\ container\ method$。
1. 问题引入以及一些即将用到的概念的说明
是否可以通过只检验图的一小部分得出整张图是否包含一个大的$clique$或者整张图是否$k-colorable$? 这两个问题是$graph\ property\ testing$领域的经典问题，它们可以被严谨表述成以下形式：
- A (simple undirected) graph $G$ on $n$ vertices is $\epsilon-far$ from a property $\Pi$ if we need to add or remove at least $\epsilon n^2$ edges from $G$ to obtain a graph that does have the property $\Pi$.
- A canonical $\epsilon-testor$ for $\Pi$ with sample cost $s$ is a bounded -error randomized algorithm that samples a set $S$ of $s$ vertices of some unknown graph $G$, examines the induced subgraph G[S], and based only on this local view of the graph can distinguish between the case where $G$ has property $\Pi$ and the case where it is $\epsilon-far$ from $\Pi$.
- The sample complxity of $\Pi$, denoted $\mathcal{S}_{\Pi}(n,\epsilon)$, is the minimum value #s# for which there is a canonical $\epsilon-tester$ for $\Pi$ with sample cost $s$.
1.1 检测 $Clique$ 性质
我们定义$\rho-clique$性质指所有包含大小为$\rho n$的$clique$的$n$顶点图。
这里$\rho$依据图的大小一般有两种常见定义：
- 当要研究large clique结构时，我们一般会固定$\rho$为常数
- 当要研究图small clique结构时，我们一般取$\rho=\rho(n)$，其中$n$为图中顶点数。注意到如果$\epsilon\lt\rho^2$时，问题将不再有意义，因为我们总是可以加入${\rho\epsilon\choose 2}\lt \rho^2 n^2$条边来得到一张有$\rho n-clique$的图。
关于检测$\rho-clique$性质，我们将在本文证明以下命题：
Theorem 1 The sample complexity of the $\rho-clique$ property is $\mathcal{S}_{\rho-clique}(n,\epsilon)=\tilde{O}(\frac{\rho^3}{\epsilon^2})$.
1.2 检测 $k-colorablility$
我们定义$k-colorable$性质指所有顶点数为$n$且可以被$k$着色的图。
当$k=2$，则$k-colorable$等价于二分性。对于二分性的检测，一个接近最优的解是$\mathcal{S}_{2-colorable}(n,\epsilon)=\tilde{\Theta}(1/\epsilon)$。所以我们关注$k\geq 3$时的情况。
对于$k-colorable$问题我们同样关注两种组织结构：
- $low\ chromatic\ number$：此时$k$为常数。
- $polychromatic$：此时$k=k(n)$是关于顶点数$n$的函数。注意此时只有当$\epsilon<1/k$时问题才是有意义的，否则我么可以消除至多$k{n/k\choose 2}\leq n^2/k$条边得到一张$k-colorable$的图。$\Longleftarrow$ 这里考虑将顶点集随意划分为$k$块，每块大小为$n/k$，则我们需要消除每部分内部的边，而内部边数可以被$k{n/k\choose 2}$给bound住，于是得到上面关于$no\ trivial$条件的判定结论。
关于$k-colorability$，我们将在本文证明以下命题：
Theorem 2 The $k-colorable$ proprety has sample complexity $\mathcal{S}_{k-colorable}(n,\epsilon)=\tilde{O}(\frac{k}{\epsilon})$.
1.3 图的容器定理
Theorem1和Theorem2都建立在使用传统tester检测我们采样得到的导出子图$G[S]$是否具有相应性质的基础上。当我们在检测图是否包含large clique结构时，对于确实包含$\rho n-clique$的图，由Theorem1得到的tester将以至少$1/2$的概率accepts；而在$k-colorablility$的检测时，对于确实具有该性质的图，由Theorem得到的tester的输出总是accepts。（详见PART 3 & 4）
难点在于证明tester会以一个比较高的概率拒绝距离该性质较远的图，我们将通过graph container method解决这个问题。
首先，我们知道graph container method是以independent sets为对象进行陈述的。所以比起检测一张图是否有$\rho-cliques$，我们的容器应用于检测图中是否有$\rho-independent\ sets$时更为自然。所以我们只需要在原图的补图中检测是否有$\rho-independent\ sets$即可（换句话说，可以得到$\rho-cliques\leq_k\rho-independent\ sets$。
简单来说，graph container method说的是，尽管一张图中可能包含大量的independent sets，但是对于任意图$G$，我们都可以找到一个很小的容器集，其中（1）每个容器都不大；（2）每个独立集都是至少一个容器的子集；（3）对于每个容器$C$，导出子图$G[C]$都是稀疏的。container method最早由Kleitman和Winston提出，而后有很多变体（前几章讲义中列举了一些），这里对于Theorem 1和Theorem 2的证明所使用的是container method最初的版本（也就是Kleitman和Winston最早提出的container method），我们需要用到container集合的构建过程中的greedy算法来证明我们的目标。
在正式深入前，我们先呈现一下我们的证明思路：
- 假设$S$是tester在$G$中随机采样得到的$s$个顶点，由graph container method知任何一个独立集$S$都具有唯一一个很小的指纹，这个指纹会对应一个大小有限的container。我们将证明$S$包含对应container中多于$\rho s$个顶点的概率是极小的，小到即使对所有可能的指纹使用了联合界，这个概率也不会很大。详细证明见PART 3。
- 对于检测$k-colorability$，大致思路是类似的，唯一的区别在于这里我们要对采样集中的任意$k$个独立集对应的$k$个指纹，它们对应的containers有一个比较小的联合界。详细证明见PART 4。
2.The Container Method再利用
独立集fingerprints和containers的构建采用Algorithm1，其大致思路与Kleitman和Winston版本相同，也用到了greedy的思想：
- 每次加入fingerprint$S$中的点$v$都是independent set $I$在$G[C_{t-1}]$中度数最高的点。
- 因为$I$是一个independent set，所以$v$的所有邻居肯定不在$I$中，所以可以从$C_t$中移除。
- 因为$v$是$I$在图$G[C_{t-1}]$中度数最高的点，所以所有在$G[C_{t-1}]$中所有度数高于$I$的点都不在$I$中，可以从$C_{t}$中移除。
这个过程直到所有$I$中点都被选入fingerprint后才结束。
Algorithm
Input: A graph $G=(V,E)$ and an independent set $I\subset V$
Initialize $F_0\leftarrow \emptyset$ and $C_0\leftarrow V$;
for $t=1,2,…,|I|$ do
$v_t \leftarrow$ the vertex in $I\backslash F_{t-1}$ with the largest degree in $G[C_{t-1}]$;
//Add $v_t$ to the fingerprint:
$F_t\leftarrow F_{t-1}\cup\{v_t\}$;
//Remove all the neighbours of $v_t$ from the container:
$C_t\leftarrow C_{t-1}\backslash\{w\in C_{t-1}:(v,w)\in E\}$;
//And remove all vertices with higher degree than $v_t$ in $G[C_{t-1}]$:
$C_t\leftarrow C_t\backslash\{w\in C_{t-1}:deg_{G[C_{t-1}]}(w)\gt deg_{G[C_{t-1}]}(v_t)\}$;
Return $F_1,\dots,F_{|I|}$ and $C_1,\dots,C_{|I|}$.
在接下来的证明中，我们记Algorithm 1每一步得到的fingerprints为$F_1,F_2,\dots,F_{|I|}$以及对应的containers为$C_1,C_2,\dots,C_{|I|}$。用记号$F_t$和$C_t$分别表示$I$的$t-th$ fingerprint和$t-th$ container。
(待更新…)