19
votes
Accepted
What are the obstructions to extending $L=SL$ to $L=NL$?
The central problem is that, on directed graphs, even a truly random walk doesn't hit all the vertices in expected polynomial time, let alone a pseudorandom walk. The standard counterexample here is ...
- 306
19
votes
Accepted
$d$-regular bipartite expander graph
There is a simple construction: Take any $d$-regular non-bipartite expander $G=(V,E)$ - there are several constructions of those, e.g., Margulis, or the Zig-Zag construction. Now, turn it into a ...
- 5,290
11
votes
Accepted
About the small set expansion conjecture
I think the following should answer your questions, even though it's not exactly in the same order.
The original formulation of the small set expansion conjecture states that, analogously to the ...
- 3,741
9
votes
Accepted
Are social networks typically good expanders?
Social networks typically have many vertices with just one or two connections to the rest of the graph. Such vertices will typically lead to a bad spectral gap.
What you could hope for is good ...
- 878
8
votes
reference request for construction of expanders
You can look at this survey by Hoory, Linial, and Wigderson [1]. Chapter 9, specifically (p. 508) is on the zigzag product.
...
- 4,381
4
votes
About some possible optimality properties of Ramanujan graphs
At least among regular bi-partite graphs, Ramanujan graphs provide the optimal approximation of the complete bipartite graph. Let's say that a graph $H$ $C$-approximates a graph $G$ if $tL_H \preceq ...
- 18.1k
4
votes
Accepted
Existence of $d$-regular expander graph that can be represented as a bipartite graph
The obvious thing to try would be to convert a non-bipartite regular expander to a bipartite one using the bipartite double cover, which preserves regularity. But it might not preserve expansion; in ...
- 50.5k
4
votes
Regularity Lemma for Sparse Graphs
Below is a long-winded answer, but tl;dr in the general case there is no hope for such a formulation, but for many of the particular classes of sparse graphs that have regularity lemmas this ...
- 2,333
4
votes
reference request for construction of expanders
Here are some additional notes: lecture notes by Dieter van Melkebeek , notes from Luca Trevisan's course on expanders.
- 387
4
votes
Accepted
Can $L=SL$ be shown with the replacement product instead of the zig-zag product?
There is a paper already in 2005 that describes how to do this...
See https://people.seas.harvard.edu/~salil/research/derand_squaring-abs.html
I cannot say why people use zig-zag instead, other than ...
- 26.7k
3
votes
Accepted
Deterministic error reduction, state-of-the-art?
Doesn't van Melkebeek's lecture notes already give a $O(1/\delta)$ bound? The bound there is $\lambda$ at most $O(\sqrt{\delta})$ and we can get $\lambda = O(1/\sqrt{d})$ using existing constructions. ...
- 96
2
votes
Are all linear-rate and -distance classical linear codes expanding?
Really cool question! This is a little bit on the handwavy side of things, but here is my take. The conclusion is that we can show the existence of an $\Omega(1)$-expander of size $\Theta(n)$, let me ...
- 41
2
votes
Accepted
Expander Graph from Hypergraph
This is not an answer but is too long for a comment:
The graph you care about is called the line graph of the hypergraph. For usual graphs, it is well known that the line graph of an expander graph ...
- 824
2
votes
Special properties of bipartite expanders
Two things come to mind when I hear "bipartite expanders"
The only proof we have about existence of Ramanujan expanders at every size is through bipartite expanders. The "Interlacing families" ...
- 644
1
vote
Are social networks typically good expanders?
Power-law graphs are arguably good models for social network graphs.
This paper by Gkantsidis, Mihail, and Saberi shows that power-law graphs are expanders.
- 1,130
Only top scored, non community-wiki answers of a minimum length are eligible