Cfrgtkky

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

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