# co.combinatorics – Expansion of random subgraphs

Let $$G = (L,R,E)$$ be a bi-regular bipartite graph, with $$|L|=n$$ and $$|R| = C cdot n$$, where $$C$$ is a large constant. Let $$d$$ be its (constant) right-degree.
We know $$G$$ is a good spectral expander. Say, for concreteness, that its normalized second eigenvalue is roughly $$frac{1}{sqrt{d}}$$, so in particular we have good vertex expansion from both sides.

I wish to pick a random subset $$S subseteq R$$ of cardinality, say, $$frac{n}{4}$$. Let’s think of $$d >4$$, so we are at a situtation in which with high probability, $$Gamma(S)$$ covers nearly all of $$L$$. Let $$G’ = (Gamma(S),S,E’)$$ be the induced subgraph, where we keep only the edges that come out of $$S$$. Note that $$G’$$ is still $$d$$ right-regular, but is no longer left-regular.

The question is: What can we say about the expansion propetries of a typical $$S$$? Specifically, what is the expected vertex expansion from left to right? I don’t expect it to be as good, but is it only mildly good, say that each small enough set $$X subseteq Gamma(S)$$ is mapped to a set of size $$frac{|X|}{2}$$? (note that it’s actually a good expansion, as the “imbalanceness” is roughly $$frac{1}{4}$$). A simple union-bound does not seem to give anything meaningful.