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.



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.