超立方体幂图最大独立集的一个注记

A Note on the Maximum Independent Set of the Power of Hypercubes

摘要: 编码理论中的一个基本问题是求最小Hamming距离为d的最大n长二元码集的大小，即求超立方体d-1次幂的最大独立集。本文运用构造超立方体d-1次幂最大独立集的方法得到几类特殊的A(n,d)的值：对于，如果，则A(n,d)=2；如果，则A(n,d)=4；如果n=3k，，且，则A(n,d)=4。

Abstract: A basic problem in coding theory is to find the size of the maximum n-length binary code with the minimum Hamming distance d. That can be regarded as the size of the maximum independent set of the (d−1)^th power of n-dimensional hypercube. In this paper, we use the method of constructing the maximum independent set of the (d−1)^th power of n-dimensional hypercube to obtain several values of A(n,d) for some special n and d: For , if , then A(n,d)=2; if , then A(n,d)=4; if n=3k, , and , then A(n,d)=4.

1. 引言

1.1. 背景介绍

随着通信技术的不断发展，现代通信系统的复杂化以及通信业务的多样化要求系统能够实现高速、实时和可靠数据传输，由于用户对通信质量的要求不断提高，使得对高数据率数字通信等领域所采用的编码技术的要求也越来越高。经研究发现编码理论和图论之间存在联系，可通过使用图论的方法研究其边界。

1.2. 相关工作

n维二元向量空间 $Z_2^n=Z_2\times Z_2\times \cdots \times Z_2$，可以将 $Z_2^n$ 中的n维二元向量看作是n长二元码字。一些码字构成的集合称为码集。给定一个码集M，用 $\left|M\right|$ 表示码集M中码字的个数。1950年，Hamming [1] 定义两个码字 $x,y$ 间的Hamming距离为其不同码元的位数，记为 $d_H\left(x,y\right)$，即 $d_H\left(x,y\right)={\displaystyle {\sum }_{i=1}^n\left|x_i-y_i\right|}$， $i\in \left[1,n\right]$。

如文献 [2] 中所述， $A\left(n,d\right)$ 为最小Hamming距离为d的最大n长二元码集M的大小，即 $A\left(n,d\right)=\max \left\{\left|M\right|:M是n长二元码集,且任意x,y\in M,有d_H\left(x,y\right)\ge d\right\}$。求 $A\left(n,d\right)$ 的值是编码理论中的一个基本问题，这个问题极其困难，迄今为止还没有被完全解决。

1950年，Hamming [1] 首次对二元纠错码集进行了研究，通过构造几何模型的方法得出了

$A\left(n,d\right)\le \frac{2^n}{{{\displaystyle \sum }}_{i=1}^{\lfloor \frac{d-1}{2}\rfloor }\left(\begin{array}{c}n\\ i\end{array}\right)}$，这个上界就是著名的Hamming界。此后，许多学者对Hamming界进行研究，具

体可参阅 [3] [4] [5]。在1962年，Johnson [3] 在Hamming的研究基础上对 $A\left(n,d\right)$ 的值进行了优化，给出

了一个更为精确的上界，即 $A\left(n,2\delta +1\right)\le \frac{2^n}{{{\displaystyle \sum }}_{i=0}^{\delta }\left(\begin{array}{c}n\\ i\end{array}\right)+\frac{\left(\begin{array}{c}n\\ \delta +1\end{array}\right)-\left(\begin{array}{c}2\delta +1\\ \delta \end{array}\right)A\left(n,2\delta +2,2\delta +1\right)}{A\left(n+1,2\delta +2,\delta +1\right)}}$。2002年，Mounits等 [6] 继续改进 $A\left(n,d\right)$ 的值，得到 $A\left(n,2\delta +1\right)\le \frac{2^n}{{{\displaystyle \sum }}_{i=0}^{\delta }\left(\begin{array}{c}n\\ i\end{array}\right)+\frac{\left(\begin{array}{c}n+1\\ \delta +2\end{array}\right)-\left(\begin{array}{c}2\delta +2\\ \delta +2\end{array}\right)A\left(n+1,2\delta +2,2\delta +2\right)}{A\left(n+1,2\delta +2,\delta +2\right)}}$。

Gilbert-Varshamov界是1952年Gilbert [7] 提出的关于 $A\left(n,d\right)$ 的一个著名下界，即 $A\left(n,d\right)\ge \frac{2^n}{{{\displaystyle \sum }}_{i=1}^{d-1}\left(\begin{array}{c}n\\ i\end{array}\right)}$。此后，研究人员对于此下界进行了改进，具体内容可参阅 [8] - [15]。其中，Jiang和Vardy [12] 改进的Gilbert- Varshamov界是目前已知的最好下界，即 $A\left(n,d\right)\ge c\frac{2^n}{{{\displaystyle \sum }}_{i=1}^{d-1}\left(\begin{array}{c}n\\ i\end{array}\right)}{\log }_2\left({{\displaystyle \sum }}_{i=1}^{d-1}\left(\begin{array}{c}n\\ i\end{array}\right)\right)$，其中c为正常数，且 $\frac{d}{n}\le 0.499$。

到目前为止，有不少研究都致力于求 $A\left(n,d\right)$ 确切的值，虽然取得了极大的进展，但是迄今为止还没有统一的计算方法可以求出 $A\left(n,d\right)$ 的值。人们便将注意力转为求对于满足特定条件下的 $A\left(n,d\right)$ 的值。2001年，Vardy等人 [16] 得到了对于 $n,d$ 取特定值时 $A\left(n,d\right)$ 的界： $A\left(21,4\right)\le 43689$， $A\left(22,4\right)\le 87378$，

$A\left(22,6\right)\le 6941$， $A\left(23,4\right)\le 173491$。2002年，Mounits等人 [6] 给出了 $A\left(n,3\right)$ 的界：若 $n\equiv 10\left(\mathrm{mod}12\right)$，

则 $A\left(n,3\right)\le \frac{2^n}{n+2+\frac{8}{n+3}}$。

1.3. 本文贡献

本文对满足最小Hamming距离为d的最大n长二元码集M的大小进行研究，利用构造超立方体 $d-1$ 次幂最大独立集的方法得出几类特殊的 $A\left(n,d\right)$ 的值：对于 $n,d,k\in Z^{+}$，如果 $\frac{2n+1}{3}\le d\le n$，则 $A\left(n,d\right)=2$ ；如果 $\frac{2n-1}{3}\le d\le \frac{2n}{3}$，则 $A\left(n,d\right)=4$ ；如果 $n=3k,d=\frac{2n-3}{3}$，且 $k\ge 4$，则 $A\left(n,d\right)=4$。

2. 预备知识

本节给出了本文需要的一些基本概念和符号。

令 $G=\left(V\left(G\right),E\left(G\right)\right)$ 为简单无向图，其中 $V\left(G\right)$ 是图G的顶点集， $E\left(G\right)$ 是图G的边集。令M是 $V\left(G\right)$ 的一个子集，若M中任意两个顶点在图G中均不相邻，则称M为图G的独立集。若图G中不包含满足 $\left|M^{*}\right|>\left|M\right|$ 的独立集 $M^{*}$，则称M为图G的最大独立集。图G的最大独立集的顶点数称为图G的独立数，记为 $\alpha \left(G\right)$。

定义2.1：图 $Q_n$ 表示n维超立方体图，其顶点集 $V\left(Q_n\right)=\left\{x|x\in Z_2^n\right\}$，且对于任意的 $x,y\in V\left(Q_n\right)$，有边 $x~y$ 当且仅当 $d_H\left(x,y\right)=1$。

定义2.2：图 $Q_n^d$ 表示n维超立方体 $Q_n$ 的d次幂图，其顶点集 $V\left(Q_n^d\right)=\left\{x|x\in Z_2^n\right\}$，且对于任意的 $x,y\in V\left(Q_n^d\right)$，有边 $x~y$ 当且仅当 $d_H\left(x,y\right)\le d$。

定义2.3： $G=\left(V\left(G\right),E\left(G\right)\right)$ 为简单无向图，若对于任意的 $x,y\in G$，存在 $\phi \in \text{Aut}\left(G\right)$ 满足 $\phi \left(x\right)=y$，则称图G为点传递图。

定义2.4：给出两个n长二元码字 $x=\left(x_1,x_2,\cdots ,x_n\right)$， $y=\left(y_1,y_2,\cdots ,y_n\right)$，定义 $x\cap y=\left\{i|x_i=y_i=1,1\le i\le n\right\}$。

3. 主要结论及其证明

由定义可得 $A\left(n,d\right)=\alpha \left(Q_n^{d-1}\right)$，即n维超立方体的 $d-1$ 次幂图的独立数等于给定最小Hamming距离为d的最大n长二元码集的大小。由定义2.3可得 $Q_n^{d-1}$ 是点传递图，所以我们利用 $Q_n^{d-1}$ 的最大独立集证明下面定理时，只构造包含点 $\left(0,0,\cdots ,0\right)$ 的最大独立集。令 $u_0=\left(0,0,\cdots ,0\right)$， $D_i\left(u_0\right)=\left\{u\in V\left(Q_n^{d-1}\right)|d_H\left(u,u_0\right)\le i\right\}\left(0\le i\le n\right)$。为便于观察，给出如下对 $Q_n^{d-1}$ 的距离划分(见图1)。

Figure 1. The distance division graph of $Q_n^{d-1}$

图1. $Q_n^{d-1}$ 的距离划分图

定理3.1：对于 $n,d\in Z^{+}$，如果 $\frac{2n+1}{3}\le d\le n$，则 $A\left(n,d\right)=2$。

证明：因为 $A\left(n,d\right)=\alpha \left(Q_n^{d-1}\right)$，我们只需证明在题目所给条件下 $\alpha \left(Q_n^{d-1}\right)=2$ 成立即可。现令 $T_1=D_0\cup D_1\cup \cdots \cup D_{d-1}$， $T_2=D_d\cup D_{d+1}\cup \cdots \cup D_n$，则 $V\left(Q_n^{d-1}\right)=T_1\cup T_2$ (见图2)。不妨设 $M\subseteq V\left(Q_n^{d-1}\right)$，且M是 $Q_n^{d-1}$ 的独立集。令 $u_0\in M$，则对于 $T_1$ 中任意一点x， $x\ne u_0$，有 $d_H\left(x,u_0\right)\le d-1$，故 $M\cap T_1=\left\{u_0\right\}$。又因为对于 $T_2$ 中任意一点u有 $d_H\left(u,u_0\right)\ge d>d-1$，且对于 $T_2$ 中任意两点 $x,y$ 有 $d_H\left(x,y\right)\le 2\left(n-d\right)\le d-1$，故 $\left|M\cap T_2\right|\le 1$。综上有 $\alpha \left(Q_n^{d-1}\right)=2$，即 $A\left(n,d\right)=2$。

Figure 2. The distance division graph of Theorem 3.1

图2. 定理3.1的距离划分图

定理3.2：对于 $n,d\in Z^{+}$，如果 $\frac{2n-1}{3}\le d\le \frac{2n}{3}$，则 $A\left(n,d\right)=4$。

证明：与定理3.1的证明同理，我们只需证明在题目所给条件下 $\alpha \left(Q_n^{d-1}\right)=4$ 成立即可。现令 $T_1=D_0\cup D_1\cup \cdots \cup D_{d-1}$， $T_2=D_d$， $T_3=D_{d+1}\cup D_{d+2}\cup \cdots \cup D_n$，则 $V\left(Q_n^{d-1}\right)=T_1\cup T_2\cup T_3$ (见图3)。不妨设 $M\subseteq V\left(Q_n^{d-1}\right)$，且M是 $Q_n^{d-1}$ 的独立集。令 $u_0\in M$，则对于 $T_1$ 中任意一点x， $x\ne u_0$，有 $d_H\left(x,u_0\right)\le d-1$，故 $M\cap T_1=\left\{u_0\right\}$。又因为对于 $T_3$ 中任意一点u有 $d_H\left(u,u_0\right)\ge d+1>d-1$，且对于 $T_3$ 中任意两点 $x,y$ 有 $d_H\left(x,y\right)\le 2\left(n-d-1\right)=d-1$，故可得 $\left|M\cap T_3\right|\le 1$。

对于任意的 $u,v\in M\cap T_2$，设 $\left|u\cap v\right|=k$，则 $d_H\left(u,v\right)=2\left(d-k\right)\ge d$，故 $k\le \frac{d}{2}$。又因为 $T_2=D_d$，所以 $n-d\ge d-k$，故 $k\ge 2d-n\ge \frac{d-1}{2}$。综上，我们有 $\frac{d-1}{2}\le k\le \frac{d}{2}$。

Figure 3. The distance division graph of Theorem 3.2

图3. 定理3.2的距离划分图

1) 若d为偶数，则有 $k=\frac{d}{2},n=\frac{3d}{2}$。

不妨设点 $u\in M\cap T_2$，且点u满足 $u_1=u_2=\cdots =u_d=1$， $u_{d+1}=u_{d+2}=\cdots =u_n=0$。对于任意的

$v\in M\cap T_2-\left\{u\right\}$，因为 $\left|u\cap v\right|=\frac{d}{2}$，故点v满足 $v_{d+1}=v_{d+2}=\cdots =v_n=1$，且其前d个坐标有 $\frac{d}{2}$ 个为1，不妨设 $v_1=v_2=\cdots =v_{\frac{d}{2}}=1$， $v_{\frac{d+2}{2}}=v_{\frac{d+4}{2}}=\cdots =v_d=0$。此时，存在 $w\in M\cap T_2-\left\{u,v\right\}$，有 $w_1=w_2=\cdots =w_{\frac{d}{2}}=0$， $w_{\frac{d+2}{2}}=w_{\frac{d+4}{2}}=\cdots =w_n=1$，且 $M\cap T_2-\left\{u,v\right\}=\left\{w\right\}$，否则若 $m\in M\cap T_2-\left\{u,v,w\right\}$，则有

$m_{d+1}=m_{d+2}=\cdots =m_n=1$，故存在 $x\in M\cap T_2$，有 $d_H\left(x,m\right)\le d-1$。即若d为偶数，有 $4\le Q_n^{d-1}\le 5$。下面证明 $\alpha \left(Q_n^{d-1}\right)\ne 5$。如果 $\alpha \left(Q_n^{d-1}\right)=5$，且M是对应的最大独立集，则有 $M\cap T_1=\left\{u_0\right\}$， $\left|M\cap T_2\right|=3$， $\left|M\cap T_3\right|=1$。此时一定存在 $u\in M\cap T_2$， $v\in M\cap T_3$ 满足 $d_H\left(u,v\right)<d$，与M是独立集矛盾，故 $\alpha \left(Q_n^{d-1}\right)\ne 5$。

2) 若d为奇数，则有 $k=\frac{d-1}{2},n=\frac{3d+1}{2}$。

设点 $u\in M\cap T_2$，且点u满足 $u_1=u_2=\cdots =u_d=1$， $u_{d+1}=u_{d+2}=\cdots =u_n=0$。对于任意的

$v\in M\cap T_2-\left\{u\right\}$，由于 $\left|u\cap v\right|=\frac{d-1}{2}$，则点v中有 $v_{d+1}=v_{d+2}=\cdots =v_n=1$，且其前d个坐标有 $\frac{d-1}{2}$ 个为1，不妨设 $v_1=v_2=\cdots =v_{\frac{d-1}{2}}=1$, $v_{\frac{d+1}{2}}=v_{\frac{d+3}{2}}=\cdots =v_d=0$。若存在 $w\in M\cap T_2-\left\{u,v\right\}$，则有 $w_{d+1}=w_{d+2}=\cdots =w_n=1$，此时， $\left|w\cap v\right|\ge \frac{d+1}{2}$，与 $k=\frac{d-1}{2}$ 矛盾。故有 $\left|M\cap T_2\right|\le 2$，从而 $\left|M\right|\le 4$。

综上可得 $\alpha \left(Q_n^{d-1}\right)=4$，即 $A\left(n,d\right)=4$。

如果 $n=3k$，则 $d=\frac{2n-3}{3}=2k-1$，对于 $k\in \left\{1,2,3\right\}$ 已知其对应的 $A\left(n,d\right)$ 的值，即 $A\left(3,1\right)=8$，

$A\left(6,3\right)=8$， $A\left(9,5\right)=6$，对于大于3的正整数k，我们给出如下定理。

定理3.3：如果 $n=3k\left(k>3\right)$，且 $d=\frac{2n-3}{3}$，则 $A\left(n,d\right)=4$。

证明：与定理3.1的证明同理，我们只需证明在题目所给条件下 $\alpha \left(Q_n^{d-1}\right)=4$ 成立即可。现令 $T_1=D_0\cup D_1\cup \cdots \cup D_{d-1}$， $T_2=D_d\cup D_{d+1}$， $T_3=D_{d+2}\cup D_{d+3}\cup \cdots \cup D_n$，则 $V\left(Q_n^{d-1}\right)=T_1\cup T_2\cup T_3$ (见图4)。不妨设 $M\subseteq V\left(Q_n^{d-1}\right)$，且M是 $Q_n^{d-1}$ 的独立集。令 $u_0\in M$，则对于 $T_1$ 中任意一点x， $x\ne u_0$，有 $d_H\left(x,u_0\right)\le d-1$，故 $M\cap T_1=\left\{u_0\right\}$。又因为对于 $T_3$ 中任意一点u有 $d_H\left(u,u_0\right)\ge d+2>d-1$，且对于 $T_3$ 中任意两点 $x,y$ 有 $d_H\left(x,y\right)\le 2\left(n-d-2\right)=d-1$，故 $\left|M\cap T_3\right|\le 1$。接下来我们证明 $\left|M\cap T_2\right|\le 3$。由于 $T_2=D_d\cup D_{d+1}$，故我们讨论 $\left|M\cap D_d\right|$ 和 $\left|M\cap D_{d+1}\right|$ 的大小：

1) $\left|M\cap D_d\right|\le 3$。

Figure 4. The distance division graph of Theorem 3.3

图4. 定理3.3的距离划分图

对于任意的 $u,v\in M\cap D_d$，设 $\left|u\cap v\right|=k$，则 $d_H\left(u,v\right)=2\left(d-k\right)\ge d$， $k\le \frac{d}{2}$。又由 $n-d\ge d-k$ 可得 $k\ge 2d-n=\frac{d-3}{2}$。则有 $\frac{d-3}{2}\le k\le \frac{d}{2}$，即 $k=\frac{d-3}{2}$ 或 $k=\frac{d-1}{2}$。不妨设点 $u\in M\cap D_d$，且点u满足 $u_1=u_2=\cdots =u_d=1$， $u_{d+1}=u_{d+2}=\cdots =u_n=0$。对于任意的 $v\in M\cap D_d-\left\{u\right\}$， $\left|u\cap v\right|=\frac{d-3}{2}$ 或 $\frac{d-1}{2}$。若 $\left|u\cap v\right|=\frac{d-1}{2}$，设点v满足 $v_1=v_2=\cdots =v_{\frac{d-1}{2}}=1$， $v_{\frac{d+1}{2}}=v_{\frac{d+3}{2}}=\cdots =v_{d+1}=0$， $v_{d+2}=v_{d+3}=\cdots =v_n=1$。此时，对于任意的 $w\in M\cap D_d-\left\{u,v\right\}$，有 $\left|w\cap u\right|=\frac{d-1}{2}$。否则如果 $\left|w\cap u\right|=\frac{d-3}{2}$，则w一定满足

$w_{d+1}=w_{d+2}=\cdots =w_n=1$，从而 $\left|w\cap v\right|=\frac{d+1}{2}$。同理，若 $\left|v\cap u\right|=\frac{d-3}{2}$，则 $M\cap D_d-\left\{u,v\right\}=\varnothing$。由于 $\left|w\cap u\right|=\frac{d-1}{2}$，故此时w一定满足在其后 $n-d$ 个坐标中有 $\frac{d+1}{2}$ 个坐标为1。又因为 $\left|w\cap v\right|\ne \frac{d+1}{2}$，故 $w_{d+1}=1$， $w_1=w_2=\cdots =w_{\frac{d-1}{2}}=0$。又因为 $k\ge 4$，所以 $\frac{d-1}{2}\ge 3$，从而 $\left|M\cap D_d-\left\{u,v\right\}\right|\le 1$。即 $\left|M\cap D_{d+1}\right|\le 3$，

可令w为 $w_1=w_2=\cdots =w_{\frac{d+1}{2}}=0$， $w_{\frac{d+3}{2}}=w_{\frac{d+5}{2}}=\cdots =w_{n-1}=1$， $w_n=0$。

2) $\left|M\cap D_{d+1}\right|\le 3$。

对于任意的 $u,v\in M\cap D_{d+1}$，设 $\left|u\cap v\right|=k$，与(1)同理可得 $k=\frac{d+1}{2}$，且 $\left|M\cap D_{d+1}\right|\le 3$。当 $\left|M\cap D_{d+1}\right|=3$

时，可设 $M\cap D_{d+1}=\left\{x,y,z\right\}$，其中

$\begin{array}{l}x=\left(\underset{\frac{d+1}{2}}{\underset{︸}{1\cdots 1}}\underset{\frac{d+1}{2}}{\underset{︸}{1\cdots 1}}\underset{\frac{d+1}{2}}{\underset{︸}{0\cdots 0}}\right)\\ y=\left(\underset{\frac{d+1}{2}}{\underset{︸}{1\cdots 1}}\underset{\frac{d+1}{2}}{\underset{︸}{0\cdots 0}}\underset{\frac{d+1}{2}}{\underset{︸}{1\cdots 1}}\right)\\ z=\left(\underset{\frac{d+1}{2}}{\underset{︸}{0\cdots 0}}\underset{\frac{d+1}{2}}{\underset{︸}{1\cdots 1}}\underset{\frac{d+1}{2}}{\underset{︸}{1\cdots 1}}\right)\end{array}$

在此基础上，我们有 $M\cap D_d$ 与 $M\cap D_{d+1}$ 的关系：如果 $\left|M\cap D_d\right|=3$，则 $M\cap D_{d+1}=\varnothing$ ；如果 $\left|M\cap D_d\right|=2$，则 $\left|M\cap D_{d+1}\right|\le 1$ ；如果 $\left|M\cap D_d\right|=1$，则 $\left|M\cap D_{d+1}\right|\le 2$。否则一定会存在 $u\in M\cap D_d$， $v\in M\cap D_{d+1}$ 使得 $d_H\left(u,v\right)<d$。同理，如果 $\left|M\cap D_{d+1}\right|=3$，则 $M\cap D_d=\varnothing$ ；如果 $\left|M\cap D_{d+1}\right|=2$，则 $\left|M\cap D_d\right|\le 1$ ；如果 $\left|M\cap D_{d+1}\right|=1$，则 $\left|M\cap D_d\right|\le 2$。综上， $\left|M\cap T_2\right|\le 3$， $4\le \left|M\right|\le 5$，故 $4\le \alpha \left(Q_n^{d-1}\right)\le 5$。

下面我们证明 $\alpha \left(Q_n^{d-1}\right)\ne 5$。如果 $\alpha \left(Q_n^{d-1}\right)=5$，且M是对应的最大独立集，则根据上述分析有 $M\cap T_1=\left\{u_0\right\}$， $\left|M\cap T_2\right|\le 3$， $\left|M\cap T_3\right|=1$。此时一定存在 $u\in M\cap T_2$， $v\in M\cap T_3$ 满足 $d_H\left(u,v\right)<d$，与M是独立集矛盾，故 $\alpha \left(Q_n^{d-1}\right)\ne 5$。

综上， $\alpha \left(Q_n^{d-1}\right)=4$，即 $A\left(n,d\right)=4$。

4. 结语

本文将 $A\left(n,d\right)$ 看作是n维超立方体 $d-1$ 次幂的最大独立集的大小，通过构造其最大独立集的方法得

到了几类特殊的 $A\left(n,d\right)$ 的值：对于 $n,d,k\in Z^{+}$，如果 $\frac{2n+1}{3}\le d\le n$，则 $A\left(n,d\right)=2$ ；如果 $\frac{2n-1}{3}\le d\le \frac{2n}{3}$，则 $A\left(n,d\right)=4$ ；如果 $n=3k,d=\frac{2n-3}{3}$，且 $k\ge 4$，则 $A\left(n,d\right)=4$。

基金项目

国家自然科学基金资助项目(11671296)。

NOTES

^*通讯作者。