# there exists a $c>0$ such that every $3$-regular bipartite graph is a $(2n,3,c)$-expander

Definition: A graph $$G = (V, E)$$ is called an $$(n, d, c)$$-expander if it has $$n$$ vertices, the maximum degree of a vertex is $$d$$, and, for every set of vertices $$W \subset V$$ of cardinality $$|W| \le n∕2$$, the inequality $$|N(W)| \ge c|W|$$ holds, where $$N(W)$$ denotes the set of all vertices in $$V \backslash W$$ adjacent to some vertex in $$W$$

By considering a random bipartite three-regular graph on $$2n$$ vertices obtained by picking three random permutations between the two color classes, prove that there is a $$c > 0$$ such that for every n there exists a $$(2n, 3, c)$$-expander.

This is question 9.6.1 from The Probabilistic Method and I am tempted to argue that for any $$c\le 1$$ the graph is trivially an expander.

In the question we are asked to consider the 3-regular bipartite graph obtained by taking the edge union of three permutations on $$[n]$$. A permutation is basically a perfect matching, therefore this construction contains a perfect matching and by Hall's theorem, every subset $$W\subset[n]$$ satistifes $$|N(W)|\ge|W|\ge c|W|$$, in particular for sets $$|W|\le 1/2$$.

(it is actually even simpler than that, no need for Hall's theorem: by 3-regularity $$|N(W)|<|W|$$ would imply $$3|N(W)|<3|W|$$ which in english means $$\#\{\text{outedges of } |N(W)|\} < \#\{\text{outedges of } |W|\}$$ which is obviously false).

But then these hints from this website point to a completely different approach. I would be interested in additional hints on how to compute the probability that $$N(W)<(1+\epsilon)|W|$$ for a given $$W\subset[n]$$ as they say in the hints.

And of course I'd like to know if taking $$c\le 1$$ is OK...

• So, why would it be obvious that it always holds for $c\leq 1$? Jan 17 at 9:47
• @ClementC. by what I wrote in the main paragraph, the neighborhood of $W$ has size at least $|W|$ Jan 17 at 9:56
• @HWalter: doesn't Hall's theorem imply that only for sets W contained entirely in one side of the bipartite (sub)graph? Jan 17 at 10:40
• Good point. Say $W=W_1\cup W_2$ is the union of $W_1\subset A$ and $W_2\subset B$, then $|N(W)|=|N(W_1)|+|N(W_2)|\ge |W_1|+|W_2|=|W|$ Jan 17 at 12:08
• As mentioned (among other things) in the current answer by Misha Lavrov, this is not quite true. If you don't count $W$ as part of the neighbours of $N(W)$ (and you shouldn't here), then what you just wrote isn't generally true. Jan 17 at 21:05

You might have been confused by the definition of $$N(W)$$. Usually this just means "the set of vertices adjacent to $$W$$". In the definition you've quoted from Alon and Spencer, we don't include vertices that are in $$W$$, which is the standard thing to do for measuring vertex expansion.

As a result, many cubic bipartite graphs are not expanders for $$c =1$$. For an extreme example, take two copies of any cubic bipartite graph, and let $$W$$ be the set of all vertices in one copy. Then $$|W| = \frac n2$$ and $$|N(W)| = 0$$, so the vertex expansion of such a graph is $$0$$.

For a family of connected examples with bad expansion, consider the prism graphs, such as the one below:

These are $$3$$-regular with $$n=2k$$ vertices, and when $$k$$ is even, they are bipartite. However, we can cut the prism in half vertically (if it is drawn as in the picture above) and take $$W$$ to be the vertices in one half. Then $$|W| = \frac n2$$ and $$|N(W)|=4$$, so at best this graph has vertex expansion $$\frac 8n$$, which goes to $$0$$ as $$n \to \infty$$.

So, no: not all bipartite cubic graphs are expanders.

The reason why you're seeing hints for proving that $$|N(W)| \ge (1+\epsilon)|W|$$ is not because $$c$$ can't be less than $$1$$. It's because in general, if $$W = W_1 \cup W_2$$ where $$W_1$$ is on one side of the bipartition and $$W_2$$ on the other, $$N(W) = (N(W_1) \setminus W_2) \cup (N(W_2) \setminus W_1)$$ which leads us to $$|N(W)| \ge (|N(W_1)| - |W_2|) + (|N(W_2)| - |W_1|) = |N(W_1)| + |N(W_2)| - |W|.$$ if we can show that $$|N(W_1)| \ge (1+\epsilon)|W_1|$$ and $$|N(W_2)| \ge (1+\epsilon)|W_2|$$, then we conclude that $$|N(W)| \ge \epsilon|W|$$. If this always holds, then we have an $$\epsilon$$-expander.

We have to be careful because $$|W| \le \frac12|V|$$ doesn't imply that $$|W_1| \le \frac12n$$ and $$|W_2| \le \frac12n$$. But we also have $$|N(W)| \ge |N(W_1)| - |W_2| \ge |W_1| - |W_2|$$, and similarly $$|N(W)| \ge |W_2| - |W_1|$$, so if the two sides of $$W$$ are too unbalanced, we get vertex expansion immediately. That tells us that $$|W_1|, |W_2| \le (\frac12 + \frac12\epsilon)n$$ in all hard cases.