# Questions tagged [expanders]

The tag has no usage guidance.

12 questions
Filter by
Sorted by
Tagged with
24 views

### Unique-neighbor expander

I want to solve Problem 4.10 from Randomness by Salil Vadhan. https://people.seas.harvard.edu/~salil/cs225/spring15/PS3.pdf Consider a bipartite expander $G$ with left degree $D$ so that every subset ...
19 views

### bipartite d regular expender explicit construction

I am looking for an explicit (and simple) construction of a d regular bi bipartite graph which is an expander. I searched the web and didn't find any sufficient answer. The only explicit graph I did ...
8 views

### Motivation behind the definition of order-$k$ (edge) expansion?

I'm trying to understand the motivation behind the idea of order-$k$ (edge) expansion for partitions of a graph, defined below: For simplicity, let's focus on $d$-regular graphs. The definitions I'm ...
30 views

### Random unbalanced bipartite graphs are good small set expanders

My question is about small set expansion properties of random unbalanced bipartite graphs. Fix a positive $\delta<1/2$, and a positive integers $n,m,d$. Let us call a bipartite graph $\mathcal{G}$...
96 views