超立方体幂图最大独立集的一个注记 A Note on the Maximum Independent Set of the Power of Hypercubes

doi:10.12677/AAM.2021.101020

Advances in Applied Mathematics
Vol. 10 No. 01 ( 2021 ), Article ID: 39900 , 8 pages
10.12677/AAM.2021.101020

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

吕梦欣，寇永芳，胡晓敏，李玉瑛，杨卫华^*

●How to Cite this Article

太原理工大学数学学院，山西晋中

收稿日期：2020年12月19日；录用日期：2021年1月15日；发布日期：2021年1月21日

摘要

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

关键词

超立方体，最大独立集，编码理论，码距

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

Mengxin Lv, Yongfang Kou, Xiaomin Hu, Yuying Li, Weihua Yang^*

School of Mathematics, Taiyuan University of Technology, Jinzhong Shanxi

Received: Dec. 19^th, 2020; accepted: Jan. 15^th, 2021; published: Jan. 21^st, 2021

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 $n, d, k \in Z^{+}$ , if $\frac{2 n + 1}{3} \leq d \leq n$ , then $A (n, d) = 2$ ; if $\frac{2 n - 1}{3} \leq d \leq \frac{2 n}{3}$ , then $A (n, d) = 4$ ; if $n = 3 k$ , $d = \frac{2 n - 3}{3}$ , and $k \geq 4$ , then $A (n, d) = 4$ .

Keywords:Hypercube, Maximum Independent Set, Coding Theory, Code Distance

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

1.1. 背景介绍

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

1.2. 相关工作

n维二元向量空间 $Z_{2}^{n} = Z_{2} \times Z_{2} \times \dots \times Z_{2}$ ，可以将 $Z_{2}^{n}$ 中的n维二元向量看作是n长二元码字。一些码字构成的集合称为码集。给定一个码集M，用 $| M |$ 表示码集M中码字的个数。1950年，Hamming [1] 定义两个码字 $x, y$ 间的Hamming距离为其不同码元的位数，记为 $d_{H} (x, y)$ ，即 $d_{H} (x, y) = \sum_{i = 1}^{n} | x_{i} - y_{i} |$ ， $i \in [1, n]$ 。

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

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

$A (n, d) \leq \frac{2^{n}}{\sum_{i = 1}^{⌊ \frac{d - 1}{2} ⌋} (\begin{matrix} n \\ i \end{matrix})}$ ，这个上界就是著名的Hamming界。此后，许多学者对Hamming界进行研究，具

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

了一个更为精确的上界，即 $A (n, 2 δ + 1) \leq \frac{2^{n}}{\sum_{i = 0}^{δ} (\begin{matrix} n \\ i \end{matrix}) + \frac{(\begin{matrix} n \\ δ + 1 \end{matrix}) - (\begin{matrix} 2 δ + 1 \\ δ \end{matrix}) A (n, 2 δ + 2, 2 δ + 1)}{A (n + 1, 2 δ + 2, δ + 1)}}$ 。2002年，Mounits等 [6] 继续改进 $A (n, d)$ 的值，得到 $A (n, 2 δ + 1) \leq \frac{2^{n}}{\sum_{i = 0}^{δ} (\begin{matrix} n \\ i \end{matrix}) + \frac{(\begin{matrix} n + 1 \\ δ + 2 \end{matrix}) - (\begin{matrix} 2 δ + 2 \\ δ + 2 \end{matrix}) A (n + 1, 2 δ + 2, 2 δ + 2)}{A (n + 1, 2 δ + 2, δ + 2)}}$ 。

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

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

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

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

1.3. 本文贡献

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

2. 预备知识

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

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

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

定义2.2：图 $Q_{n}^{d}$ 表示n维超立方体 $Q_{n}$ 的d次幂图，其顶点集 $V (Q_{n}^{d}) = {x | x \in Z_{2}^{n}}$ ，且对于任意的 $x, y \in V (Q_{n}^{d})$ ，有边 $x ~ y$ 当且仅当 $d_{H} (x, y) \leq d$ 。

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

定义2.4：给出两个n长二元码字 $x = (x_{1}, x_{2}, \dots, x_{n})$ ， $y = (y_{1}, y_{2}, \dots, y_{n})$ ，定义 $x \cap y = {i | x_{i} = y_{i} = 1, 1 \leq i \leq n}$ 。

3. 主要结论及其证明

由定义可得 $A (n, d) = α (Q_{n}^{d - 1})$ ，即n维超立方体的 $d - 1$ 次幂图的独立数等于给定最小Hamming距离为d的最大n长二元码集的大小。由定义2.3可得 $Q_{n}^{d - 1}$ 是点传递图，所以我们利用 $Q_{n}^{d - 1}$ 的最大独立集证明下面定理时，只构造包含点 $(0, 0, \dots, 0)$ 的最大独立集。令 $u_{0} = (0, 0, \dots, 0)$ ， $D_{i} (u_{0}) = {u \in V (Q_{n}^{d - 1}) | d_{H} (u, u_{0}) \leq i} (0 \leq i \leq n)$ 。为便于观察，给出如下对 $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{2 n + 1}{3} \leq d \leq n$ ，则 $A (n, d) = 2$ 。

证明：因为 $A (n, d) = α (Q_{n}^{d - 1})$ ，我们只需证明在题目所给条件下 $α (Q_{n}^{d - 1}) = 2$ 成立即可。现令 $T_{1} = D_{0} \cup D_{1} \cup \dots \cup D_{d - 1}$ ， $T_{2} = D_{d} \cup D_{d + 1} \cup \dots \cup D_{n}$ ，则 $V (Q_{n}^{d - 1}) = T_{1} \cup T_{2}$ (见图2)。不妨设 $M \subseteq V (Q_{n}^{d - 1})$ ，且M是 $Q_{n}^{d - 1}$ 的独立集。令 $u_{0} \in M$ ，则对于 $T_{1}$ 中任意一点x， $x \neq u_{0}$ ，有 $d_{H} (x, u_{0}) \leq d - 1$ ，故 $M \cap T_{1} = {u_{0}}$ 。又因为对于 $T_{2}$ 中任意一点u有 $d_{H} (u, u_{0}) \geq d > d - 1$ ，且对于 $T_{2}$ 中任意两点 $x, y$ 有 $d_{H} (x, y) \leq 2 (n - d) \leq d - 1$ ，故 $| M \cap T_{2} | \leq 1$ 。综上有 $α (Q_{n}^{d - 1}) = 2$ ，即 $A (n, d) = 2$ 。

Figure 2. The distance division graph of Theorem 3.1

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

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

证明：与定理3.1的证明同理，我们只需证明在题目所给条件下 $α (Q_{n}^{d - 1}) = 4$ 成立即可。现令 $T_{1} = D_{0} \cup D_{1} \cup \dots \cup D_{d - 1}$ ， $T_{2} = D_{d}$ ， $T_{3} = D_{d + 1} \cup D_{d + 2} \cup \dots \cup D_{n}$ ，则 $V (Q_{n}^{d - 1}) = T_{1} \cup T_{2} \cup T_{3}$ (见图3)。不妨设 $M \subseteq V (Q_{n}^{d - 1})$ ，且M是 $Q_{n}^{d - 1}$ 的独立集。令 $u_{0} \in M$ ，则对于 $T_{1}$ 中任意一点x， $x \neq u_{0}$ ，有 $d_{H} (x, u_{0}) \leq d - 1$ ，故 $M \cap T_{1} = {u_{0}}$ 。又因为对于 $T_{3}$ 中任意一点u有 $d_{H} (u, u_{0}) \geq d + 1 > d - 1$ ，且对于 $T_{3}$ 中任意两点 $x, y$ 有 $d_{H} (x, y) \leq 2 (n - d - 1) = d - 1$ ，故可得 $| M \cap T_{3} | \leq 1$ 。

对于任意的 $u, v \in M \cap T_{2}$ ，设 $| u \cap v | = k$ ，则 $d_{H} (u, v) = 2 (d - k) \geq d$ ，故 $k \leq \frac{d}{2}$ 。又因为 $T_{2} = D_{d}$ ，所以 $n - d \geq d - k$ ，故 $k \geq 2 d - n \geq \frac{d - 1}{2}$ 。综上，我们有 $\frac{d - 1}{2} \leq k \leq \frac{d}{2}$ 。

Figure 3. The distance division graph of Theorem 3.2

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

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

不妨设点 $u \in M \cap T_{2}$ ，且点u满足 $u_{1} = u_{2} = \dots = u_{d} = 1$ ， $u_{d + 1} = u_{d + 2} = \dots = u_{n} = 0$ 。对于任意的

$v \in M \cap T_{2} - {u}$ ，因为 $| u \cap v | = \frac{d}{2}$ ，故点v满足 $v_{d + 1} = v_{d + 2} = \dots = v_{n} = 1$ ，且其前d个坐标有 $\frac{d}{2}$ 个为1，不妨设 $v_{1} = v_{2} = \dots = v_{\frac{d}{2}} = 1$ ， $v_{\frac{d + 2}{2}} = v_{\frac{d + 4}{2}} = \dots = v_{d} = 0$ 。此时，存在 $w \in M \cap T_{2} - {u, v}$ ，有 $w_{1} = w_{2} = \dots = w_{\frac{d}{2}} = 0$ ， $w_{\frac{d + 2}{2}} = w_{\frac{d + 4}{2}} = \dots = w_{n} = 1$ ，且 $M \cap T_{2} - {u, v} = {w}$ ，否则若 $m \in M \cap T_{2} - {u, v, w}$ ，则有

$m_{d + 1} = m_{d + 2} = \dots = m_{n} = 1$ ，故存在 $x \in M \cap T_{2}$ ，有 $d_{H} (x, m) \leq d - 1$ 。即若d为偶数，有 $4 \leq Q_{n}^{d - 1} \leq 5$ 。下面证明 $α (Q_{n}^{d - 1}) \neq 5$ 。如果 $α (Q_{n}^{d - 1}) = 5$ ，且M是对应的最大独立集，则有 $M \cap T_{1} = {u_{0}}$ ， $| M \cap T_{2} | = 3$ ， $| M \cap T_{3} | = 1$ 。此时一定存在 $u \in M \cap T_{2}$ ， $v \in M \cap T_{3}$ 满足 $d_{H} (u, v) < d$ ，与M是独立集矛盾，故 $α (Q_{n}^{d - 1}) \neq 5$ 。

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

设点 $u \in M \cap T_{2}$ ，且点u满足 $u_{1} = u_{2} = \dots = u_{d} = 1$ ， $u_{d + 1} = u_{d + 2} = \dots = u_{n} = 0$ 。对于任意的

$v \in M \cap T_{2} - {u}$ ，由于 $| u \cap v | = \frac{d - 1}{2}$ ，则点v中有 $v_{d + 1} = v_{d + 2} = \dots = v_{n} = 1$ ，且其前d个坐标有 $\frac{d - 1}{2}$ 个为1，不妨设 $v_{1} = v_{2} = \dots = v_{\frac{d - 1}{2}} = 1$ , $v_{\frac{d + 1}{2}} = v_{\frac{d + 3}{2}} = \dots = v_{d} = 0$ 。若存在 $w \in M \cap T_{2} - {u, v}$ ，则有 $w_{d + 1} = w_{d + 2} = \dots = w_{n} = 1$ ，此时， $| w \cap v | \geq \frac{d + 1}{2}$ ，与 $k = \frac{d - 1}{2}$ 矛盾。故有 $| M \cap T_{2} | \leq 2$ ，从而 $| M | \leq 4$ 。

综上可得 $α (Q_{n}^{d - 1}) = 4$ ，即 $A (n, d) = 4$ 。

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

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

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

证明：与定理3.1的证明同理，我们只需证明在题目所给条件下 $α (Q_{n}^{d - 1}) = 4$ 成立即可。现令 $T_{1} = D_{0} \cup D_{1} \cup \dots \cup D_{d - 1}$ ， $T_{2} = D_{d} \cup D_{d + 1}$ ， $T_{3} = D_{d + 2} \cup D_{d + 3} \cup \dots \cup D_{n}$ ，则 $V (Q_{n}^{d - 1}) = T_{1} \cup T_{2} \cup T_{3}$ (见图4)。不妨设 $M \subseteq V (Q_{n}^{d - 1})$ ，且M是 $Q_{n}^{d - 1}$ 的独立集。令 $u_{0} \in M$ ，则对于 $T_{1}$ 中任意一点x， $x \neq u_{0}$ ，有 $d_{H} (x, u_{0}) \leq d - 1$ ，故 $M \cap T_{1} = {u_{0}}$ 。又因为对于 $T_{3}$ 中任意一点u有 $d_{H} (u, u_{0}) \geq d + 2 > d - 1$ ，且对于 $T_{3}$ 中任意两点 $x, y$ 有 $d_{H} (x, y) \leq 2 (n - d - 2) = d - 1$ ，故 $| M \cap T_{3} | \leq 1$ 。接下来我们证明 $| M \cap T_{2} | \leq 3$ 。由于 $T_{2} = D_{d} \cup D_{d + 1}$ ，故我们讨论 $| M \cap D_{d} |$ 和 $| M \cap D_{d + 1} |$ 的大小：

1) $| M \cap D_{d} | \leq 3$ 。

Figure 4. The distance division graph of Theorem 3.3

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

对于任意的 $u, v \in M \cap D_{d}$ ，设 $| u \cap v | = k$ ，则 $d_{H} (u, v) = 2 (d - k) \geq d$ ， $k \leq \frac{d}{2}$ 。又由 $n - d \geq d - k$ 可得 $k \geq 2 d - n = \frac{d - 3}{2}$ 。则有 $\frac{d - 3}{2} \leq k \leq \frac{d}{2}$ ，即 $k = \frac{d - 3}{2}$ 或 $k = \frac{d - 1}{2}$ 。不妨设点 $u \in M \cap D_{d}$ ，且点u满足 $u_{1} = u_{2} = \dots = u_{d} = 1$ ， $u_{d + 1} = u_{d + 2} = \dots = u_{n} = 0$ 。对于任意的 $v \in M \cap D_{d} - {u}$ ， $| u \cap v | = \frac{d - 3}{2}$ 或 $\frac{d - 1}{2}$ 。若 $| u \cap v | = \frac{d - 1}{2}$ ，设点v满足 $v_{1} = v_{2} = \dots = v_{\frac{d - 1}{2}} = 1$ ， $v_{\frac{d + 1}{2}} = v_{\frac{d + 3}{2}} = \dots = v_{d + 1} = 0$ ， $v_{d + 2} = v_{d + 3} = \dots = v_{n} = 1$ 。此时，对于任意的 $w \in M \cap D_{d} - {u, v}$ ，有 $| w \cap u | = \frac{d - 1}{2}$ 。否则如果 $| w \cap u | = \frac{d - 3}{2}$ ，则w一定满足

$w_{d + 1} = w_{d + 2} = \dots = w_{n} = 1$ ，从而 $| w \cap v | = \frac{d + 1}{2}$ 。同理，若 $| v \cap u | = \frac{d - 3}{2}$ ，则 $M \cap D_{d} - {u, v} = \emptyset$ 。由于 $| w \cap u | = \frac{d - 1}{2}$ ，故此时w一定满足在其后 $n - d$ 个坐标中有 $\frac{d + 1}{2}$ 个坐标为1。又因为 $| w \cap v | \neq \frac{d + 1}{2}$ ，故 $w_{d + 1} = 1$ ， $w_{1} = w_{2} = \dots = w_{\frac{d - 1}{2}} = 0$ 。又因为 $k \geq 4$ ，所以 $\frac{d - 1}{2} \geq 3$ ，从而 $| M \cap D_{d} - {u, v} | \leq 1$ 。即 $| M \cap D_{d + 1} | \leq 3$ ，

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

2) $| M \cap D_{d + 1} | \leq 3$ 。

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

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

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

在此基础上，我们有 $M \cap D_{d}$ 与 $M \cap D_{d + 1}$ 的关系：如果 $| M \cap D_{d} | = 3$ ，则 $M \cap D_{d + 1} = \emptyset$ ；如果 $| M \cap D_{d} | = 2$ ，则 $| M \cap D_{d + 1} | \leq 1$ ；如果 $| M \cap D_{d} | = 1$ ，则 $| M \cap D_{d + 1} | \leq 2$ 。否则一定会存在 $u \in M \cap D_{d}$ ， $v \in M \cap D_{d + 1}$ 使得 $d_{H} (u, v) < d$ 。同理，如果 $| M \cap D_{d + 1} | = 3$ ，则 $M \cap D_{d} = \emptyset$ ；如果 $| M \cap D_{d + 1} | = 2$ ，则 $| M \cap D_{d} | \leq 1$ ；如果 $| M \cap D_{d + 1} | = 1$ ，则 $| M \cap D_{d} | \leq 2$ 。综上， $| M \cap T_{2} | \leq 3$ ， $4 \leq | M | \leq 5$ ，故 $4 \leq α (Q_{n}^{d - 1}) \leq 5$ 。

下面我们证明 $α (Q_{n}^{d - 1}) \neq 5$ 。如果 $α (Q_{n}^{d - 1}) = 5$ ，且M是对应的最大独立集，则根据上述分析有 $M \cap T_{1} = {u_{0}}$ ， $| M \cap T_{2} | \leq 3$ ， $| M \cap T_{3} | = 1$ 。此时一定存在 $u \in M \cap T_{2}$ ， $v \in M \cap T_{3}$ 满足 $d_{H} (u, v) < d$ ，与M是独立集矛盾，故 $α (Q_{n}^{d - 1}) \neq 5$ 。

综上， $α (Q_{n}^{d - 1}) = 4$ ，即 $A (n, d) = 4$ 。

4. 结语

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

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

基金项目

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

文章引用

吕梦欣,寇永芳,胡晓敏,李玉瑛,杨卫华. 超立方体幂图最大独立集的一个注记
A Note on the Maximum Independent Set of the Power of Hypercubes[J]. 应用数学进展, 2021, 10(01): 172-179. https://doi.org/10.12677/AAM.2021.101020

参考文献

1. Hamming, R.W. (1950) Error Detecting and Error Correcting Codes. Bell System Technical Journal, 29, 147-160. https://doi.org/10.1002/j.1538-7305.1950.tb00463.x

2. MacWilliams, F.J. and Sloane, N.J.A. (1977) The Theory of Error-Correcting Codes. North-Holland Mathematical Library. Elsevier, Amsterdam.

3. Johnson, S. (1962) A New Upper Bound for Error-Correcting Codes. IEEE Transactions on Information Theory, 8, 203-207. https://doi.org/10.1109/TIT.1962.1057714

4. Johnson, S.M. (1971) On Upper Bounds for Unrestricted Binary-Error-Correcting Codes. IEEE Transactions on Information Theory, 17, 466-478. https://doi.org/10.1109/TIT.1971.1054656

5. Wax, N. (1959) On Upper Bounds for Error Detecting and Error Correcting Codes of Finite Length. IEEE Transactions on Information Theory, 5, 168-174. https://doi.org/10.1109/TIT.1959.1057514

6. Mounits, B., Etzion, T. and Litsyn, S. (2002) Improved Upper Bounds on Sizes of Codes. IEEE Transactions on Information Theory, 48, 880-886. https://doi.org/10.1109/18.992776

7. Gilbert, E.N. (1952) A Comparison of Signalling Alphabets. Bell System Technical Journal, 31, 504-522. https://doi.org/10.1002/j.1538-7305.1952.tb01393.x

8. Barg, A., Guritman, S. and Simonis, J. (2000) Strengthening the Gilbert-Varshamov Bound. Linear Algebra and Its Applications, 307, 119-129. https://doi.org/10.1016/S0024-3795(99)00271-2

9. Elia, M. (1983) Some Results on the Existence of Binary Linear Codes. IEEE Transactions on Information Theory, 29, 933-934. https://doi.org/10.1109/TIT.1983.1056743

10. Fabris, F. (2001) Sharpening the Gilbert-Varshamov Bound in the Finite Case. Journal of Discrete Mathematical Sciences and Cryptography, 4, 65-75. https://doi.org/10.1080/09720529.2001.10697920

11. Hashim, A. (1978) Improvement on Varshamov-Gilbert Lower Bound on Minimum Hamming Distance of Linear Codes. Electrical Engineers Proceedings of the Institution, 125, 104-106. https://doi.org/10.1049/piee.1978.0028

12. Jiang, T. and Vardy, A. (2004) Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Binary Codes. IEEE Transactions on Information Theory, 50, 1655-1664. https://doi.org/10.1109/TIT.2004.831751

13. Tolhuizen, M.G.M.L. (1997) The Generalized Gilbert-Varshamov Bound Is Implied by Turan’s. IEEE Transactions on Information Theory, 43, 1605-1606. https://doi.org/10.1109/18.623158

14. Varshamov, R.R. (1957) Estimate of the Number of Signals in Error Correcting Codes. Doklady Akademia Nauk SSSR, 117, 739-741.

15. Plotkin, M. (1960) Binary Codes with Specified Minimum Distance. IEEE Transactions on Information Theory, 6, 445-450. https://doi.org/10.1109/TIT.1960.1057584

16. Agrell, E., Vardy, A. and Zeger, K. (2001) A Table of Upper Bounds for Binary Codes. IEEE Transactions on Information Theory, 47, 3004-3006. https://doi.org/10.1109/18.959279

NOTES

^*通讯作者。

期刊菜单