# Is the following graph an expander graph?

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

It has the following adjacency matrix:

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

• It doesn’t make sense to speak of an expander graph—only of a family of graphs. Dec 20 '21 at 22:37
• Why not? Are there no definite graphs that satisfy the expansion property mentioned above? Dec 21 '21 at 2:12
• For given numerical values of the parameters, it does make sense. Dec 21 '21 at 5:15
• 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. Dec 21 '21 at 7:54