# Questions tagged [expanders]

The tag has no usage guidance.

14 questions
Filter by
Sorted by
Tagged with
31 views

335 views

### Amplifying the correctness of $\mathsf{RP}$ algorithms using expander graphs

A graph $G = (V, E)$ is called an $(n, d, \varepsilon)$-expander if the graph has $n$ vertices, maximum degree $d$, and satisfies the following expansion property: for every subset $W\subset V$ such ...
372 views

### Random Graph is a good expander

If a (n,d) random graph is a n-vertex graph defined as : Choose d random permutations $\pi_1 \ldots \pi_d$, from [n] to [n]. Take edge (u,v) if $v = \pi_i(u)$ for some i. I am trying to prove that, ...
712 views

### Relationship between graph expansion and conductance

I'm quite confused about the exact relationship between the expansion of a graph and its conductance. My first question is: Could someone point me to a reference that discusses both of these notions? ...
54 views

### Union of 2 expander graphs [closed]

Suppose that $G$ and $H$ are both expander graphs on the same node set with a second largest eigenvalue of $\lambda_G$ resp. $\lambda_H$. What can be said about the expansion of graph $G \cup H$? In ...
130 views

### Electrical resistance of expander graphs

Let $G$ be a $d$-regular expander graph. What is the electrical resistance of $G$? Is it a constant independent of the number of nodes $n$ once $d$ is large enough? If not, can we give matching upper ...