202311021611

Tags : Algorithmic Coding Theory

---

Bipartite Expander Graphs

Bipartite graphs: $G=(L,R,E)$

Given any $[n,k{]}_2$ code $C$ with parity check matrix $H$, we’ll call the bipartite graph $G_H$ with $A_{G_H}=H$. Given a bipartite graph $G=(L,R,E)$, with $|L|\ge |R|$, the corresponding code has parity check matrix $A_G$.

$G$ is sparse, each vertex in $L$ has at most a fixed number of neighbours in $R$,…

Left Regularity: A bipartite graph $G=(L,R,E)$ is $D-$left regular if every vertex in $L$ has degree exactly $D$.

Neighbour Set:

Unique Neighbour Set: For any left vertex set $S\subset L$, a vertex $u\in R$ is called a unique neighbour if it is adjacent to only one neighbour of $S$.

Bipartite Expander Graphs: An $(n,m,D,\gamma ,\alpha )$ bipartite expander is a $D-$left regular bipartite graph $G=(L,R,E)$, $|L|=n$, $|R|=m$, if for every $S\subset L$ with $|S|\le \gamma n,|N(S)|\ge \alpha |S|$.

We have existential results, but the natural question is, of course, how to construct expander graphs, which we will take as a black box for the purpose of this course.

Let $G$ be an $(n,n-k,D,\gamma ,D(1-ϵ))$ bipartite expander with $ϵ<\frac{1}{2}$, then $C(G)$ is an $[n,k,\gamma n]$ binary code. Proof: FTSOC, assume that $C(G)$ has distance at most $\gamma n$. $\exists$ a non zero codeword $\tilde{c}\in C(G)$, with $wt(\tilde{c})\le \gamma n$. Let $S$ be the set of non zero coordinates of $\tilde{c}$. $r\in U(S)$ $|U(S)|\ge D(1-2ϵ)|S|>0$, $ϵ<\frac{1}{2},|S|\ge 1$

---

References

Expander Graphs and Applications