# Questions tagged [expanders]

The tag has no usage guidance.

13 questions
Filter by
Sorted by
Tagged with
18 views

### How to prove the existence of the spectral expander with the given parameteres?

I need to prove the existence of the $(1944, 144, 0.5)$ spectral expander. I tried to construct it using tensor product of the following graphs:  (1944, 144, 0.5) = (9^2, 9, 1/3) \otimes (24, 16, 0....
52 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 ...
21 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 ...
9 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}$...
102 views