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 ...
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 ...
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 ...
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 ...
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 ...
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