In chapter 1 of Lubotzky's "Discrete Groups, Expanding Graphs and Invariant Measures", remark 1.1.2, one definition of expanders is the following: if $n, k \in \mathbb{N}$ and $c \in \mathbb{R}_{> 0}$, an $(n, k, c)$-expander is a $k$-regular bipartite graph with $n$ inputs and $n$ outputs such that for any set $A$ of at most $\frac{n}{2}$ inputs we have $|\partial A| \geq (1 + c) |A|$, where $\partial A = \{ v : d(v, A) = 1 \}$.
The author goes on to say that any such graph admits a perfect matching by Hall's marriage lemma. Now I know that regular bipartite graphs always admit a perfect matching. However some other authors define expanders as graphs with degree bounded by $k$, instead of $k$-regular graphs. So I was wondering if the following is true:
Let $X$ be a bipartite graph with $n$ inputs and $n$ outputs and maximum degree $k$, such that for any subset $A$ of at most $\frac{n}{2}$ vertices we have $|\partial A| \geq (1 + c)|A|$, for some fixed $c > 0$. Does $X$ admit a perfect matching?
The fact that we have the expansion factor of $c$ only implies, in general, that $|\partial A| \geq |A| + 1$, and I don't know to what extent that may be helpful. But maybe for $n$ large enough in terms of $c, k$ it may have some nice implications…
Best Answer
Yes expansion on both sides does imply a perfect matching, if both sides of the graph have the same number of vertices--regularity is not needed.
Let us write the sides of $G$ as $S$ and $T$; both have $n$ vertices each. Let $A$ be a subset of more than $\frac{n}{2}$ vertices on one side $S$ of the graph. Then let $B= T \setminus N_G(A)$.
Now, $|N_G(A)|$ is at least $\frac{n}{2}$, as subsets on one side with $\frac{n}{2}$ vertices (in particular, any subset of $A$ with $\frac{n}{2}$ vertices) have at least $(1+c)$ times as many neighbours on the other side. So $B$ has no more than $\frac{n}{2}$ vertices and so $|N_G(B)| \geq (1+c)B$. Furthemore, $N_G(B)$ does not intersect $A$.
So writing $|A| = an$ and $|B|=bn$. Then on the one hand it follows that $|N_G(A)| = |T \setminus B| = (1-b)n$. On the other hand, as $N_G(B)$ does not intersect $A$ it follows that $(1+c)bn \leq n-an$. So putting these together gives $|N_G(A)| \geq \left(1-\frac{1-a}{1+c}\right)n$ $\geq an = |A|$.
So $|N_G(A)| \geq |A|$ for all $A \subseteq S$, and one can use the same line of reasoning to conclude that $N_G(L) \geq |L|$ for all $L \subseteq T$. So finish using Halls'.
The above argument does NOT hold if one side of $G$ has more vertices than the other; i.e., if $G$ is a concentrator. In that case (wrting $|S|=n$) the equation $|N_G(A)| = (1-b)n$ does not hold if $|T|$ is less than $n$.
ETA: And, per the comments below, there is not necessarily a perfect matching if there is expansion from only one side (and such bipartite graphs exist even when both sides have the same number $n$ vertices).