Non-Monotonicity of Optimal Identifying Code Size in Hypercubes

(with Rigorous Certificates for $r=2$ and Explicit Counterexamples for $r > n/2$)

Draft — February 22, 2026

Abstract

Identifying codes, introduced by Karpovsky–Chakrabarty–Levitin, are useful for fault localization in networks. In the binary Hamming space (hypercube) $Q_n$, let $M_r(n)$ denote the minimum size of an $r$-identifying code. A natural open question asks: for fixed radius $r$, is $M_r(n)$ monotonically non-decreasing in the dimension $n$? While monotonicity is known to hold for $r = 1$ (Moncel), the case $r > 1$ remained open. We provide two fully explicit counterexamples: (1) The classical $r = 2$ counterexample: $M_2(3) = 7 > 6 = M_2(4)$, where we construct a 6-element code and prove no 5-element code exists, forming a rigorous certificate; (2) A stronger result showing that even under the constraint $r > n/2$, monotonicity can fail: $M_3(4) = 15$ while $M_3(5) \leq 10$, hence $M_3(5) < M_3(4)$. These phenomena demonstrate that optimal identifying code sizes can exhibit sudden drops at boundary regimes (e.g., $n = r + 1$).

1. Introduction and Background

Let $Q_n$ denote the $n$-dimensional hypercube, with vertex set $\mathbb{F}_2^n = {0,1}^n$, where two vertices are adjacent if and only if they differ in exactly one coordinate. The hypercube is a classical model in parallel computing and network topology, making the structure and parameters of identifying codes on this graph a subject of sustained interest.

For any integer $r \geq 0$ and vertex $v$, define $$B_r(v) := {x \in \mathbb{F}_2^n : d(x, v) \leq r},$$ where $d(\cdot, \cdot)$ denotes the Hamming distance. Given a code $C \subseteq \mathbb{F}_2^n$, define the $r$-identifying set of vertex $v$ as $$I_r(v) := B_r(v) \cap C.$$

Definition 1 ($r$-identifying code). A set $C \subseteq \mathbb{F}_2^n$ is called an $r$-identifying code of $Q_n$ if:

1. (Covering) For all $v \in \mathbb{F}_2^n$, $I_r(v) \neq \emptyset$;
2. (Separation) For all distinct $u, v \in \mathbb{F}_2^n$, $I_r(u) \neq I_r(v)$.

Let $M_r(n)$ denote the minimum size of an $r$-identifying code of $Q_n$.

The optimization of identifying codes is generally NP-hard (e.g., Charon–Hudry–Lobstein established NP-hardness for general graphs). On hypercubes, a natural question is monotonicity: for fixed $r$, is $M_r(n)$ monotonically non-decreasing in $n$? Moncel proved monotonicity for $r = 1$, but for $r > 1$ the conclusion does not hold. Below we provide two fully explicit, directly verifiable counterexamples with rigorous proofs.

2. Preliminary Lemmas

2.1 Complementary Ball Identity

For $x \in \mathbb{F}_2^n$, let $\bar{x}$ denote the bitwise complement. Since for any $z$ we have $d(z, x) + d(z, \bar{x}) = n$, we obtain the following identity.

Lemma 2 (Complementary Ball Identity). For any $0 \leq r \leq n - 1$ and any $x \in \mathbb{F}_2^n$, $$\mathbb{F}$$2^n \setminus B_r(x) = B{n-r-1}(\bar{x}).

In particular, when $n = 5, r = 3$: $B_3(x) = \mathbb{F}_2^5 \setminus B_1(\bar{x})$; when $n = 4, r = 2$: $B_2(x) = \mathbb{F}_2^4 \setminus B_1(\bar{x})$.

Proof. $z \notin B_r(x) \iff d(z, x) \geq r + 1 \iff d(z, \bar{x}) \leq n - r - 1$. $\square$

2.2 Exact Value for Radius $n - 1$

Lemma 3. For any $n \geq 2$, $$M_{n-1}(n) = 2^n - 1.$$

Proof. For any $v$, we have $B_{n-1}(v) = \mathbb{F}_2^n \setminus {\bar{v}}$. If the identifying code $C$ has complement $\mathbb{F}$2^n \setminus CF2n​∖C containing at least two distinct points $a \neq b$, let $u = \bar{a}, v = \bar{b}$, then $$I$${n-1}(u) = (\mathbb{F}2^n \setminus {a}) \cap C = C, $$I$${n-1}(v) = (\mathbb{F}_2^n \setminus {b}) \cap C = C, so $u$ and $v$ cannot be separated—a contradiction. Hence $|\mathbb{F}_2^n \setminus C| \leq 1$, i.e., $|C| \geq 2^n - 1$. On the other hand, taking $C = \mathbb{F}_2^n \setminus {x}$ easily satisfies both covering and separation. $\square$

3. The $r = 2$ Computer-Assisted Counterexample: $M_2(3) = 7 > 6 = M_2(4)$

This section presents the well-known $r = 2$ non-monotonicity phenomenon. Such counterexamples are often first discovered via computer search; here we provide a hand-verifiable rigorous certificate: we construct a 2-identifying code of size 6 on $Q_4$ and prove that no 2-identifying code of size 5 exists.

3.1 Dimension $n = 3$: $M_2(3) = 7$

Corollary 4. $M_2(3) = 7$.

Proof. In $Q_3$, $r = 2 = n - 1$, so by Lemma 3, $M_2(3) = 2^3 - 1 = 7$. $\square$

3.2 Dimension $n = 4$: Constructing a 6-Element 2-Identifying Code

Let $$C = {0000, 0001, 0010, 0101, 1010, 1100} \subseteq \mathbb{F}_2^4.$$

Proposition 5. The set $C$ above is a 2-identifying code of $Q_4$; hence $M_2(4) \leq 6$.

Proof. Direct computation of $I_2(v) = B_2(v) \cap C$ shows that all 16 identifying vectors are non-empty and pairwise distinct. For ease of verification, Table 1 provides the identifying matrix $m_{v,c} = \mathbf{1}[d(v,c) \leq 2]$ (rows correspond to vertices $v$, columns to codewords $c \in C$). Since every row is non-zero and all rows are distinct, covering and separation hold. $\square$

Table 1: 2-identifying matrix for $C = {0000, 0001, 0010, 0101, 1010, 1100}$ in $Q_4$.

3.3 Optimality: No 5-Element 2-Identifying Code Exists

Proposition 6. No 2-identifying code of size 5 exists in $Q_4$; hence $M_2(4) \geq 6$.

Proof. Suppose for contradiction that a 2-identifying code $C \subseteq \mathbb{F}_2^4$ with $|C| = 5$ exists. By Lemma 2 (with $n = 4, r = 2$), $$I_2(v) = C \setminus (C \cap B_1(\bar{v})).$$

Define $$J(x) := C \cap B_1(x) \quad (x \in \mathbb{F}_2^4).$$

Then the injectivity of $v \mapsto I_2(v)$ is equivalent to the injectivity of $x \mapsto J(x)$ (since complementation and bitwise negation are both bijections). Therefore ${J(x) : x \in \mathbb{F}_2^4}$ must consist of 16 pairwise distinct subsets of $C$.

Note that $|B_1(x)| = 5$ and $|C| = 5$. If some $x$ satisfies $J(x) = C$, then $I_2(\bar{x}) = \emptyset$, violating covering. Hence $J(x) \neq C$ for all $x$, i.e., $$|J(x)| \leq 4 \quad (\forall x).$$

On the other hand, the number of subsets of $C$ with size $\leq 2$ is $$\binom{5}{0} + \binom{5}{1} + \binom{5}{2} = 1 + 5 + 10 = 16,$$

so to obtain 16 pairwise distinct values of $J(x)$, we must have exactly all subsets of size 0, 1, and 2, with no $J(x)$ of size $\geq 3$.

In particular, for any two distinct codewords $c_i, c_j \in C$, there must exist a unique vertex $x$ such that $$J(x) = {c_i, c_j} \iff d(x, c_i) \leq 1 \text{ and } d(x, c_j) \leq 1.$$

This means that for each pair of distinct codewords $c_i, c_j$, the radius-1 ball intersection $B_1(c_i) \cap B_1(c_j)$ must contain exactly one vertex $x$.

However, in $Q_4$, for any two distinct vertices $u \neq v$:

• If $d(u,v) = 1$, then $|B_1(u) \cap B_1(v)| = 2$ (namely $u$ and $v$ themselves);
• If $d(u,v) = 2$, then $|B_1(u) \cap B_1(v)| = 2$ (their two "midpoints");
• If $d(u,v) \geq 3$, then $B_1(u) \cap B_1(v) = \emptyset$.

In every case, $|B_1(u) \cap B_1(v)| \in {0, 2}$—it can never equal 1. Contradiction.

Therefore no $|C| = 5$ 2-identifying code exists, and $M_2(4) \geq 6$. $\square$

Combining Propositions 5 and 6 immediately gives $M_2(4) = 6$. Together with Corollary 4, we obtain the main result of this section.

Corollary 7. $$M_2(3) = 7 > 6 = M_2(4),$$ hence monotonicity of $M_r(n)$ in $n$ fails when $r = 2$.

4. Non-Monotonicity Persists for $r > n/2$: $M_3(4) = 15$ and $M_3(5) \leq 10$

This section addresses the stronger (seemingly more "reasonable") conjecture:

If $r > n/2$, then $M_r(n)$ is monotonically non-decreasing (or increasing) in $n$.

We prove this conjecture also fails, providing a fully explicit counterexample.

Theorem 8 (Explicit counterexample: even $r > n/2$ can decrease). Let $r = 3$. Then $$M_3(4) = 15, \quad M_3(5) \leq 10,$$ hence $M_3(5) < M_3(4)$. Note that $3 > 4/2$ and $3 > 5/2$, so the counterexample occurs in the regime $r > n/2$.

Proof.

Part 1: In $Q_4$, $r = 3 = n - 1$, so by Lemma 3, $M_3(4) = 2^4 - 1 = 15$.

Part 2: We construct a 3-identifying code of size 10 on $Q_5$. Let $e_i$ denote the unit vector with a 1 in position $i$ and 0 elsewhere, and let $\mathbf{1} = 11111$. Define $$C := {e_1, e_2, e_3, e_4, e_5} \cup {\mathbf{1} - e_1, \mathbf{1} - e_2, \mathbf{1} - e_3, \mathbf{1} - e_4, \mathbf{1} - e_5}.$$

That is, $C$ consists of all vertices of weight 1 and all vertices of weight 4, giving $|C| = 10$.

By Lemma 2 (with $n = 5, r = 3$), $$B_3(v) = \mathbb{F}_2^5 \setminus B_1(\bar{v}),$$ $$I_3(v) = C \setminus (C \cap B_1(\bar{v})).$$

Again define $J(x) := C \cap B_1(x)$. Since $|B_1(x)| = 6 < |C| = 10$, we must have $J(x) \neq C$, so $I_3(v) \neq \emptyset$ and covering holds.

To prove separation, it suffices to show $J(\cdot)$ is injective. For any $x \in \mathbb{F}_2^5$, we classify by weight:

• If $\text{wt}(x) = 0$ ($x = 00000$): $J(x) = {e_1, \ldots, e_5}$
• If $\text{wt}(x) = 5$ ($x = 11111$): $J(x) = {\mathbf{1} - e_1, \ldots, \mathbf{1} - e_5}$
• If $\text{wt}(x) = 1$ with $x = e_i$: $J(x) = {e_i}$
• If $\text{wt}(x) = 4$ with $x = \mathbf{1} - e_i$: $J(x) = {\mathbf{1} - e_i}$
• If $\text{wt}(x) = 2$ with 1-positions ${i, j}$: $J(x) = {e_i, e_j}$
• If $\text{wt}(x) = 3$ with 0-positions ${i, j}$: $J(x) = {\mathbf{1} - e_i, \mathbf{1} - e_j}$

The size and element structure of these sets uniquely determine $x$, hence $J(\cdot)$ is injective, and therefore $I_3(\cdot)$ is injective. Thus $C$ is a 3-identifying code and $M_3(5) \leq 10$. Combined with Part 1, we obtain $M_3(5) < M_3(4)$. $\square$

5. Discussion: Why Does the "Sudden Drop" Occur?

Theorem 8 shows that even when $r > n/2$, the optimal identifying code size can decrease as $n$ increases. The mechanism can be explained by a boundary phenomenon: when $n = r + 1$, the radius $r$ equals $n - 1$, and the ball almost covers the entire space. By Lemma 3, the optimal identifying code is then forced to be close to the full vertex set (size $2^n - 1$). However, once the dimension increases to $n = r + 2$, the same radius $r$ becomes $n - 2$, causing a significant change in local structure. This allows constructions of much smaller size, producing sudden drops like "$15 \to 10$."

References

[1] J. Moncel, "Monotonicity of the minimum cardinality of an identifying code in the hypercube," Discrete Applied Mathematics 154 (2006), 898–899.

[2] I. Charon, O. Hudry, A. Lobstein, "Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard," Theoretical Computer Science 290 (2003), 2109–2120.

[3] S. Janson, T. Laihonen, "On the size of identifying codes in binary hypercubes," Journal of Combinatorial Theory, Series A 116 (2009), 1087–1096.

[4] O. Hudry, V. Junnila, A. Lobstein, "Iiro Honkala's contributions to identifying codes," arXiv:2402.08264.