# Tag Info

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

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

• 41
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