Independent set&its applications in coding theory

在图论中，独立集是一类非常重要的研究对象。本文将分为理论与应用两个部分，第一部分中会介绍一些独立集相关的概念与基础理论，对于几个经典的结果，我希望能给出易于接受的证明。第二部分我将介绍编码理论中的基本问题，即纠错码的最大码字个数的估计，通过建立其与图论中最大独立集数的关系，使得我们可以从图论的观点去看待编码理论的问题，并且我将通过一些例子说明图论方法的优越性。

一. 独立集简介

首先我们简单介绍一下独立集，极大独立集，最大独立集的概念。

Definition 1.1：对于一个图 $G(V,E)$ ,称 $V$ 的一个子集 $S$ 为图 $G$ 的独立集，当 $S$ 中的任意两个点在图 $G$ 中均不连边。进一步地，称 $G$ 的独立集 $S$ 是极大的(maximal)，当向 $S$ 中再加入任何一个点得到 $\hat{S}$ ， $\hat{S}$ 均不再是图 $G$ 的独立集。 $G$ 的最大独立集是指，对给定的图 $G$ ，包含点数最多的独立集，一般地，我们称最大独立集包含的点数为最大独立集数，一般记作 $\alpha(G)$ .

对于一个给定的图，寻找它的最大独立集数是一个NP-hard的问题，意味着几乎不可能有一个有效快速的算法输出一个给定图的最大独立集数。我们今天主要关心的就是最大独立集数 $\alpha(G)$ 的估计问题，比如通过一些图的已知条件，给出一些关于 $\alpha(G)$ 的界等。

其他常用概念和符号：

图中点 $v$ 的度数(degree)为点 $v$ 的邻点数目，一般记作 $deg(v)$ 或 $d_{v}$ .；
若图 $G$ 的每个点的度数均相等，则称图 $G$ 是正则的(regular)；
H-free 图：指禁掉某种子结构H的图，如triangle-free，是指图中不存在3个点互相连边的结构；
$N(v)$ 常表示点 $v$ 的邻点集合，有时为了具体表明在某个图中的邻点，会加一个角标，如 $N_{G}(v)$ ;
图 $G=(V,E)$ 的诱导子图(induced subgraph) $G[S]$ ，其点集为 $V$ 的子集 $S$ ，而边集为 $E$ 中所有两个端点都在 $S$ 中的边构成的集合；

二. 概率方法与 $\alpha(G)$ 的下界估计

首先我们用概率方法给一个比较简单的下界刻画：

Theorem 2.1(Caro and Wei)：对于一个图 $G(V,E)$ ,记每个点的度数为 $d_{v}$ ,则有

$\alpha(G)\geqslant\sum\limits_{v\in V}\frac{1}{d_{v}+1}.\$

proof : 定义某种序关系，用 $<$ 表示。我们从 $|V|$ 个点的按 $<$ 关系的所有排序中均匀选择其中一种，定义如下集合

$I=\{v\in V: \{v,w\}\in E \Rightarrow v<w \}.\$

即集合 $I$ 中的点 $v$ ，是他所有邻点中序关系最小的点。我们再令 $X_{v}$ 为表示 $v\in I$ 的随机示性变量（即若 $v\in I$ ，则 $X_{v}=1$ ，否则为0），再令 $X=\sum X_{v}=|I|$ . 由于 $v\in I$ 当且仅当 $v$ 是他所有邻点中序关系最小的点，那么对于每个 $v\in V$ , $X_{v}$ 的期望为

$E[X_{v}]=Pr(v\in I)=\frac{1}{d_{v}+1}\$ .

所以，由于期望的线性性，我们有

$E[X]=\sum\limits_{v\in V}\frac{1}{d_{v}+1}\$ .

那么假如 $I$ 中的有两个点 $x,y$ ,他们之间连边，那么会导致 $x<y,y<x$ ,这显然是矛盾的。因此 $I$ 一定是一个独立集，并且由于 $|I|$ 的期望已知，则存在点数大于等于期望值的独立集，因此有 $\alpha(G)\geqslant \sum\limits_{v\in V}\frac{1}{d_{v}+1}.$ 证毕。 $\square$

Corollary 2.2： 若图 $G$ 是一个 $n$ 个点的正则图，则 $\alpha(G)\geqslant \frac{n}{d+1}$ .
Corollary 2.3： 若图 $G$ 的最大度数不超过 $d$ ，则 $\alpha(G)\geqslant \frac{n}{d+1}$ .

以上的下界估计大概是1940年前后做的，也是概率方法应用早期的一个非常好的例子，随后在1980年前后，Ajtai，Komlos,Szemeredi [1]在研究著名的Ramsey问题(特别是R(3,k))时，发现如果一个图是triangle-free的，那么它的最大独立集数可以在Corollary 2.3的基础上有所改进！

Throrem 2.4(Ajtai. et al). 令 $G=(V,E)$ 是 $n$ 个点且不含有三角形(triangle-free)的图，若它的最大度数不超过 $d$ ，则有 $\alpha(G)\geqslant \frac{n\log_{2}d}{8d}$ .

而1980年文献[1]中的原始证明被称为概率组合中最重要的证明方法之一，并且推进了semi-random method的发展。限于篇幅，在这里我介绍我比较喜欢的一套证明。

proof：令 $X$ 为图 $G$ 中所有独立集组成的集合，显然 $X$ 是非空的，从 $X$ 中均匀随机抽取一个独立集出来，要证明Theorem 2.4，只需要证明 $E[I]\geqslant \frac{n\log_{2}d}{8d}$ 即可。

对每个 $V$ 中的点 $v$ ，考虑如下随机变量

$Y_{v}:=d|I\cap \{v\}|+|N(v)\cap I|\$ ,

其中 $N(v)$ 是点 $v$ 的邻点集。因为 $I$ 是个独立集，因此若 $v\in I$ ，那么 $Y_{v}=d$ ,否则， $Y_{v}=|\{w\in I : \{v,w\}\in E\}|$ 。又因此已知图 $G$ 中每个点的最大度数为 $d$ ，那么对于 $I$ 中的点 $w$ ，那么由简单的计数可以得到：

$\sum\limits_{v\in V}Y_{v}\leqslant 2d|I|.\$

在上式两边同取期望，结合期望的线性性，可以得到：

$E[|I|]\geqslant \frac{1}{2d}\sum\limits_{v\in V}E[Y_{v}].\$

那么要证明 $E[I]\geqslant \frac{n\log_{2}d}{8d}$ ，我们只需证明，对所有 $v\in V$ , $E[Y_{v}]\geqslant\frac{\log_{2}d}{4}$ 均成立。

现固定 $v\in V,$ 考虑 $G=(V,E)$ 的诱导子图 $G'(V',E')$ ,其中 $V'=V\setminus\{N(v)\cup\{v\}\}.$ 显然 $I\cap V'$ 也是 $V'$ 的独立集，接下去我们建立一个条件概率关系，那么欲证明 $E[Y_{v}]\geqslant\frac{\log_{2}d}{4}$ ，我们只需证对 $V'$ 中的所有独立集 $I’$ ，下面的条件期望关系成立：

$E(Y_{v}| I\cap V'=I')\geqslant \frac{\log_{2}d}{4}.\$

固定一个独立集 $I'$ ,令 $J\subseteq N(v)$ 为 $V$ 中满足与 $v$ 相邻，但不与 $I’$ 中任何点相邻的点的集合。因为 $G$ 是triangle-free的,因此 $J$ 是一个独立集。因此一旦 $I'$ 确定下来，我们就可以按照下面的方法构造独立集 $I$ ：向 $I'$ 中加点，要么加入点 $v$ ，要么加入 $J$ 的子集。我们不妨设 $|J|=m$ ，那么加点的方式有 $2^{m}+1$ 种，若将 $v$ 加入 $I’$ ，则由于 $v\in I$ ,从而 $Y_{v}=d.$ 若加入 $J$ 的某个子集 $J'$ ，那么 $Y_{v}=|J'|$ ,由于 $|J’|$ 的平均值为 $\frac{m}{2}$ ,且加入是等概率的，因此有

$E[Y_{v}|I\cap V'=I']=\frac{d}{2^{m}+1}+\frac{m}{2}\frac{2^{m}}{2^{m}+1}.\$

计算可得，当 $d\geqslant 16,m\geqslant 1$ 时， $\frac{d}{2^{m}+1}+\frac{m}{2}\frac{2^{m}}{2^{m}+1} \geqslant \frac{\log_{2}d}{4}.$ 证毕。 $\square$

我们发现,Theorem 2.4 是基于triangle-free的图的结论，似乎限制过强，那么如果适当放宽这方面的限制，是否可以有类似的结果呢？1985年，Bollobas在它的著作《Random Graph》中给出了当triangle数目较少时的结果。

Theorem 2.5(Bollobas,1985) 令图 $G=(V,E)$ 为 $n$ 个点的图，最大度数为 $d$ ，若图 $G$ 中至多含有 $T$ 个三角形，那么我们有：

$\alpha(G)\geqslant \frac{n}{10d}(\log_{2}d-\frac{1}{2}\log_{2}(\frac{T}{n})).\$

而后Vardy与Tao Jiang[2]通过观察sparse graph的一些性质，对Theorem 2.5做了更便于处理的刻画。

Theorem 2.6(Vardy, Tao Jiang,2004) 令图 $G=(V,E)$ 为 $n$ 个点的图，最大度数为 $d$ ，若对任何 $G$ 中的点 $v$ ，由 $v$ 的邻点生成的诱导子图的边数最多为 $P$ ，那么我们有

$\alpha(G)\geqslant \frac{n}{10d}(\log_{2}d-\frac{1}{2}\log_{2}(\frac{P}{3})).\$

Proof of Theorem 2.6: 注意到，对于 $G$ 中的点 $v$ ，由 $v$ 的邻点生成的诱导子图的边数等于包含点 $v$ 的三角形的数目。因此对于任何 $G$ 中的点 $v$ ，至多有 $P$ 个三角形包含点 $v$ 。把 $V(G)$ 的点都累加一边，那么每个三角形恰好会被数3次，那么 $G$ 中三角形的总数至多为 $\frac{nP}{3}$ ,代入Theorem 2.5即得Theorem 2.6的结果。 $\square$

至此，我们已经得到了一些关于 $\alpha(G)$ 下界的估计，接下去我们将简单介绍如何将极值图论中的这些结果，应用到编码理论中。

三.编码理论问题简介

限于篇幅，这里就不对整个编码理论的背景做太多叙述与铺垫，我将直接给出一些基本的概念与其中的数学问题，主要关注编码理论基本问题，即确定码长 $n$ 与极小距离 $d$ ，计算最大的码字个数 $\mathcal{C}(n,d)$ 。如对编码理论领域其他问题感兴趣，如编码的构造，编码译码算法的设计等，可参阅相关专业书籍。另外，本文中主要介绍 $q$ 元码与置换码，并且我们指的距离均为Hamming距离。

Definition 3.1 对于两个相等长度的序列，它们的Hamming距离是两个序列对应位置数码不同的个数。即若我们令 $A_{n}=\{a_{1},a_{2},\ldots,a_{n}\}, B_{n}=\{b_{1},b_{2},\ldots,b_{n}\}$ ,他们的Hamming距离定义为 $d_{H}(A_{n},B_{n})=|\{i |a_{i} \neq b_{i} , 1\leqslant i \leqslant n \}|$ .

本文中我们主要介绍q元码与置换码：

$q$ 元码：码字为 $0,1,2,\ldots,q-1$ 构成的 $n$ 长序列，是最经典的编码。
置换码：码字为置换群 $S_{n}$ 中的元素的向量表示，近年来由于在电力线传输，分布式存储，DNA存储等领域的广泛应用，使得置换码成为过去十余年研究的热点问题。

经典的编码理论中，我们常考虑3个参数，码长 $n$ ,码字个数 $M$ ，码的极小距离 $d$ 。称 $\mathcal{C}$ 为一个 ( $n,M,d$ )码，若任意 $C_{1},C_{2}\in \mathcal{C}$ 都有 $d_{H}(C_{1},C_{2}) \geqslant d$ .一般来说，我们认为好的码应该符合下面三个条件：

码长尽可能短，便于存储，传输等；
码字个数尽可能多，即希望一个码中具有的信息量更多；
极小距离尽可能大，即纠错性能尽可能好。（这里我们需要知道，一个极小距离 $2t+1$ 的码可以纠任意 $t$ 个位置的错误）。

但是以上三个目标其实是相互制约的，因此便有了如下问题：

编码理论基本问题: 给定码长 $n$ 和极小距离 $d$ ，求最大码字数 $\mathcal{C}(n,d)$ 。

至此已经我们可以把这个问题看作一个极值问题了，下面我们介绍关于 $\mathcal{C}(n,d)$ 最经典的下界

Theorem 3.2 (Gilbert-Varshamov bound)

$q$ 元码： $\mathcal{C}(n,d)\geqslant \frac{q^{n}}{\sum_{j=0}^{d-1}\binom{n}{j}(q-1)^{j}}$ 。
置换码： $\mathcal{C}(n,d)\geqslant \frac{n!}{\sum_{k=0}^{d-1}D_{k}\binom{n}{k}}$ ，其中 $D_{k}$ 为经典的置换中的错排数(Derangement)。

我们可以发现，这两个式子本质上都是： $\frac{全空间大小}{半径d-1的球的大小}$ 。我们可以给一个非常直观的解释，即用不相交的半径大小为 $d-1$ 的球填入整个空间，那么在每个球里面选取一个码字，这时候选出来的码字之间的距离必然是大于等于 $d$ 的。

关于这些编码的界，最新的结果可以参考

Andries E. Brouwer

四.图论模型与Gilbert-Varshamov bound的优化

下面就到了本文最核心的部分：如何利用图论中的独立集的知识，来优化编码理论基本问题中，经典的Gilbert-Varshamov bound。

图论模型：给定码长 $n$ 和极小距离 $d$ 后，考虑这样的图 $G=(V,E)$ ，其中点集 $V$ 为码的全空间，如对于 $q$ 元码， $|V|=q^{n}$ ,对于置换码，则 $|V|=n！$ , $V$ 中的两个点 $x,y\in V$ 在 $G$ 中连边，当且仅当他们的Hamming距离不超过 $d-1$ 。

此时，编码理论中的 $\mathcal{C}(n,d)$ 就可以等价成图 $G$ 的最大独立集数 $\alpha(G)$ ，那么我们是否可以用Theorem 2.5与2.6关于 $\alpha(G)$ 下界的估计，去优化Gilbert-Varshamov bound？

答案是肯定的，大约2000年前后，Tao Jiang与A.Vardy [2] 就注意到了这个想法，并且将它做到了二元码上，但是二元码的计算相对较为复杂，他们在优化的过程中还用到了一些规划的思想。2012年前后，Gao et al. [3] 将该想法应用到了置换码上，由于 $S_{n}$ 中元素具有一些vertex-transitive的性质，因此构造 $S_{n}$ 对应的图是正则的，因此他们选取了更便于计算的估计式，从而将原有置换码的Gilbert-Varshamov bound在渐近意义上改进了 $\Omega({\log{n}})$ 。

我们简单说明一下这套方法的核心思想与局限性。

首先我们知道对于置换码构造的图是正则的，并且我们可以发现每个点的度数 $\Delta$ ，恰好是半径为 $d-1$ 的球的大小减一（去掉球心），如此一来，我们可以得到Theorem2.6 中对 $\alpha(G)$ 的估计式与Gilbert-Varshamov bound的比值为 $\frac{\Delta+1}{10\Delta}(\log_{2}\Delta-\frac{1}{2}\log_{2}(\frac{P}{3}))$ ，那么我们只需要估计任何一个点(比如单位置换)所生成的induced subgraph中的边数即可（这句话看似轻松，实际上往往是解决问题最困难的一步），如果我们能得到 $\frac{\Delta}{\sqrt{\frac{P}{3}}}=\Omega(n^{c}), c>0$ ,我们就可以在渐近意义上，将Gilbert-Varshamov bound提高 $\Omega(\log{n})$ 倍。局限性其实也一目了然，就是这套方法在估计上只能提高形如 $\Omega(\log{n})$ 级别的倍数，并不能算太强的结果。

五.后续工作

关于第四章中置换码的工作，2016年前后，Jin[4], Wang et al.[5] 分别独立地用有理函数域与染色两种不同的方法，将置换码基于Hamming距离的Gilbert-Varshamov bound提高了 $n$ 倍。近一两年，也有不少关于该问题的工作在陆续跟进。

Reference

[1]M.Ajtai , J.Komlós, E.Szemerédi A note on Ramsey numbers[J]. Journal of Combinatorial Theory, 1980, 29(3):354-360.

[2] Jiang Tao , Vardy A . Asymptotic improvement of the Gilbert-Varshamov bound on the size of binary codes[M]. IEEE Press, 2004.

[3] F.Gao,, Y. Yang , and G. Ge . “An Improvement on the Gilbert–Varshamov Bound for Permutation Codes.”IEEE Transactions on Information Theory 59.5(2013):3059-3063.

[4] L.Jin. A Construction of Permutation Codes From Rational Function Fields and Improvement to the Gilbert–Varshamov Bound[J]. IEEE Transactions on Information Theory, 2016, 62(1):159-162.

[5] X.Wang , Y.Zhang , Y.Yang ,G.Ge. New bounds of permutation codes under Hamming metric and Kendall’s τ -metric[J]. Designs Codes and Cryptography, 2016, 85(3).

来源：知乎 www.zhihu.com

作者：Ivan

【知乎日报】千万用户的选择，做朋友圈里的新鲜事分享大牛。
点击下载