# A new explicit construction of unique-neighbor expanders

Weiqi Zhu

School of Mathematical Sciences, University of Science and Technology of China, Hefei 230026, China

Correspondence: Weiqi Zhu, E-mail: zwq13133565657@mail.ustc.edu.cn

© 2025 The Author(s). This is an open access article under the CC BY-NC-ND 4.0 license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

## Graphical abstract

<figure><img src="image_1.png" /><figcaption>Research framework.</figcaption></figure>

## Public summary

* This article presents a new method for explicitly constructing unique-neighbor expanders for specific degrees ($4 \le d \le 11$) using bipartite Ramanujan graphs and small gadgets. This moves beyond prior probabilistic methods, offering a more controlled approach.

* Unique-neighbor expanders have significant applications in network design, coding theory, and quantum computing, supporting efficient connectivity, data balancing, reliable error correction, etc.

* This work lays groundwork for further advancements in constructing higher-degree expanders and exploring more applications across network and data-intensive fields, enhancing efficiency in complex systems.
# A new explicit construction of unique-neighbor expanders

Weiqi Zhu

<figure><img src="image_2.png" /></figure>

School of Mathematical Sciences, University of Science and Technology of China, Hefei 230026, China

<figure><img src="image_3.png" /></figure>

Correspondence: Weiqi Zhu, E-mail: zwq13133565657@mail.ustc.edu.cn

© 2025 The Author(s). This is an open access article under the CC BY-NC-ND 4.0 license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

<figure><img src="image_4.png" /></figure>

Cite This: JUSTC, 2025, 55(5): 0505 (10pp)

<figure><img src="image_5.png" /></figure>

Read Online

**Abstract:** For every integer $4 \le d \le 11$, an explicit construction of infinite families of 2d-regular unique-neighbor expanders is presented, which is a generalization of the 6-regular unique-neighbors initially developed by Alon and Capalbo. Additionally, for values of $d$ greater than 11, a sufficient condition is established for employing the same construction method. Our construction method involves the “line product” of large bipartite Ramanujan graphs and a sufficiently good unique-neighbor expander (a small gadget).

**Keywords:** unique-neighbor expander; Ramanujan graph; line product

**CLC number:** O157.5

**Document code:** A

**2020 Mathematics Subject Classification:** 05C48

# 1 Introduction

Consider a graph $G = (V(G), E(G))$ and let $S$ be a subset of $V(G)$. A vertex $x \in V(G) \setminus S$ is called a unique neighbor of $S$ if and only if $x$ is connected to precisely one vertex within $S$. We call a graph $\Lambda = (V(\Lambda), E(\Lambda))$ an $\alpha$-unique-neighbor expander if for any subset $S$ of $V(\Lambda)$ such that $|S| \le \alpha|V(\Lambda)|$, there is a unique neighbor of $S$ in $\Lambda$. Currently, there is some information available about constructing expander graphs, but there is not much on the construction of unique-neighbor expanders, which are a special type of expander graph. In this study, we are interested in constructing explicit unique-neighbor expanders.

## 1.1 Related work

Alon and Capalbo[1] first gave several explicit constructions of unique-neighbor expanders. They developed infinite families of unique-neighbor expanders with degrees 3, 4, and 6 by employing a combination of graph products involving Ramanujan graphs and specialized gadgets. Additionally, they constructed a family of unbalanced bipartite unique-neighbor expanders, where the size of the left vertex side is $\frac{22}{21}$ times that of the right side, ensuring that any small subset on the left has a unique neighbor on the right.

However, not all of these four families are Cayley graphs. In response to Tali Kaufman's question about the existence of an infinite family of unique-neighbor expanders that are Cayley graphs, Becker[2] used a similar method to develop a construction of such a family where every graph in the family is a Cayley graph.

This construction methodology was further extended in recent research by Asherov and Dinur[3]. They constructed one-sided bipartite unique-neighbor expanders. Hsieh et al.[4] also contributed to this line of work by introducing two-sided

biregular unique-neighbor expanders. Their main construction methods yield two distinct products: the routed product and the line product. Both techniques leverage graph products involving Ramanujan graphs and gadgets of fixed sizes.

Another construction method uses random conductors. Capalbo et al.[5] utilized a generalized zig-zag product on random conductors to establish an infinite family of bipartite lossless expanders, which can be deduced into unique-neighbor expanders.

Lossless expanders exhibit the best unique-neighbor expansion properties. Recently, Golowich[6] presented a new explicit construction of one-sided bipartite lossless expanders with a constant degree and an arbitrary constant ratio between the sizes of the two vertex sets, which is simpler than the construction presented in Ref. [5].

## 1.2 Application

Unique-neighbor expanders are useful for designing non-blocking networks[7]: Given the input and output sets, there is an algorithm that can satisfy any request for a connection or disconnection between an input and an output in bounded steps, even if many requests are made at once.

In coding theory, Refs. [8, 9] proved that unique-neighbor expander codes[10,11] are weakly smooth and can be used to construct robustly testable codes with a code that has a constant relative distance.

Additionally, unique-neighbor expanders support algorithms for solving the load-balancing problem[1,12]: Given a unique-neighbor expander and a small set of pebbles, suppose that the pebbles are placed arbitrarily on the vertices of the graph. There is an algorithm for redistributing the pebbles via edges of the graph such that each vertex has at most one pebble.

Recently, with respect to quantum tanner codes, quantum LDPC codes, and $c^3$-LTCs[13–15], Lin and Heish[16] reported that,
assuming the existence of 2-sided lossless expander graphs with free group action, the resulting qLDPC codes have constant rate, linear distance, and linear time decoders.

## 1.3 Main results

Although Refs. [3, 4] presented the existence of infinite families of bipartite unique-neighbor expanders, they only used probability methods to show the existence of their gadgets, which means that we cannot have explicit constructions. Our conclusion serves as an explicit construction of infinite families of unique-neighbor expanders:

**Theorem 1.** For every integer $4 \le d \le 11$ and a small positive $\alpha$, there are infinite families of explicit $\alpha$-unique-neighbor $2d$-regular expanders.

Our approach to constructing expanders involves utilizing both the infinite family of bipartite Ramanujan graphs (for more details, refer to Section 2) and a fixed-size graph known as a gadget, which exhibits a good unique neighbor property. The foundation of our construction relies on a special graph product called the “line product” between the bipartite Ramanujan graph and the gadget. The crucial theorem we prove is that if the gadget has a “good” unique-neighbor property, then the line product graph is also a unique-neighbor expander.

# 2 Preliminaries

## 2.1 Expander graphs

In this section, we focus on undirected graphs. An expander graph is a sparse graph with the property that for any vertex subset $S$ of the graph, the size of the neighborhood (nodes adjacent to the nodes in $S$) of $S$ or the number of edges between $S$ and the complement of $S$ is at least a constant multiple of the size of $S$ (for expander graphs, see Ref. [17] for details).

By using the discrete Cheeger inequality[18], we can utilize a spectral method to assess expansion. Let $A$ be the adjacency matrix of an $n$-vertex $d$-regular graph $G$, and let $\lambda_1 = d \ge \lambda_2 \ge \cdots \ge \lambda_n$ be its spectrum. Then, $G$ is a $\lambda$-扩ender if the largest absolute value of non-trivial eigenvalues is less than or equal to $\lambda$, i.e., $\max\{|\lambda_2|, |\lambda_n|\} \le \lambda$ for non-bipartite $G$ and $\max\{|\lambda_2|, |\lambda_{n-1}|\} \le \lambda$ for bipartite $G$.

Consider a family of $d$-regular graphs $\{G_i\}_{i \in \mathbb{N}}$ with the number of vertices growing to infinity. This family is called an infinite family of $\lambda$-expanders if, for every $i$, $G_i$ is a $\lambda$-扩ender.

## 2.2 Ramanujan graphs

Given that small values of $\max\{|\lambda_2|, |\lambda_n|\}$ imply good expansion, it is natural to ask how small $\max\{|\lambda_2|, |\lambda_n|\}$ can be made. For $d$-regular graphs, the Alon–Boppana bound[19] presents the optimal spectral bound, which is $\lambda = 2 \sqrt{d-1}$. These specific graphs are referred to as Ramanujan graphs. Ramanujan graphs exhibit exceptional expansion properties, and their nontrivial eigenvalues are contained in the spectrum of the infinite $d$-regular tree. A critical challenge involves establishing the existence and constructing infinite families of Ramanujan graphs for all possible degrees. Significantly, Marcus et al.[20] employed the concepts of 2-lift and

interlacing families to demonstrate the existence of infinite families of regular bipartite Ramanujan graphs for every degree[20]. This result will subsequently be employed in developing our unique-neighbor expander.

**Remark 1.** The existence and explicit construction of an infinite family of $d$-regular Ramanujan graphs for every possible $d$ are still open. Ramanujan graphs are highly regarded for their exceptional expansion properties, raising the intuitive question of whether they are unique-neighbor expanders. Currently, most constructions of Ramanujan graphs have been achieved through number theory methods (see Refs. [21, 22] for details). However, Kamber and Kaufman[23] revealed that the graphs presented in Ref. [21] do not possess the unique-neighbor expansion property.

## 2.3 Products of the graphs

**Definition 1.** (Line product) Given a $d_1$-regular graph $G$ on $n$ vertices and a $d_2$-regular graph $H$ on $d_1$ vertices, the line product $G \circ H$ is a graph on the edges of $G$, where for every vertex $v \in G$, we put a copy of $H$ on the edges in $G$ incident to $v$.

**Example 1.** Here is an example of the line product:

<figure><img src="image_6.png" /></figure>

We use the line product to construct unique-neighbor expanders.

**Definition 2.** (Cartesian product) Given two graphs, $G = (V, E_1)$ and $H = (\Sigma, E_2)$. Consider $X = V \times \Sigma$. Subsequently, let $\Gamma = G \times H$ be the graph on $X$, where $(v, \pi)$ and $(v', \pi')$ are adjacent in $\Gamma$ if and only if either

① $v = v'$, and $\pi$ and $\pi'$ are adjacent in $\Sigma$, or

② $\pi = \pi'$, and $v$ and $v'$ are adjacent in $V$.

We use the Cartesian product to construct gadgets. In the following proofs, let $G$ be a good expander and $H$ be a fixed graph $C$, where good expander and $C$ will be defined later.

**Definition 3.** For every integer $d \ge 4$, We refer to a $(d-3)$-regular graph $G = (V(G), E(G))$ as a $d$-good expander if $|V(G)| \le \lfloor \frac{d^2}{8} \rfloor$, and for every $S \in V(G)$ with $2 \le |S| < \lfloor \frac{d+1}{4} \rfloor$, $S$ has at least $(d+1-4|S|)$ unique neighbors.

**Example 2.** For every integer $4 \le d \le 11$, we provide structures of $d$-good expanders that will be used to construct gadgets. The first four are $d$-good expanders for $4 \le d \le 7$ and the last four are the complement graphs of the $d$-good expanders for $8 \le d \le 11$.

<figure><img src="image_7.png" /></figure>

Now, let us construct the gadget: Fix $C = (\Sigma, E_2)$ be the $3$-regular, $8$-vertex graph on $N_{\ge 7}$, where $x$ and $y$ are adjacent in $C$ if and only if $|x-y|$ equals 1 or 4, or 7. For every integer
4 ≤ d ≤ 11, let $G = (V(G), E(G))$ a d-good expander, as defined in Example 2. As a result of taking the Cartesian product of $G$ and $C$, we obtain the gadget graph $\Gamma = G \times C$ is d-regular and $|X| \le d^2$.

**Example 3.** Fig. 1 shows an example of the construction of the gadget $\Gamma = K_2 \times C$.

### 3 Construction

In this section, we generalize the construction of $d = 3$ in Ref. [1]. For every integer $4 \le d \le 11$, with the d-regular gadget $\Gamma = (X, E(\Gamma))$ defined before, we present the explicit construction of our unique-neighbor expanders. For the remainder of this section, we denote $H_x$ as the infinite family of $|X|$-regular Ramanujan graphs. In accordance with Ref. [20], we are aware of the existence of regular bipartite Ramanujan graphs of all degrees. Furthermore, Ref. [24] provides a polynomial-time algorithm for deriving these graphs from the results in Ref. [20]. As a consequence, we can efficiently obtain $H_x$ for each degree $|X|$ within polynomial time.

Let $\Lambda = (V(\Lambda), E(\Lambda))$ be a graph in $H_x$. Let $\Lambda' = \Lambda \circ \Gamma$. If $\Lambda'$ is 2d-regular, we assert the following:

**Theorem 2.** $\Lambda'$ is an $\alpha$-unique-neighbor 2d-regular expander, with $\alpha$ as defined in Corollary 1 below.

The proof of Theorem 2 is a generalization of the proof of $d = 3$ in Ref. [1], which hinges on a theorem established by Kahale[25] and an alternate proof method presented by Asherov et al.[3] Additionally, we rely on the following theorem:

**Theorem 3.** Let $\bar{\Lambda} = (\bar{V}, \bar{E})$ be a k-regular Ramanujan graph. Then, for all $\delta > 0$ and any nonempty subset $S$ of size at most $k^{-\frac{1}{\delta}}|\bar{V}|$, the average degree $d$ of $\bar{\Lambda}[S]$ satisfies

$$d \le (1 + \sqrt{k-1})(1 + O(\delta)).$$

This theorem illustrates the corollary we employ:

**Corollary 1.** For a graph $\Lambda = (V(\Lambda), E(\Lambda))$ in $H_x$, there exists a strictly positive $\alpha$ such that, for any subset $S$ of $E(\Lambda)$ where $|S| \le \alpha|E(\Lambda)|$, the average degree of $\Lambda[V_S]$ is at most $1.1 + \sqrt{|X|-1}$, where $V_S$ is the set of vertices $v \in V(\Lambda)$ such that $v$ is incident to at least one edge in $S$.

<figure><img src="image_8.png" /><figcaption>**Fig. 1.** The gadget $\Gamma = K_2 \times C$.</figcaption></figure>

**Proof.** Given $\Lambda$ as a $|X|$-regular graph, for any edge subset $S$ with $|S| \le \alpha|E(\Lambda)|$, we have $|V_S| \le 2|S| \le 2\alpha|E(\Lambda)| = \alpha|X||V(\Lambda)|$. For every $\alpha$, there exists a $\delta = \delta(\alpha)$ such that $\alpha|X| \le |X|^{-\frac{1}{\delta}}$. Hence $|V_S| \le |X|^{-\frac{1}{\delta}}|V(\Lambda)|$. By selecting a sufficiently small $\alpha$ and $\delta$, we can use Theorem 3 to establish that the upper bound of the average degree of $V_S$ is $1.1 + \sqrt{|X|-1}$.

With this, we need a theorem of the gadget.

**Theorem 4.** For every integer $d \ge 4$, when $C$ is the graph defined earlier and $G$ is a d-good expander, consider $\Gamma = G \times C$. In $\Gamma$, for every nonempty subset $J$ of $X$, the quantity $|J| + |J'|$ is at least $d+1$, where $J'$ is the set of vertices $(v, \pi)$ in $X \setminus J$ such that $(v, \pi)$ is a unique neighbor of $J$ in $\Gamma$.

The proof of Theorem 4 is given in the next section. Leveraging Theorem 4 and Corollary 1, we can now prove Theorem 2. The proof of this theorem is an extension of the proof of Theorem 2.1 in Ref. [1].

**Proof of Theorem 2.** Let $S$ be a subset of $E(\Lambda)$ with $|S| \le \alpha|E(\Lambda)|$, and define $V_S$ as specified in Corollary 1. By Corollary 1 there exists a vertex $v \in V_S$ in $\Lambda$ with at most $\lfloor 1.1 + \sqrt{|X|-1} \rfloor$ neighbors in $V_S$. Let $E_v$ be the set of edges in $E(\Lambda)$ incident to $v$ and $H_v$ be a graph isomorphic to $\Gamma$, with $E_v$ as its vertex set. Define $J = E_v \cap S$ and let $J'$ be the set of all vertices of $H_v$ that are adjacent to a unique vertex of $J$. Notably, all the elements in $J \cup J'$ correspond to edges of $\Lambda$ incident with $v$. Applying Theorem 4, we have $|J| + |J'| \ge d+1$, indicating that there is at least one member $\gamma \in J \cup J'$ whose other endpoint (besides $v$) lies outside $V_S$, as $|X| \le d^2$ and $d+1 \ge \lfloor 1.1 + \sqrt{|X|-1} \rfloor$. By the definition of $V_S$, it is evident that $\gamma \in J'$ implies that $\gamma$ is not in $S$ and serves as a unique neighbor of $S$.

### 4 Proof of Theorem 4

In this section, we establish the significant property concerning the gadget, which will be used to construct unique-neighbor expanders. In fact, this theorem holds not only for $4 \le d \le 11$ but also for $d > 11$.

We start with a few useful definitions for $G = (V, E_i)$ and $C = (\Sigma, E_2)$. For each vertex $v \in V$, let $C_v$ denote the set $\{(v, \pi) \in X | \pi \in \Sigma\}$ and refer to it as row $v$. Similarly, for each $\pi \in \Sigma$, let $G_\pi$ denote the set $\{(v, \pi) \in X | v \in V\}$ and call it column $\pi$. As such, we denote $\Gamma_v = \Gamma[C_v]$, $\Gamma_\pi = \Gamma[G_\pi]$; therefore, $\Gamma_v \cong C$, $|C_v| = 8$, and $\Gamma_\pi \cong G$, $|G_\pi| = |V|$.

For any $J \subset X$, let $J_v$ be the set of pairs $(v, \pi)$ in $J$ for a given $v \in V$, $J_\pi$ be the set of pairs in $J$ for a given $\pi \in \Sigma$, and let $j_v = |J_v|$, $j_\pi = |J_\pi|$. Define $R_j = \{v \in V | \exists \pi \in \Sigma \text{ such that } (v, \pi) \in J\}$ and $C_j = \{\pi \in \Sigma | \exists v \in V \text{ such that } (v, \pi) \in J\}$. The number of rows and columns in $J$ are represented as $r_j = |R_j|$ and $c_j = |C_j|$, respectively.

**Definition 4.** Consider a subset $J$ of $X$. We define a unique neighbor of $J$ as $(v, \pi)$, which is a row unique neighbor if it is connected to a vertex in $J_v$ and a column unique neighbor if connected to a vertex in $J_\pi$.

The proof is structured into eight cases (labeled “case i”). In each case, we assume that the vertices within subset $J$ are present in exactly $i$ columns, i.e., $c_j = i$. For values of $d$ less than 8, it is sufficient to consider the first $d$ cases.

First, we need the following observation about graph $C$.
**Lemma 1.**<sup>[1]</sup> Let $C$ be the 3-regular, 8-vertex graph on $\mathbb{N}_{\ge 7}$, where $x$ and $y$ are adjacent in $C$ if and only if $|x-y|$ equals 1, 4, or 7. For every nonempty subset $J$ of $\mathbb{N}_{\ge 7}$, the quantity $|J|+|J'|$ is at least 4.

For every nonempty $J$ with $|J| < d+1$, with the support of Lemma 1, we assert the following:

**Lemma 2.** Let $J \subset X$ and $(v, \pi) \in J$. Then

(i) There are at least $\max\{0, 4-c_j\}$ row unique neighbors of $J$ in $\Gamma_v$.

(ii) If $j_\pi = |J_\pi|$ is less than $\lceil \frac{d+1}{4} \rceil$, then there are at least $\max\{0, d+1-r_j-3j_\pi\}$ column unique neighbors of $J$ in $\Gamma_\pi$.

**Proof.** (i) Suppose that $c_j < 4$; from Lemma 1, the number of row unique neighbors in $\Gamma_v$ of $J_v$ is at least $\max\{0, 4-j_v\} = 4-j_v$ since $j_v \le c_j$. Importantly, $(4-j_v)-(c_j-j_v) = 4-c_j$ of these $4-j_v$ neighbors must be unique since $c_j-j_v$ of these $4-j_v$ neighbors could be shared with the neighboring column(s).

(ii) In $\Gamma_\pi$, $j_\pi$ vertices yield $d+1-4j_\pi$ unique neighbors of $J_\pi$ since $\Gamma[G_\pi] \cong G$. Similarly, some neighbors might also be shared with vertices from other columns within the same row, but their count is no greater than $r_j-j_\pi$. Hence, a minimum of $d+1-r_j-3j_\pi$ column unique neighbors remain.

The first statement in Lemma 2 is applicable between Case 1 and Case 3, whereas the second statement is useful between Case 2 and Case 5. However, addressing Cases 4 and 5 necessitates the introduction of another crucial lemma, which will be proven separately in the next section.

**Lemma 3.** Let $J \subset X$ with $|J| = d-d_0$, $r_j = d-d_0-k \ge \lceil \frac{d+1}{4} \rceil$, and $c_j = 4$ or 5, accounting for all possible nonnegative $d_0$ and $k$. For any integer $i \ge 1$, there exist at least $\max\{0, 3i-k\}$ row unique neighbors of $J$ if $j_\pi \ge i$ for every $\pi \in C_j$.

**Case 1-3:** Choose $\pi \in C_j$ with the minimum $j_\pi$. If $j_\pi \ge \lceil \frac{d+1}{4} \rceil$, applying Lemma 2 we have at least $r_j \cdot (4-c_j)$ row unique neighbors. Therefore, $|J|+|J'| \ge c_j \cdot j_\pi + r_j \cdot (4-c_j) \ge 4j_\pi \ge d+1$. If $j_\pi < \lceil \frac{d+1}{4} \rceil$, adding the extra $\max\{0, d+1-r_j-3j_\pi\}$ column unique neighbors we have $|J|+|J'| \ge c_j \cdot j_\pi + r_j \cdot (4-c_j) + \max\{0, d+1-r_j-3j_\pi\}$. If $d+1-r_j-3j_\pi \ge 0$,

$$|J| + |J'| \ge c_j \cdot j_\pi + r_j \cdot (4 - c_j) + d + 1 - r_j - 3j_\pi = d + 1 + (3 - c_j)(r_j - j_\pi) \ge d + 1.$$

If $d+1-r_j-3j_\pi < 0$,

$$|J| + |J'| \ge c_j \cdot j_\pi + r_j \cdot (4 - c_j) = r_j + 3j_\pi + (3 - c_j)(r_j - j_\pi) > d + 1.$$

**Case 4-5:** If $r_j < \lceil \frac{d+1}{4} \rceil$, it follows that the vertex count within each of these four or five columns is less than or equal to $r_j$. As per Lemma 2, within each column $\Gamma_\pi$ for $\pi \in C_j$, the summation of the number of column unique neighbors and the vertex count is at least $d+1-r_j-2j_\pi \ge d+1-3r_j$. Notably, $c_j \cdot (d+1-3r_j) \ge c_j(d+1) - 3c_j(\lceil \frac{d+1}{4} \rceil - 1) \ge d+1$, which implies that $|J|+|J'| \ge d+1$.

However, when $r_j \ge \lceil \frac{d+1}{4} \rceil$, we can use Lemmas 2 and 3 to establish the following proof: By the pigeonhole principle, there is a column $\pi \in C_j$ with the minimum $j_\pi < \lceil \frac{d+1}{4} \rceil$ since $r_j \ge \lceil \frac{d+1}{4} \rceil$. Therefore, by Lemma 2 we have $|J|+|J'| = d-d_0+d+1-(d-d_0-k)-3j_\pi = d+1+k-3j_\pi$. Let $i = j_\pi$; if $k \ge 3i$, we are doing so. Otherwise, by Lemma 3 there are $3i-k$ extra row unique neighbors. Adding it, then we can obtain $|J|+|J'| \ge d+1$.

**Case 6:** In this instance, a lemma is needed.

**Lemma 4.** For any two distinct vertices $\pi$ and $\pi'$ in graph $C$, it is guaranteed that in the graph $C' = C - \{\pi, \pi'\}$, there cannot exist a group of 3 vertices, each with a degree of 3 in $C'$.

**Proof.** Considering any two vertices $\pi \ne \pi'$ in $C$, if $\pi$ is adjacent to $\pi'$ in $C$, then $\{\pi, \pi'\}$ has 4 neighbors externally. On the other hand, if $\pi$ is not adjacent to $\pi'$ in $C$, then the combined set $\{\pi, \pi'\}$ has 4 or 5 neighbors externally. Therefore, upon removing the $\pi$ and $\pi'$ from the graph, a minimum of 4 vertices will experience a decrease of 1 in their degrees. This reduction in degrees implies that it is impossible to identify 3 vertices with a degree of 3 within the graph $C'$.

For every nonempty $J$ with $|J| < d+1$, we can invoke the pigeonhole principle, which reveals that there exist at least 3 columns where the vertex count is less than $\lceil \frac{d+1}{4} \rceil$. Assuming that the points are not distributed in columns $\pi$ and $\pi'$, we obtain a corresponding graph $C'$. Assume that the number of vertices for these six columns is $j_{\pi_1}, j_{\pi_2}, j_{\pi_3}, j_{\pi_4}, j_{\pi_5}$, and $j_{\pi_6}$, and, without loss of generality, $j_{\pi_1} \le j_{\pi_2} \le j_{\pi_3} \le j_{\pi_4} \le j_{\pi_5} \le j_{\pi_6}$. When there are precisely three columns with a vertex count less than $\lceil \frac{d+1}{4} \rceil$, which means that there are $d+1-4j_{\pi_1}+d+1-4j_{\pi_2}+d+1-4j_{\pi_3} = 3(d+1)-4(j_{\pi_1}+j_{\pi_2}+j_{\pi_3})$ unique neighbors in $\Gamma_{\pi_1}, \Gamma_{\pi_2}$ and $\Gamma_{\pi_3}$. Utilizing Lemma 4 for calculation, the upper bound on the number of eliminated unique neighbors is $j_{\pi_4}+j_{\pi_5}+j_{\pi_6}+j_{\pi_2}+j_{\pi_3}+j_{\pi_5}+j_{\pi_6}$, which is the case in which $\pi_1$ is connected to $\pi_4, \pi_5, \pi_6$ in $C$, $\pi_2$ is connected to $\pi_3, \pi_5$, and $\pi_6$ in $C$ and $\pi_3$ is connected to $\pi_2$, and $\pi_4$ in $C$ by Lemma 4. Hence, we obtain a lower bound on the remaining number of unique neighbors, which is $3(d+1)-4(j_{\pi_1}+j_{\pi_2}+j_{\pi_3})-(j_{\pi_4}+j_{\pi_5}+j_{\pi_6}+j_{\pi_2}+j_{\pi_5}+j_{\pi_6}+j_{\pi_3}+j_{\pi_4})$. Therefore,

$$|J| + |J'| \ge 3(d+1) - 3j_{\pi_1} - 4j_{\pi_2} - 4j_{\pi_3} - j_{\pi_4} - j_{\pi_5} - j_{\pi_6} \ge 2(d+1) - 2j_{\pi_1} - 3j_{\pi_2} - 3j_{\pi_3} \ge d+1.$$

In the case where there are 4, 5, or 6 columns with a vertex count less than $\lceil \frac{d+1}{4} \rceil$, a similar calculation on the remaining unique neighbors on those columns, added to their vertex counts, will also lead to the conclusion.

**Case 7-8:** Consider any nonempty set $J$ with $|J| < d+1$. Let us choose the column $\pi \in C_j$ with the minimum $j_\pi$. By applying the pigeonhole principle, we observe that $j_\pi < \lceil \frac{d+1}{c_j} \rceil \le \lceil \frac{d+1}{4} \rceil$. Consequently, there are at least $d+1-4j_\pi$ unique neighbors in $\Gamma_\pi$.

However, these neighbors can also be shared with other vertices in some rows, and we can deduce that the count of the unique neighbors within $\Gamma_\pi$ but not in the original graph $\Gamma$
is at most $|J| - (c_J - 3)j_π$. This is because suppose the degree of vertex $π$ equals 3 in $C[C_J]$, and all other columns contain $j_π$ vertices, which means that at least $(c_J - 3)j_π$ vertices of $J$ cannot be the neighbors of these unique neighbors. Therefore, $|J'|$ is greater than or equal to

$$d+1-4j_{\pi}-(|J|-(c_{J}-3)j_{\pi})=d+1-|J|+(c_{J}-7)j_{\pi}.$$

In light of this, we establish that $|J| + |J'| \ge d + 1$.

# 5 Proof of Lemma 3

In this section we prove Cases 4 and 5 of Lemma 3 separately, and we do so by employing induction on the variable $i$.

For Case 4: Let us begin by introducing several definitions and lemmas that will be used.

**Definition 5.** Let $J \subset X$, we refer to a vertex $(v, \pi) \in J$ as an "isolated row vertex" if $j_v = 1$.

**Definition 6.** We call "same rows" for those rows that share the same vertex count and are situated in the same column and "distinct rows" as rows where any two of them are not the same.

**Lemma 5.** If there are four isolated row vertices of $J$ in four distinct columns, then these four vertices have a minimum of three row unique neighbors of $J$.

**Lemma 6.** Any pair of distinct rows of $J$ in the graph $\Gamma$ have at least one row unique neighbor of $J$.

**Lemma 7.** Any three distinct rows of $J$ in the graph $\Gamma$ have at least two row unique neighbors of $J$.

These three Lemmas are established by thoroughly considering all possible cases, and we present the proofs in the Appendix.

For $i=1$, we need to consider only cases where $k$ is less than 3. If $k < 3$, there must exist such structures:

$$\left(\begin{array}{ccccc}
1 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 1
\end{array}\right), \left(\begin{array}{ccccc}
1 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 1
\end{array}\right), \left(\begin{array}{ccccc}
1 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 1
\end{array}\right), \\
\left(\begin{array}{ccccc}
1 & 1 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 1
\end{array}\right), \left(\begin{array}{ccccc}
1 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 1 & 1
\end{array}\right).$$

Here, we employ the symbol "1" to denote a vertex in $J$, whereas "0" indicates its absence. The initial matrix corresponds to $k=0$, the second to $k=1$, and the subsequent matrices from the third to the sixth pertain to $k=2$. For each value of $k$ and its corresponding structure, utilizing Lemmas 5, 6, and 7 we can obtain at least $3-k$ unique neighbors in these rows.

Assuming that it holds for $i-1$, let us consider the case for $i$. At this point, $j_π \ge i$ for every $π \in C_J$, so $|J| \ge 4i$. Let us partition it into three cases for discussion on the basis of the value of $k$.

(i) When $k \le i-1$: Since $k \le i-1$ and $j_π \ge i$, any possible scenario for $J$ includes these two structures: The first one is four isolated row vertices in four distinct columns, and the second one is all $J \subset X$ with $|J| = d - d_0 - 4$,

$r_J = d - d_0 - 4 - k$, and $j_π \ge i-1$ for every $π \in C_J$. The first structure has 3 row unique neighbors by Lemma 5, and the second structure has $3(i-1) - k$ by induction. Summing them, we have $3i - k$ row unique neighbors.

(ii) When $i \le k < 2i$: First, since $|J| = d - d_0 \ge 4i$, we have $r_J \ge 4i - k$. In this case, we claim that we can select $m$ pairs of 3 distinct rows and $n$ pairs of 2 distinct rows, where $m+n=i$ and $3m+2n=4i-k$. By this claim, Lemma 6, and Lemma 7 we have a total number of row unique neighbors greater than or equal to $2m+n=3i-k$.

To prove the upper claim, we can easily obtain $m$ and $n$ pairs of 3 and 2 rows because we can first select $i$ pairs of two rows, and then remove $m$ rows from the remaining rows to distribute among $m$ pairs, ensuring that each pair receives one row. Therefore, the difficulty lies in the distinctions. If the number of the same rows is all less than or equal to $i$, we can greedily select them. Conversely, if there is a set of same rows with row count $r_0$, which is greater than $i$:

(a) If these same rows each have only 1 vertex, these vertices are isolated row vertices. Since we only need to eliminate $(i-1)$-columns, we can simplify this by selecting $i$ rows from within these. This reduces it to the previously discussed scenario.

(b) If these same rows each consist of 2 vertices, the number of extra vertices represents the number of vertices left of $J$ on the basis of having one vertex in each row in $R_J$, so this number must be $k$. Therefore, $r_0$ extra vertices are used so the number of rows of $J$ intersecting with the other two columns is at least $2i - (k - r_0)$, because there are at least $i$ vertices in each column and $k - r_0$ extra vertices remaining. With the bound $r_0 > i$, we have $2i - (k - r_0) > 3i - k$, and the largest count of the same rows among these rows is $i$ by (a). We begin by selecting $i$ rows from the same rows and placing them into $i$ pairs, ensuring each pair contains one row. Then, rows are greedily selected from the rows intersecting with the other two columns until each pair consists of distinct rows.

(c) If these same rows have 3 or 4 vertices each, $2r_0$ or $3r_0$ extra vertices are used, which means that there are at least $2 \times (i+1) \ge k$ extra vertices, leading to a contradiction.

(iii) When $2i \le k \le 3i-1$: With $r_J$ greater than or equal to $4i-k$, select $n$ pairs of 2 rows each from these rows, where $n = \lfloor \frac{4i-k}{2} \rfloor$. This approach to selection is justified. Additionally, we can prove $3i-k \le n$. If $k$ is even, we only need to prove $6i-2k \le 4i-k$, which is evident from $2i \le k$. If $k$ is odd, only need to prove $6i-2k \le 4i-k-1$, which follows from $2i+1 \le k$.

Therefore, we only need to prove that we can obtain a total of $3i-k$ pairs of 2 distinct rows from all rows, which means $3i-k$ row unique neighbors by Lemma 6. If the number of same rows is less than or equal to $3i-k$, we can greedily select them. Otherwise, if there is a set of the same rows with a row count greater than $3i-k$:

(a) If each of these specific rows consists of 4 vertices, then the row count cannot exceed $i-1$; otherwise, we would have at least $3 \times i$ extra vertices, leading to a contrast. Considering all rows, there are at least $4i-k-(i-1)=$
$3i-k+1 \ge 3i-k$ rows remaining. By combining one row from the same rows with another from the remaining rows, we achieve our goal.

(b) If each of these same rows has 1, 2, or 3 vertices, consider the corresponding 3, 2, or 1 column(s) not occupied by vertices in these rows. At least $i \ge 3i-k$ other rows of J intersect with these column(s) because $j_\pi \ge i$. Similarly, combine one row from the same rows with another from the remaining rows.

For Case 5, at this point, the three crucial lemmas from Case 4 no longer hold. However, we can only establish some special structures. These structures help us estimate the number of row unique neighbors. The first lemma concerns isolated row vertices.

**Lemma 8.** If there are two (three) isolated row vertices of J in two (three) distinct columns, then there are 2 and 1 row unique neighbor(s) of J within these rows.

**Lemma 9.** For the structure

$$ \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}, \\ \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \end{pmatrix}, \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 \end{pmatrix}, \\ \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 \end{pmatrix} $$

there are 1, 1, 2, 2, 2, 2, 2, 2, and 2 row unique neighbor(s) of J within these rows.

The proofs of the two lemmas above rely on exhaustive enumeration. To maintain concision, they are presented in the Appendix. Similarly, we proceed with the proof of Lemma 3 in Case 5 by employing an induction on $i$.

For $i=1, k < 3$, such structures must exist:

$$ \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}, \\ \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} $$

Analogously, the initial matrix corresponds to $k=0$, the second corresponds to $k=1$, and the subsequent matrices from the third to the sixth matrix pertain to $k=2$. By Lemmas 8 and 9 we can find that for each $k < 3$ and each structure, there are $3i-k$ row unique neighbors.

Assuming that it holds for $\le i-1$, consider case $i$. The following lemma pertains to a specific structures, and by employing these structures and using induction, we can directly derive the proof of Lemma 3. For all the structures that do not contain structures from Lemma 10, we utilize Lemmas 8 and 9 to calculate the count of row unique neighbors.

**Lemma 10.** If there exist some rows that fit into any of the

following structures, Lemma 3 holds.

$$ \begin{pmatrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \end{pmatrix}, \\ \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{pmatrix}, \\ \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 \end{pmatrix} $$

**Proof.** In the general order from top to bottom and left to right, “(m)” represents the mth structure.

(1) The remaining part is identical to the case where $d_{01} = d_0 + 5$, $i_1 = i - 1$, and $k_1 = k - 4$, with the straightforward verification that $k_1 < 3i_1$. By induction, there are at least $3i_1 - k_1 = 3i - 3 - k + 4 \ge 3i - k$ row unique neighbors.

(3) All the remaining cases are encompassed within the context where $i_1 = i - 2$ and $k_1 = k - 6$. Similarly, by induction.

(4) The remaining part is identical to the case where $i_1 = i - 1$ and $k_1 = k - 2$. Therefore, if $k < 3i - 1$, we have $k_1 < 3i_1$, and by induction, $3i_1 - k_1 = 3i - k - 1$ row unique neighbors exist. With Lemma 9, we deduce $3i - k$. If $k = 3i - 1$, we can directly apply Lemma 9 to obtain a row unique neighbor.

The fifth, seventh, and eighth cases are akin to the fourth case, and the second and sixth cases resemble the first case.

On the basis of Lemma 10, we need only consider cases that do not include the aforementioned structures. We classify them on the basis of the column number where the isolated row vertices are located.

**5 columns:** Divide the structure into two parts: The first part is $i_1 = i - 1, k_1 = k$, and the second part is five isolated row vertices in five different columns. By induction and Lemma 8, there are $\max\{0, 3(i-1)-k\} + 3 \ge \max\{0, 3i-k\}$ unique neighbors.

**4 columns:** Let us focus on the remaining column. All rows intersecting with this column can contain 2, 3, 4, or 5 vertices. However, these several possibilities each belong to structures 7, 5, 2, and 1 of lemma 10.

**3 columns:** In the following four scenarios (from 3 columns to 0 columns), we need to consider all possible row distributions of vertices. We continue to utilize matrices, with the final letter in each row of the matrices signifying the number of rows in J for that specific row distribution.

$$ \begin{pmatrix} 1 & 1 & 1 & 0 & 0 & b_1 \\ 1 & 1 & 0 & 1 & 0 & b_2 \\ 1 & 1 & 0 & 0 & 1 & b_3 \\ 1 & 0 & 1 & 1 & 0 & b_4 \\ 1 & 0 & 1 & 0 & 1 & b_5 \\ 1 & 0 & 0 & 1 & 1 & b_6 \\ 0 & 1 & 1 & 1 & 0 & b_7 \\ 0 & 1 & 1 & 0 & 1 & b_8 \\ 0 & 1 & 0 & 1 & 1 & b_9 \\ 0 & 0 & 1 & 1 & 1 & b_{10} \end{pmatrix}, \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & c_1 \\ 1 & 0 & 1 & 0 & 0 & c_2 \\ 1 & 0 & 0 & 1 & 0 & c_3 \\ 1 & 0 & 0 & 0 & 1 & c_4 \\ 0 & 1 & 1 & 0 & 0 & c_5 \\ 0 & 1 & 0 & 1 & 0 & c_6 \\ 0 & 1 & 0 & 0 & 1 & c_7 \\ 0 & 0 & 1 & 1 & 0 & c_8 \\ 0 & 0 & 1 & 0 & 1 & c_9 \\ 0 & 0 & 0 & 1 & 1 & c_{10} \end{pmatrix} $$

Assuming that all isolated row vertices are confined to the first three columns of the matrices, the focus then shifts to the remaining two columns, and suppose $k < 3i$. As indicated by Lemma 10, no row intersects both of these columns, leading
to the inference that the number of rows intersecting these two columns is greater than or equal to 2i. Consequently, at least one value $c_q > 0$ must hold, where $q \in \{3,4,6,7,8,9\}$; otherwise, $k \ge 2 \times 2i = 4i$, which is a contradiction.

If we consider only one such case, by symmetry let us assume $c_3$. This assumption implies that the count of vertices in rows intersecting with the last column must be greater than or equal to 3, leading to $k \ge 2 \times i + i = 3i$, which contradicts the initial premise.

Suppose that two $c_q$ values are active, and according to Lemma 10, the potential cases are $\{c_8, c_9\}$ and $\{c_6, c_8\}$. In the first scenario, only variables $b_4, b_5, b_7, b_8, a_1$, and $a_2$ could be greater than 0 by the above lemmas, with the following constraints about the remaining 2 columns:

$$ \begin{cases} c_8 + b_4 + b_7 + a_1 \ge i, \\ c_9 + b_5 + b_8 + a_2 \ge i. \end{cases} $$

However, in this instance, the sum of $c_8 + c_9 + b_4 + b_5 + b_7 + b_8 + a_1 + a_2$ would indicate that the vertex count in the third column is greater than or equal to 2i, which is contradictory since there are $3i-k$ row unique neighbors from the rows intersecting with the last three columns. In the second scenario, where $\{c_6, c_8\}$ are active, the number of vertices in rows intersecting with the last column must be greater than or equal to 3, thus implying $k \ge 3i$.

For the scenario involving greater than or equal to three $c_q$ values > 0, the only plausible combination is $\{c_3, c_6, c_8\}$. In this case, the number of vertices in rows intersecting with the last column must be 4, which leads to contradictions.

**2 columns:** Without loss of generality, let us consider the scenario where all isolated row vertices exist only in the first two columns of the matrices and suppose $k < 3i$. By Lemma 10 only need to consider $a_4 = a_5 = b_{10} = 0$. In this context, we assert that $c_8 + c_9 + c_{10} > 0$. If this condition is not met, then we obtain the following system of equations:

$$ \begin{cases} 3 \sum_{q=1}^{3} a_q + 2 \sum_{q=1}^{9} b_q + \sum_{q=1}^{7} c_q = k, \\ 2 \sum_{q=1}^{3} a_q + \sum_{q=1}^{3} b_q + 2 \sum_{q=4}^{9} b_q + \sum_{q=1}^{7} c_q \ge 3i. \end{cases} $$

The first one is about the number of extra vertices, and the second one is because at least $i$ vertices in each of the last three columns. Therefore, $k \ge 3i$, which is a contradiction. Without loss of generality, let us assume that $c_8 \le c_9 \le c_{10}$. According to structure 4 and 5 of Lemma 9, we deduce that $a_1 = a_2 = a_3 = 0$.

$$ \text{If } c_8 \neq 0, \text{ then there is a structure } \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 \end{pmatrix}. \text{ By} $$

applying Lemma 10, we establish that this case is resolved.

Now, let's consider the situation where $c_8 = 0$ and $c_9 \neq 0$.

In this case, the structure is $\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{pmatrix}$. The

remaining part of this structure can be categorized either as

the case of $i-1, k-2$ or when the last column contains exactly $i$ points. For the first case, by utilizing Lemmas 8 and 9 and employing induction, the problem is resolved. For the second case, the vertex requirements from the third column to the fifth column are as follows:

$$ \begin{cases} b_4 + b_5 + b_7 + b_8 + c_9 \ge i, \\ b_4 + b_6 + b_7 + b_9 + c_{10} \ge i, \\ b_3 + b_5 + b_6 + b_8 + b_9 + c_4 + c_7 + c_9 + c_{10} = i. \end{cases} $$

Summing these equations leads to $2b_4 + 2b_7 \ge i + b_3 + c_4 + c_7$. This implies that $b_4$ and $b_7$ cannot both be 0. Thus,

we encounter another structure $\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{pmatrix}$. In this

structure, we have at least 2 row unique neighbors. The remaining part can be analyzed as the scenario of $i-2, k-4$, leading to obtaining $3i-k$ unique neighbors.

Now, let us consider the scenario where $c_8 = c_9 = 0$. In the third column, we have

$$ b_4 + b_5 + b_7 + b_8 \ge i. $$

If only $b_4$ and $b_7$ are greater than 0, this implies $k \ge 2(b_4 + b_7) \ge 2i$. However, since there are no vertices in the fifth column, filling it with at least $i$ points would require $k \ge 2i + i = 3i$, which contradicts the assumption. The case where only $b_5$ and $b_8$ are greater than 0 follows the same logic. Similarly, for the other cases, we can apply induction to resolve the situation.

**1 column:** In this case, we split the proof into two parts. In the first part, we assume that there is only one isolated row vertex, which is situated without loss of generality in the first column. We claim that a row with 2 vertices intersecting the first column must exist. If not, among all the rows intersecting the first column, let the number of rows containing three vertices be denoted as $a$, and the number of rows containing four vertices be denoted as $b$. Thus, $a+b \ge i-1$. Since the remaining four columns have a point count greater than or equal to $i$, we have $k \ge 3a + 2b + \frac{1}{2}(4i - (3a + 2b)) \ge 3i - 1 + \frac{1}{2}a$ (Equality holds when the other rows all have 2 vertices). It becomes evident that the case where $a$ equals 0 must follow a specific structure: $\begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \end{pmatrix}$, which signifies a row unique neighbor.

Moving on to this special row, assuming it intersects with column 2, our focus shifts similarly to $c_8, c_9$, and $c_{10}$. We initially note that $c_8 + c_9 + c_{10} > 0$; otherwise we would have $k \ge 3i$ since we use one extra vertex to fill one in these 3 columns. Assuming $c_8 \le c_9 \le c_{10}$. For $c_8 \neq 0$, we employ a structure and

induction: $\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{pmatrix}$. When $c_8 = 0, c_9 > 0$, on the

basis of column 3, we have $c_9 < i$ otherwise $k \ge 3i$; Consequently, $a_1 + a_2 + a_4 + b_4 + b_5 + b_7 + b_8 > 0$. However, for
every possible row, Lemmas 9 and 10 allow us to utilize induction. Similarly, for $c_8 = c_9 = 0$, we find that $a_1 + a_2 + a_4 + b_4 + b_5 + b_7 + b_8 + c_2 > 0$. Based on the two lemmas, the feasible scenario is only $c_2 \neq 0$. However, in this case, $k \ge 3i$, leading to a contradiction.

Next, we need to consider the case where the number of isolated row vertices is greater than 1. Importantly, $b_7 + b_8 + b_9 + b_{10} + c_5 + c_6 + c_7 + c_8 + c_9 + c_{10} > 0$, because the constraint $k < 3i$. Assuming that $b_q = 0$ for all $q = 7, 8, 9$, and 10, we can partition the remaining six numbers into three groups: $\{c_5, c_{10}\}$, $\{c_6, c_9\}$, and $\{c_7, c_8\}$; thus, by Lemma 10, there must be at least one $c_q = 0$ in each group. If fewer than three $c_q$s are greater than 0, then at least one column, apart from the first column, does not contain these vertices. This column has $\ge i$ vertices, yet all rows intersecting with this column also intersect with the first column. This contradicts the condition that $k < 3i$. When $3 c_q$s $> 0$ intersect all four columns,

the structure must be:
$$ \begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \end{pmatrix} $$
. However, this would also lead to $k \ge 3i$.

On the other hand, without loss of generality, let $b_7 \neq 0$. By

using the structure:
$$ \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \end{pmatrix} $$
and induction, we can determine that only $b_7 = 0$. Similarly, from column 5, we

have $c_7 + c_9 + c_{10} > 0$. Then the structure
$$ \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 \end{pmatrix} $$
implies that only one of these three is left. Suppose that $c_{10} > 0$. However, in this case, $k \ge 3i$.

0 columns: Let us assume that the numbers of rows with 4, 3, and 2 vertices are denoted by $a$, $b$, and $c$, respectively (according to Lemma 10, we exclude rows with 5 vertices). Therefore, we have $3a+2b+c=k$ and $4a+3b+2c \ge 5i$. This leads to the conclusion that $c \neq 0$; otherwise, $k+a+b \ge 2i$ implies $k > 2(a+b) > 2 \times 2i$, which contradicts the scenario. Without loss of generality, let $c_1$ be the largest among $c_1$ to $c_{10}$.

If $c_1 = 1$, we group $c$ rows into sets of three rows each. Using the second structure in Lemma 9, it becomes evident that any group possesses a row unique neighbor. Thus, we only need to prove $\lfloor \frac{c}{3} \rfloor \ge 3i - k$.

We prove that $3\lfloor \frac{c}{3} \rfloor \ge 9i - 3k$. For $c \ge 3$, we have $3\lfloor \frac{c}{3} \rfloor \ge c - 2$. From the first equation, $c = k - 3a - 2b$. Substitute it into the second equation, $2k \ge 5i + 2a + b$. Therefore, $c - 2 - 9i + 3k = k - 3a - 2b - 9i + 3k - 2 \ge i + a - 2 \ge 0$, implying $3\lfloor \frac{c}{3} \rfloor \ge 9i - 3k$. For $c < 3$, we have $k \ge 4i$, which is contradictory.

When $c_1 \ge 2$, it is similar to the 2-columns case: First, $c_8 + c_9 + c_{10} > 0$; otherwise, $k \ge 3i$. Assuming that $c_8 \le c_9 \le c_{10}$, for $c_8 \ge 0$ and $c_8 = 0$ but $c_9 > 0$, we apply the following first and second structures and induction:

$$ \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{pmatrix} $$

Finally, for $c_8 = c_9 = 0$, we similarly deduce $k \ge 3i$.

# 6 Conclusions

For every integer $4 \le d \le 11$, we provide an explicit construction of an infinite family of $\alpha$-unique neighbor 2d-regular expanders, which serves as a generalization of the well-known 6-regular ($d=3$) case. Additionally, for every integer $d \ge 12$, we provide a sufficient condition of the construction by showing the good property of the gadget.

A remaining question is the existence and construction of a $d$-good expander $G$ for $d \ge 12$. When $4 \le d \le 7$, $G$ can be $K_{d-2}$. For $8 \le d \le 11$, we can construct $G = H^c$, where $H$ is a $\lfloor \frac{d^2}{8} \rfloor$-vertex ($\lfloor \frac{d^2}{8} \rfloor - (d-3) - 1$)-regular graph. When $d$ is large, the explicit construction remains open. We conjecture that $H$ can be constructed for every $d \ge 12$ as follows. Notably, for values of $d$ within the range $8 \le d \le 11$, this construction method is also applied: First, $\lfloor \frac{d^2}{8} \rfloor$ vertices in the shape of regular polygons are arranged; next, we use the following one or more steps to construct the edges of $H$.

**Setp 1.** When the number of vertices is a multiple of 3, symmetrically construct some equilateral triangles such that each vertex lies on two edges.

**Setp 2.** When the number of vertices is a multiple of 4, symmetrically construct some squares such that each vertex lies on two edges.

**Setp 3.** When the number of vertices is even and the degrees are odd, construct a perfect matching.

**Setp 4.** Construct symmetric Hamiltonian cycles.

# Conflict of interest

The author declares that he has no conflict of interest.

# Biography

Weiqi Zhu is a master's graduate in Applied Mathematics at the School of Mathematical Sciences, University of Science and Technology of China. His research mainly focuses on the specific construction of expander graphs and their applications in coding theory.

# References

[1] Alon N, Capalbo M. Explicit unique-neighbor expanders. In: The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Vancouver, Canada: IEEE, 2002: 73-79.

[2] Becker O. Symmetric unique neighbor expanders and good LDPC codes. Discrete Applied Mathematics, 2016, 211: 211-216.

[3] Asherov R, Dinur I. Bipartite unique-neighbour expanders via Ramanujan graphs. arXiv: 2301.03072, 2023.

[4] Hsieh J-T, McKenzie T, Mohanty S, et al. Explicit two-sided unique-neighbor expanders. arXiv: 2302.01212, 2023.

[5] Capalbo M, Reingold O, Vadhan S, et al. Randomness conductors and constant-degree lossless expanders. In: STOC 2002: Proceedings
of the Thiry-Fourth Annual ACM Symposium on Theory of
Computing. Montreal, Canada: Association for Computing
Machinery, **2002**: 659–668.

[6] Golowich L. New explicit constant-degree lossless expanders. arXiv: 2306.07551, **2023**.

[7] Arora S, Leighton F T, Maggs B M. On-line algorithms for path selection in a nonblocking network. *SIAM Journal on Computing*, **1996**, *25* (3): 600–625.

[8] Ben-Sasson E, Viderman M. Tensor products of weakly smooth codes are robust. *Theory of Computing*, **2009**, *5*: 239–255.

[9] Dinur I, Sudan M, Wigderson A. Robust local testability of tensor products of LDPC codes. *Electron. Colloquium Comput. Complex.*, **2006**: Report No. 118.

[10] Tanner R. A recursive approach to low complexity codes. *IEEE Transactions on Information Theory*, **1981**, *27*(5): 533–547.

[11] Sipser M, Spielman D A. Expander codes. *IEEE Transactions on Information Theory*, **1996**, *42*(6): 1710–1722.

[12] Peleg D, Upfal E. The token distribution problem. *SIAM Journal on Computing*, **1989**, *18*(2): 229–243.

[13] Leverrier A, Zémor G. Quantum Tanner codes. In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). Denver, CO, USA: IEEE, **2022**: 872–883.

[14] Panteleev P, Kalachev G. Asymptotically good quantum and locally testable classical LDPC codes. In: STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Rome: Association for Computing Machinery, **2022**: 375–388.

[15] Dinur I, Evra S, Livne R, et al. Locally testable codes with constant rate, distance, and locality. In: STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing.

Rome: Association for Computing Machinery, **2022**: 357–374.

[16] Lin T-C, Hsieh M-H. Good quantum LDPC codes with linear time decoder from lossless expanders. arXiv: 2203.03581, **2022**.

[17] Hoory S, Linial N, Wigderson A. Expander graphs and their applications. *Bull. Amer. Math. Soc.*, **2006**, *43*: 439–562.

[18] Dodziuk J. Difference equations, isoperimetric inequality and transience of certain random walks. *Trans. Am. Math. Soc.*, **1984**, *284*(2): 787–794.

[19] Alon N. Eigenvalues and expanders. *Combinatorica*, **1986**, *6*: 83–96.

[20] Marcus A, Spielman D, Srivastava N. Interlacing families I: Bipartite Ramanujan graphs of all degrees. *Annals of Mathematics*, **2015**, *182*(1): 307–325.

[21] Lubotzky A, Phillips R, Sarnak P C. Ramanujan graphs. *Combinatorica*, **1988**, *8*: 261–277.

[22] Morgenstern M. Existence and explicit constructions of $q+1$ regular Ramanujan graphs for every prime power $q$. *J. Comb. Theory, Ser. B*, **1994**, *62*(1): 44–62.

[23] Kamber A, Kaufman T. Combinatorics via closed orbits: Number theoretic Ramanujan graphs are not unique neighbor expanders. In: STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Rome: Association for Computing Machinery, **2022**: 426–435.

[24] Cohen M B. Ramanujan graphs in polynomial time. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). New Brunswick, NJ, USA: IEEE, **2016**: 276–281.

[25] Kahale N. On the second eigenvalue and linear expansion of regular graphs. In: 33rd Annual Symposium on Foundations of Computer Science. Pittsburgh, PA, USA: IEEE, **1992**: 296–296.

# Appendix

In this section, we provide proofs for Lemma 5 and Lemma 8. The proofs of the remaining lemmas follow a similar approach, where we will only enumerate some unique neighbor cases used in the proofs without providing specific details.

**Proof of Lemma 5.** Suppose that there exists a case where it is impossible to obtain three row unique neighbors. Without loss of generality, let us assume that there is a vertex in column 1. We examine all possible scenarios of the remaining three columns, dividing them into four cases:

(i) No columns 2, 5, or 8:

In this scenario, the vertex in column 1 generates three row unique neighbors in columns 2, 5, and 8.

(ii) One of columns 2, 5, or 8:

If the remaining column is column 2, the vertex in column 1 will generate at least two row unique neighbors in columns 5 and 8. Thus, the remaining two columns must be columns 3 and 6; otherwise, column 2 would also generate a row unique neighbor, leading to a contradiction. However, this would cause a vertex in column 6 to generate a row-unique neighbor in column 7, resulting in another contradiction.

Similar contradictions arise when the remaining column is either column 5 or column 8.

(iii) Two of columns 2, 5, and 8:

Considering columns 2 and 5, the vertex in column 1 generates one row unique neighbor in column 8. The vertex in column 2 may have row unique neighbors in columns 3 and 6, and the vertex in column 5 may have row unique neighbors in columns 4 and 6. However, with three columns set, adding another column will yield at least three row unique neighbors. Similar contradictions are obtained when columns 2 and 8, and columns 5 and 8 are included.

(iv) Columns 2, 5, and 8:

Here, the vertex in column 2 generates row unique neighbors in columns 3 and 6, whereas the vertex in column 5 generates a row unique neighbor in column 6. This leads to contradictions.

All the examined scenarios lead to contradictions, confirming the lemma's validity.

For the proofs of Lemma 6 and Lemma 7, categorization is necessary on the basis of the number of vertices in each row and their row and column positions. Here, we won't list them one by one. Instead, we utilize Table A1 to display the possible row unique neighbors that different vertices in a row may produce, and provide an example for illustration.

Table A1 represents the required row subsets and their corresponding row unique neighbors, which can be translated to other subsets' row unique neighbors via translation. For instance, the row unique neighbors of 3 and 4 are the row unique neighbors corresponding to 1 and 2 plus 2 (mod 8), which are 5, 7, 8, and 2.

Here, we present the proof for one case of Lemma 6; the proofs for the other cases are similar, assuming one row with one
<table><caption>**Table A1.** Row unique neighbors for different vertex subsets of $V(C)$.</caption><thead><tr><th>Vertex subset</th><th>Row unique neighbors</th><th>Vertex subset</th><th>Row unique neighbors</th></tr></thead><tbody><tr><td>1</td><td>2,5,8</td><td>1,2,3</td><td>4,5,6,7,8</td></tr><tr><td>1,2</td><td>3,5,6,8</td><td>1,2,4</td><td>6</td></tr><tr><td>1,3</td><td>4,5,7,8</td><td>1,2,5</td><td>3,4,8</td></tr><tr><td>1,4</td><td>2,3</td><td>1,3,5</td><td>6,7,8</td></tr><tr><td>1,5</td><td>2,4,6,8</td><td>1,3,6</td><td>4,8</td></tr></tbody></table>

vertex and another row with two vertices. Therefore, it must be one of the following two structures:

$$ \begin{pmatrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}, \begin{pmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}. $$

If the conclusion is not valid, then in the first structure, assuming that the column containing the isolated row vertex is column 1, the remaining three columns must be columns 2, 5, and 8; otherwise, a contradiction will arise. However, regardless of which column among the three has a vertex, Table A1 indicates that there will be two row unique neighbors, leading to a contradiction.

For the second structure, similarly, assuming that the isolated row vertex is in column 1, the remaining three columns must be columns 2, 5, and 8. However, if there are vertices in columns 2 and 5, Table A1 shows two row unique neighbors in columns 3 and 4. The other cases yield similar contradictions.

Now let us prove Lemma 8. The proof of Lemma 9 is similar and requires the use of Table A1. Lemma 8 and Lemma 9 are based on the premise that the vertices in set $J$ are located in five columns.

**Proof of Lemma 8.** Lemma 8 consists of two cases:

$$ \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \end{pmatrix}, \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{pmatrix}. $$

To begin, let's assume the lemma is false.

**Case 1.** Suppose column 1 contains an isolated row vertex. Then, columns 2, 5, and 8 must be among the remaining four columns. If none of these columns contain isolated row vertices, one of columns 3, 4, 6, or 7 must have an isolated row vertex. However, since all five columns are determined, each possibility results in a row unique neighbor, leading to a contradiction.

**Case 2.** Continuing, let's assume an isolated row vertex is in column 1 without loss of generality. Therefore, at least two of columns 2, 5, and 8 must be among the remaining four columns. If only two columns are present, let's say columns 2 and 5, we already have a row unique neighbor from column 1. If column 2 contains an isolated row vertex, then columns 3 and 6 must be the remaining two columns; otherwise, it would lead to a contradiction. However, regardless of the location of the third isolated row vertex, it results in another row unique neighbor, contradicting our assumption. If both columns 2 and 5 do not contain isolated row vertices, it implies that two of columns 3, 4, 6, and 7 have isolated row vertices, each of which leads to a contradiction according to Table A1. The cases involving columns 2, 8, and columns 5, 8 are similar and lead to contradictions.

If columns 2, 5, and 8 are all among the remaining four columns, at least one of them contains an isolated row vertex, say column 2. Therefore, the last column must be either column 3 or column 6, or else there would be two row unique neighbors, leading to a contradiction. However, regardless of whether it's column 3 or column 6, considering the last isolated row vertex, any possibility still produces a row unique neighbor, resulting in a contradiction.

Thus, both cases lead to contradictions, proving the lemma.