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

  • $\begingroup$ So, why would it be obvious that it always holds for $c\leq 1$? $\endgroup$
    – Clement C.
    Jan 17 at 9:47
  • $\begingroup$ @ClementC. by what I wrote in the main paragraph, the neighborhood of $W$ has size at least $|W|$ $\endgroup$
    – H. Walter
    Jan 17 at 9:56
  • $\begingroup$ @HWalter: doesn't Hall's theorem imply that only for sets W contained entirely in one side of the bipartite (sub)graph? $\endgroup$
    – Clement C.
    Jan 17 at 10:40
  • $\begingroup$ 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|$ $\endgroup$
    – H. Walter
    Jan 17 at 12:08
  • 1
    $\begingroup$ 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. $\endgroup$
    – Clement C.
    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:

enter image description here

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.


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.