0
$\begingroup$

This is essentially a repost of this math overflow post since it didn't get any reception.

Let $G = (V \cup C, \mathcal{E})$ be $(\gamma_V, \delta_A, \gamma_B, \delta_B)$-left-right-expanding with left degree bounded above by $d_V$ and right degree bounded above by $d_C$. I want to randomly select a subset $R \subset C$ and remove these vertices as well as any edges coming from $R$ from the graph. We then consider the induced subgraph $G' = (V, C \backslash R, \mathcal{E}')$.

The question is asking about the expansion properties of $G'$, i.e. is $G'$ still left-expanding, right-expanding, or both. Additionally, what can we say about the number and size of the connected components in $G'$? There has been work done on vertex percolation of $d$-regular expanders, but I can't see how this applies in the bipartite case.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.