Let's say we have the following bipartite-graph, denoted $G=(L,R,E)$:

enter image description here

It has the following adjacency matrix:

enter image description here

I am having problems decoding a received word from what I was told is an expander code that is based on this graph. The parameters are $\gamma = \frac{2}{7}$ and $\alpha=\frac{3}{2}$.

This really falls down to the definition of bipartite expanders. If we define $N(S)$ as the set of neighbors to vertices in $S$, I found two definitions:

  1. I was given the following definition: A Bipartite Expander $(n,m,D,\gamma,\alpha)$ is a $D$-regular bipartite graph $G=(L,R,E)$ with $|L|=n,|R|=m$, such that for all $S\subseteq L$, which satisfy $|S|\leq\gamma n$, we have $|N(S)|\geq \alpha |S|$.
  2. In Sipser-Spielman 1996 (link to paper) the definition involves general graphs and so the notation is a bit different, but it can be translated to bipartite graphs, and to the following definition: For all $S\subseteq L$, which satisfy $|S|\leq\gamma n$, we have $|N(S)|> \alpha |S|$.

I am not sure which definition is the correct one, or if it matters, but if it matters and Sipser-Spielman were correct, then $G$ is not a bipartite expander with respect to $\gamma = \frac{2}{7}$ and $\alpha=\frac{3}{2}$, because by choosing vertices $S={1,3}$, we get a neighbor set $N(S)$ of size $3\not > 3=\alpha |S|$.

  • $\begingroup$ It doesn’t make sense to speak of an expander graph—only of a family of graphs. $\endgroup$
    – Aryeh
    Dec 20 '21 at 22:37
  • $\begingroup$ Why not? Are there no definite graphs that satisfy the expansion property mentioned above? $\endgroup$ Dec 21 '21 at 2:12
  • $\begingroup$ For given numerical values of the parameters, it does make sense. $\endgroup$
    – Aryeh
    Dec 21 '21 at 5:15
  • $\begingroup$ It’s not a matter of which is “correct”. Just as with many other notions in TCS, different authors use slightly different conventions; this is quite normal. $\endgroup$ Dec 21 '21 at 7:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.