# Tag Info

19

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 a directed graph with $n$ vertices ordered from left to right, where each vertex has an edge leading to the vertex to its right (except for the rightmost vertex,...

19

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 bipartite graph $G' = (V_1 \cup V_2, E')$ as follows: $V_1$ and $V_2$ are copies of $V$. Two vertices $v_1 \in V_1$ and $v_2 \in V_2$ are adjacted in $G'$ if and ...

11

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 Unique Games Conjecture, for every $\epsilon >0$ there exists $\delta>0$ so that it is NP-hard to determine whether in a graph $G$ it's the "YES" case where ...

10

The answer should be positive if your bounded-degree graph has both the property of having constant expansion and $\Omega( \log n)$ girth. The argument would be: start at a vertex, then for $n^\epsilon$ steps take a walk in which each step is chosen at random among those that don't take us back to where we were the step before. (So if the graph is $d$-...

10

For 0/1-polytopes (all vertex coordinates are 0 or 1), this is not known to be true. There is a conjecture by Mihail and Vazirani that the edge expansion of the graph of a 0/1-polytope is at least one. More information is described in a paper by Volker Kaibel. I should note two things. (1) For 0/1-polytopes, the Hirsch conjecture is true. (2) When ...

9

In general it is not true: Consider two dual- to cyclic d-polytopes with n facets each and merge them along a vertex. (This is the dual operation of gluing two polutops). The number of vertices will be like $n^{[d/2]}$ and the spectrual gap will be roughly 1 over this. (You can use d edges to separete the graph into two parts. I proved 1/poly(n) seperation ...

8

You can look at this survey by Hoory, Linial, and Wigderson [1]. Chapter 9, specifically (p. 508) is on the zigzag product. 9.The zig-zag product 9.1. Introduction 9.2. Construction of an expander family using zig-zag 9.3. Definition and analysis of the zig-zag product 9.4. Entropy analysis 9.5. An application to complexity theory: SL=L ...

8

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 vertex/edge expansion for sufficiently large sets. However, if you have tightly-knit communities within the network, then again you would expect low expansion. I'm ...

5

Regarding the last eigenvalue: The last eigenvalue $\lambda_n$ measures (roughly) how close is the graph to be bipartite. For example, $\lambda_n = -d$ if and only if the graph is bipartite (this is a fairly easy exercise). You can read more about it in Luca Trevisan's blog: http://lucatrevisan.wordpress.com/2008/06/13/max-cut-and-the-smallest-eigenvalue/ ...

4

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 formulation exists. For background, there are two popular versions of the SRL. They are: for any fixed $\varepsilon > 0$ and any $n$-node graph $G = (V, E)$, one ...

4

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 CL_G$ for $t$ the smallest real number such that $L_G \preceq tL_H$. (I.e. $t := \|L_H^{-1/2} L_G L_H^{-1/2}\|$ where the norm is the operator norm and inverses ...

4

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 particular, if you have only a small number of vertices involved in odd cycles, they would become a bottleneck in the double cover. But if all you need is ...

4

Here are some additional notes: lecture notes by Dieter van Melkebeek , notes from Luca Trevisan's course on expanders.

4

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 perhaps they found the original reference readable enough that they did not need to look at secondary literature. At least for teaching purposes it seems the ...

3

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. In Dwork's lecture notes as well, the condition required is that the expansion be $C/\delta$ for some constant $C$ (looking at a points in distance c is ...

2

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" construction of Marcus-Spielman-Srivastava effectively settles for the case of bipartite graphs what has been conjectured by Bilu and Linial to be true for all ...

2

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 is also an expander graph (because vertex and edge expansion are equivalent). Whether this holds for hypergraphs probably depends on which of the many notions ...

1

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.

Only top voted, non community-wiki answers of a minimum length are eligible