# Tagged Questions

An expander graph is a graph in which small sets of vertices have large 'boundary'. Ramanujan graphs are examples of expanders.

57 views

### Group of Lie type as expanders: explicit estimates

In a paper Finite simple groups as expanders by M. Kassabov, A. Lubotzky and N. Nikolov there is a theorem, stating that there exists $\varepsilon>0$ and $k\in\mathbb{N}$, such that for every non-...
55 views

### Does anyone have a reference for a proof of expansion for this construction?

http://people.seas.harvard.edu/~salil/pseudorandomness/expanders.pdf "Construction 4.26: p-cycles with inverse chords.... The proof of expansion relies on the “Selberg 3/16 Theorem” from number ...
190 views

### Non-Cayley expander graphs

When I search about expander graphs in google I see a lot of articles about expander Cayley graphs. Now my questions are as follows: Are all expander regular graphs are Cayley, or there is a special ...
304 views

102 views

### Expanding graphs from iterated zig-zag product

Let $\Gamma \, zz\, G$ denote the zig-zag product of graphs $\Gamma$ and $G$. Reingold, Vadhan, and Wigderson proved that the second largest eigenvalue of the normalized adjacency matrix of the zig-...
63 views

279 views

### Variant of an Expander graph: Probability that S random points cast a shadow/projection of size at most S/2 on each face of a cube.

Consider an integer cube of size $\sqrt{k} \times \sqrt{k} \times \sqrt{k}$, where $k$ is an asymptotically large perfect square number. Place k points in this cube at uniformly random locations, i.e.,...
398 views

### More expanders?

Having received several exhausting answers to my recent question about the expansion properties of a certain graph, I now wonder whether anything is known on the following graphs of a similar nature: ...
581 views

### An expander (?) graph

For a prime $p$, consider the graph on the vertex set ${\mathbb F}_p$, in which every vertex $z$ is adjacent to $z\pm 1$ and also to $z^{-1}$ (unless $z=0$). I was told that this graph is known to be ...
Fix a positive integer $k>0$. For $p>k$ a prime, let $A_p$ be a subset of the finite field $\mathbb{Z}/p\mathbb{Z}$ of size $k$ which contains a primitive element. Define $G_p$ to be the (di)...