<p>There is a simple construction: Take any $d$-regular <em>non-bipartite</em> expander $G=(V,E)$ - there are several constructions of those, e.g., Margulis, or the Zig-Zag construction. Now, turn it into a bipartite graph $G' = (V_1 \cup V_2, E')$ as follows: $V_1$ and $V_2$ are copies of $V$. Two vertices $v_1 \in V_1$ and $v_2 \in V_2$ are adjacted in $G'$ if and only if the corresponding vertices in $G$ are adjacted. The expansion of $G'$ follows from the expansion of $G$.</p>

<p>However, one thing that should be noted is that the expansion factor in all those constructions is at most $d/2$. We do not have bipartite expanders that have a better expansion factor and are balanced (i.e. have degree $d$ on both sides).</p>

CC BY-SA 3.0
2015-06-12T08:56:33.293Z
2015-06-13T00:20:25.607Z
2015-06-13T00:20:25.607Z
Or Meir
<p>I have seen that there exists <a href="http://theory.epfl.ch/courses/topicstcs/Lecture3.pdf">$d$-left regular bipartite graphs</a>. My question is do there exists $d$-regular bipartite expander graphs in which <em>both the degree of the left and the right vertices</em> is exactly equal to $d$? If yes, is there any constructive proof for such graphs and what is the expansion factor? Kindly provide a reference as well.</p>

<graph-theory><co.combinatorics><expanders>
$d$-regular bipartite expander graph
user1105
# $d$-regular bipartite expander graph

(Asked by: username_0 on 2015-06-11)

I have seen that there exists [$d$-left regular bipartite graphs](http://theory.epfl.ch/courses/topicstcs/Lecture3.pdf). My question is do there exists $d$-regular bipartite expander graphs in which *both the degree of the left and the right vertices* is exactly equal to $d$? If yes, is there any constructive proof for such graphs and what is the expansion factor? Kindly provide a reference as well.

**Tags:** graph-theory, co.combinatorics, expanders

---

## 1 answers

### Answer by username_1 on 2015-06-12. Score: 19 | Accepted answer

There is a simple construction: Take any $d$-regular *non-bipartite* expander $G=(V,E)$ - there are several constructions of those, e.g., Margulis, or the Zig-Zag construction. Now, turn it into a bipartite graph $G' = (V\_1 \cup V\_2, E')$ as follows: $V\_1$ and $V\_2$ are copies of $V$. Two vertices $v\_1 \in V\_1$ and $v\_2 \in V\_2$ are adjacted in $G'$ if and only if the corresponding vertices in $G$ are adjacted. The expansion of $G'$ follows from the expansion of $G$.

However, one thing that should be noted is that the expansion factor in all those constructions is at most $d/2$. We do not have bipartite expanders that have a better expansion factor and are balanced (i.e. have degree $d$ on both sides).


---

