<p>Let's say we have the following bipartite-graph, denoted <span class="math-container">$G=(L,R,E)$</span>:</p>
<p><a href="https://i.sstatic.net/ztzIF.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ztzIF.png" alt="enter image description here" /></a></p>
<p>It has the following adjacency matrix:</p>
<p><a href="https://i.sstatic.net/1q7qi.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/1q7qi.png" alt="enter image description here" /></a></p>
<p>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 <span class="math-container">$\gamma = \frac{2}{7}$</span> and <span class="math-container">$\alpha=\frac{3}{2}$</span>.</p>
<p>This really falls down to the definition of bipartite expanders. If we define <span class="math-container">$N(S)$</span> as the set of neighbors to vertices in <span class="math-container">$S$</span>, I found two definitions:</p>
<ol>
<li>I was given the following definition: A Bipartite Expander <span class="math-container">$(n,m,D,\gamma,\alpha)$</span> is a <span class="math-container">$D$</span>-regular bipartite graph <span class="math-container">$G=(L,R,E)$</span> with <span class="math-container">$|L|=n,|R|=m$</span>, such that for all <span class="math-container">$S\subseteq L$</span>, which satisfy <span class="math-container">$|S|\leq\gamma n$</span>, we have <span class="math-container">$|N(S)|\geq \alpha |S|$</span>.</li>
<li>In Sipser-Spielman 1996 (<a href="https://www.cs.yale.edu/homes/spielman/Research/expanders.html" rel="nofollow noreferrer">link to paper</a>) 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 <span class="math-container">$S\subseteq L$</span>, which satisfy <span class="math-container">$|S|\leq\gamma n$</span>, we have <span class="math-container">$|N(S)|&gt; \alpha |S|$</span>.</li>
</ol>
<p>I am not sure which definition is the correct one, or if it matters, but if it matters and Sipser-Spielman were correct, then <span class="math-container">$G$</span> is not a bipartite expander with respect to <span class="math-container">$\gamma = \frac{2}{7}$</span> and <span class="math-container">$\alpha=\frac{3}{2}$</span>, because by choosing vertices <span class="math-container">$S={1,3}$</span>, we get a neighbor set <span class="math-container">$N(S)$</span> of size <span class="math-container">$3\not &gt; 3=\alpha |S|$</span>.</p>

CC BY-SA 4.0
2021-12-20T22:37:36.193Z
It doesn’t make sense to speak of an expander graph—only of a family of graphs.
Aryeh
CC BY-SA 4.0
2021-12-21T02:12:17.347Z
Why not? Are there no definite graphs that satisfy the expansion property mentioned above?
Louie_the_unsolver
CC BY-SA 4.0
2021-12-21T05:15:04.890Z
For given numerical values of the parameters, it does make sense.
Aryeh
CC BY-SA 4.0
2021-12-21T07:54:26.527Z
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.
Emil Jeřábek
<coding-theory><expanders><definitions>
Is the following graph an expander graph?
Louie_the_unsolver
# Is the following graph an expander graph?

(Asked by: username_0 on 2021-12-20)

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

[![enter image description here](https://i.sstatic.net/ztzIF.png)](https://i.sstatic.net/ztzIF.png)

It has the following adjacency matrix:

[![enter image description here](https://i.sstatic.net/1q7qi.png)](https://i.sstatic.net/1q7qi.png)

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](https://www.cs.yale.edu/homes/spielman/Research/expanders.html)) 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|$.

**Tags:** coding-theory, expanders, definitions

> **Comments:**
> **username_1**: It doesn’t make sense to speak of an expander graph—only of a family of graphs.  
> **username_0**: Why not? Are there no definite graphs that satisfy the expansion property mentioned above?  
> **username_1**: For given numerical values of the parameters, it does make sense.  
> **username_2**: 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.  

---

## 0 answers

