2
$\begingroup$

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 in a situation 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 properties 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.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.