7
$\begingroup$

I have seen that there exists $d$-left regular bipartite graphs. 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.

$\endgroup$
19
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.