<p>Really cool question! This is a little bit on the handwavy side of things, but here is my take. The conclusion is that we can show the existence of an <span class="math-container">$\Omega(1)$</span>-expander of size <span class="math-container">$\Theta(n)$</span>, let me know if you spot any error.</p>
<hr />
<p>So naively, the answer would be no, because one could use two copies of the same <span class="math-container">$[n,\Theta(n),\Theta(n)]$</span> code and obtain a non-connected graph that cannot be expander. But we can do better if we ask whether the graph <em>contains</em> a linear sized expander.</p>
<p>If you'll allow me I'll modify your setting a little bit (for LDPCs it will yield the same result up to constants anyway).</p>
<p>For a code <span class="math-container">$C$</span>, we consider the graph <span class="math-container">$G(H) = (V,E)$</span> where <span class="math-container">$V = [n]$</span> is identified with the bits, and there is an edge <span class="math-container">$(u,v) \in E$</span> if <span class="math-container">$u$</span> and <span class="math-container">$v$</span> are involved in the same check.</p>
<p>We can continue by defining some of the quantities we'll use. An (edge) separator is a subset <span class="math-container">$E' \subset E$</span> of edges such that its removal leaves two disconnected subgraphs <span class="math-container">$G_1 = (V_1, E_1), G_2 = (V_2, E_2)$</span> such that <span class="math-container">$|V_1|, |V_2| \leq \frac{2}{3}n$</span>. We can now define <span class="math-container">$\sigma_G$</span> the separation number of <span class="math-container">$G$</span>.</p>
<p><span class="math-container">$$
\sigma_G = \max_{G' \subset G} \ \min_{S \text{ is a separator of } G'} |S|
$$</span></p>
<p>We'll also need the Cheeger constant. For any <span class="math-container">$U \subset V$</span>, we define</p>
<p><span class="math-container">$$
\phi(U) = \frac{|\partial U|}{|U|}
$$</span></p>
<p>where <span class="math-container">$\partial U \subset E$</span> is the set of edges with exactly one endpoint in <span class="math-container">$U$</span>. The Cheeger constant <span class="math-container">$h_G$</span> is defined as</p>
<p><span class="math-container">$$
h_G = \min_{U \subset V, |U| \leq |V|/2 } \phi(U)
$$</span></p>
<p>Now using Lemma 12 of <a href="https://www.sciencedirect.com/sdfe/reader/pii/S0195669809002017/pdf" rel="nofollow noreferrer">this paper</a>, there exist universal constants <span class="math-container">$c_1, c_2$</span> such that if <span class="math-container">$\sigma_G \geq \epsilon n$</span>, then there exists a subgraph <span class="math-container">$G' \subset G$</span> with <span class="math-container">$|G'| \geq c_1 \epsilon n$</span> and <span class="math-container">$h_{G'} \geq c_2 \epsilon$</span>. In that paper they focus on vertex expansion, but their proof of this lemma can transparently be adapted to deal with edge expansion/edge separators.</p>
<p>On the code theoretic side, <a href="https://arxiv.org/abs/0909.5200" rel="nofollow noreferrer">that paper</a> shows that if the vertices <span class="math-container">$V$</span> of <span class="math-container">$G(H)$</span> can be partitioned into <span class="math-container">$A \sqcup B_1 \sqcup ... \sqcup B_l$</span> such that <span class="math-container">$\forall i, |B_i| &lt; d$</span> and there are no edges between <span class="math-container">$B_i$</span> and <span class="math-container">$B_j$</span> for any <span class="math-container">$i,j$</span>, then <span class="math-container">$k \leq |A|$</span>.</p>
<p>We now show that if <span class="math-container">$\sigma_G$</span> is small, then we can obtain a partition of <span class="math-container">$G(H)$</span> where both <span class="math-container">$A$</span> and the <span class="math-container">$B_i$</span>'s are small.
Find a separator <span class="math-container">$S_1$</span> of <span class="math-container">$G$</span>, by definition <span class="math-container">$|S_1| \leq \sigma_G$</span>, and the induced graph contains two disjoint subgraphs, each with size at most <span class="math-container">$\frac{2}{3}|V|$</span>. If we recursively do this process on each connected component <span class="math-container">$m$</span> times, each <span class="math-container">$B_i$</span> has size at most <span class="math-container">$(2/3)^m n$</span>, and we have removed at most <span class="math-container">$(1+ 2 + 4 + ... + 2^{m-1})\sigma_G = (2^m - 1) \sigma_G \leq 2^m \sigma_G$</span> edges. We define <span class="math-container">$A$</span> as the set of endpoints of these edges, and <span class="math-container">$B_i' \equiv B_i \setminus A$</span>, then we obtain <span class="math-container">$A \sqcup B'_0 \sqcup ... \sqcup B'_l$</span> such that <span class="math-container">$|A| \leq 2 \cdot 2^{m}\sigma_G $</span>, and <span class="math-container">$|B'_i| \leq |B_i| \leq (2/3)^m n$</span>.</p>
<p>It remains to pick an appropriate <span class="math-container">$m$</span>. We can always pick <span class="math-container">$m = \lceil \log_{2/3}(\frac{d-1}{n}) \rceil \leq \log_{2/3}(\frac{d-1}{n}) + 1$</span> to obtain <span class="math-container">$|B'_i| \leq (\frac{2}{3})^m n &lt; d$</span>. With a little bit more algebra this gives <span class="math-container">$m \leq \log_2\left((\frac{n}{d})^c\right) + 1$</span>, with <span class="math-container">$c = \log_2(3/2)^{-1} \approx 1.7$</span> .</p>
<p>We then get <span class="math-container">$k \leq 2 \cdot 2^m \sigma_G \leq 2^2 \cdot \left(\frac{n}{d}\right)^c \sigma_G$</span>. If we have <span class="math-container">$d \in \Omega(n)$</span>, then <span class="math-container">$k \in O(\sigma_G)$</span>. If <span class="math-container">$k \in \Omega(n)$</span>, this gives <span class="math-container">$\sigma_G \in \Omega(n)$</span> too. By Lemma 12, this implies the existence of a subgraph <span class="math-container">$G' \subset G$</span> such that <span class="math-container">$|G'| \in \Omega(n)$</span>, and <span class="math-container">$h_{G'} \in \Omega(1)$</span>.</p>
<p>I'm really curious to know if <span class="math-container">$c$</span> can be improved. Can we get <span class="math-container">$c = 1$</span>?</p>

CC BY-SA 4.0
2022-10-24T01:56:13.297Z
2022-11-02T15:38:47.133Z
2022-11-02T15:38:47.133Z
loplo
<p>Consider a LDPC linear code defined as <span class="math-container">$\ker H$</span> for a <span class="math-container">$O(1)$</span> row- and column-sparse matrix <span class="math-container">$H \in \{0,1\}^{n \times r}$</span> with independent rows. Assume the code is linear-rate meaning <span class="math-container">$n - r = \Omega(n)$</span> and linear-distance meaning <span class="math-container">$\min_{0 \neq x \in \ker H} |x| = \Omega(n)$</span> where <span class="math-container">$|\cdot|$</span> is the Hamming distance.</p>
<p>If we draw a bipartite graph corresponding to <span class="math-container">$H$</span> meaning <span class="math-container">$(V_1, V_2) = ([n],[r])$</span> with an edge <span class="math-container">$b \sim r$</span> if <span class="math-container">$H(b,r) = 1$</span>. Is it necessarily the case that the graph is expanding? I am interested in any definition of expansion but particularly edge expansion.</p>
<p>It is well known that the converse is true; expanding graphs generate such codes with high probability. Furthermore, we know that the statement is false if we don't assume linear-rate since the repetition code is linear-distance but not expanding.</p>

<coding-theory><expanders>
Are all linear-rate and -distance classical linear codes expanding?
Chinmay Nirkhe
# Are all linear-rate and -distance classical linear codes expanding?

(Asked by: username_0 on 2022-06-26)

Consider a LDPC linear code defined as $\ker H$ for a $O(1)$ row- and column-sparse matrix $H \in \{0,1\}^{n \times r}$ with independent rows. Assume the code is linear-rate meaning $n - r = \Omega(n)$ and linear-distance meaning $\min\_{0 \neq x \in \ker H} |x| = \Omega(n)$ where $|\cdot|$ is the Hamming distance.

If we draw a bipartite graph corresponding to $H$ meaning $(V\_1, V\_2) = ([n],[r])$ with an edge $b \sim r$ if $H(b,r) = 1$. Is it necessarily the case that the graph is expanding? I am interested in any definition of expansion but particularly edge expansion.

It is well known that the converse is true; expanding graphs generate such codes with high probability. Furthermore, we know that the statement is false if we don't assume linear-rate since the repetition code is linear-distance but not expanding.

**Tags:** coding-theory, expanders


---

## 1 answers

### Answer by username_1 on 2022-10-24. Score: 2

Really cool question! This is a little bit on the handwavy side of things, but here is my take. The conclusion is that we can show the existence of an $\Omega(1)$-expander of size $\Theta(n)$, let me know if you spot any error.

---

So naively, the answer would be no, because one could use two copies of the same $[n,\Theta(n),\Theta(n)]$ code and obtain a non-connected graph that cannot be expander. But we can do better if we ask whether the graph *contains* a linear sized expander.

If you'll allow me I'll modify your setting a little bit (for LDPCs it will yield the same result up to constants anyway).

For a code $C$, we consider the graph $G(H) = (V,E)$ where $V = [n]$ is identified with the bits, and there is an edge $(u,v) \in E$ if $u$ and $v$ are involved in the same check.

We can continue by defining some of the quantities we'll use. An (edge) separator is a subset $E' \subset E$ of edges such that its removal leaves two disconnected subgraphs $G\_1 = (V\_1, E\_1), G\_2 = (V\_2, E\_2)$ such that $|V\_1|, |V\_2| \leq \frac{2}{3}n$. We can now define $\sigma\_G$ the separation number of $G$.

$$
\sigma\_G = \max\_{G' \subset G} \ \min\_{S \text{ is a separator of } G'} |S|
$$

We'll also need the Cheeger constant. For any $U \subset V$, we define

$$
\phi(U) = \frac{|\partial U|}{|U|}
$$

where $\partial U \subset E$ is the set of edges with exactly one endpoint in $U$. The Cheeger constant $h\_G$ is defined as

$$
h\_G = \min\_{U \subset V, |U| \leq |V|/2 } \phi(U)
$$

Now using Lemma 12 of [this paper](https://www.sciencedirect.com/sdfe/reader/pii/S0195669809002017/pdf), there exist universal constants $c\_1, c\_2$ such that if $\sigma\_G \geq \epsilon n$, then there exists a subgraph $G' \subset G$ with $|G'| \geq c\_1 \epsilon n$ and $h\_{G'} \geq c\_2 \epsilon$. In that paper they focus on vertex expansion, but their proof of this lemma can transparently be adapted to deal with edge expansion/edge separators.

On the code theoretic side, [that paper](https://arxiv.org/abs/0909.5200) shows that if the vertices $V$ of $G(H)$ can be partitioned into $A \sqcup B\_1 \sqcup ... \sqcup B\_l$ such that $\forall i, |B\_i| < d$ and there are no edges between $B\_i$ and $B\_j$ for any $i,j$, then $k \leq |A|$.

We now show that if $\sigma\_G$ is small, then we can obtain a partition of $G(H)$ where both $A$ and the $B\_i$'s are small.
Find a separator $S\_1$ of $G$, by definition $|S\_1| \leq \sigma\_G$, and the induced graph contains two disjoint subgraphs, each with size at most $\frac{2}{3}|V|$. If we recursively do this process on each connected component $m$ times, each $B\_i$ has size at most $(2/3)^m n$, and we have removed at most $(1+ 2 + 4 + ... + 2^{m-1})\sigma\_G = (2^m - 1) \sigma\_G \leq 2^m \sigma\_G$ edges. We define $A$ as the set of endpoints of these edges, and $B\_i' \equiv B\_i \setminus A$, then we obtain $A \sqcup B'\_0 \sqcup ... \sqcup B'\_l$ such that $|A| \leq 2 \cdot 2^{m}\sigma\_G $, and $|B'\_i| \leq |B\_i| \leq (2/3)^m n$.

It remains to pick an appropriate $m$. We can always pick $m = \lceil \log\_{2/3}(\frac{d-1}{n}) \rceil \leq \log\_{2/3}(\frac{d-1}{n}) + 1$ to obtain $|B'\_i| \leq (\frac{2}{3})^m n < d$. With a little bit more algebra this gives $m \leq \log\_2\left((\frac{n}{d})^c\right) + 1$, with $c = \log\_2(3/2)^{-1} \approx 1.7$ .

We then get $k \leq 2 \cdot 2^m \sigma\_G \leq 2^2 \cdot \left(\frac{n}{d}\right)^c \sigma\_G$. If we have $d \in \Omega(n)$, then $k \in O(\sigma\_G)$. If $k \in \Omega(n)$, this gives $\sigma\_G \in \Omega(n)$ too. By Lemma 12, this implies the existence of a subgraph $G' \subset G$ such that $|G'| \in \Omega(n)$, and $h\_{G'} \in \Omega(1)$.

I'm really curious to know if $c$ can be improved. Can we get $c = 1$?


---

