5
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.