# Questions tagged [expanders]

The tag has no usage guidance.

13 questions
Filter by
Sorted by
Tagged with
1 vote
23 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....
• 158
1 vote
74 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 ...
• 117
1 vote
37 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 ...
• 209
11 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 ...
• 557
33 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}$...
104 views

• 23
2k views

### How to practically construct regular expander graphs?

I need to construct d-regular expander graph for some small fixed d (like 3 or 4) of n vertices. What is the easiest method to do this in practice? Constructing a random d-regular graph, which is ...
• 683