# Are all linear-rate and -distance classical linear codes expanding?

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.

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, 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 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$$?