# Questions tagged [expanders]

An expander is a sparse (low degree) graph with high "expansion," measured in one of several ways; typically akin to the minimum ratio of the size of a subgraph boundary to the subgraph's volume.

43 questions
Filter by
Sorted by
Tagged with
143 views

### reference request for construction of expanders

I'm looking for a good exposition of the explicit constructive proof of the existence of expander graph families due to Reingold Vadhan and Wigderson. Arora/Barak has a chapter on it, but i find it ...
393 views

### Deterministic error reduction, state-of-the-art?

Assume one has a randomized (BPP) algorithm $A$ using $r$ bits of randomness. Natural ways to amplify its probability of success to $1-\delta$, for any chosen $\delta>0$, are Independent runs + ...
144 views

### Random unbalanced bipartite graphs are good small set expanders

My question is about small set expansion properties of random unbalanced bipartite graphs. Fix a positive $\delta<1/2$, and a positive integers $n,m,d$. Let us call a bipartite graph $\mathcal{G}$...
119 views

### Expander Graph from Hypergraph

I came up with this problem while thinking about an optimizing compiler. Let $H$ be a hypergraph. From this we construct a graph $G_H$ as follows the vertices are the hyperedges of the hypergraph. ...
47 views

### *Simple* explicit constructions of bounded-degree expanders of “largish” spectral gap

I want to use for some work of mine bounded-degree (balanced bipartite) expanders with "decent" spectral gap. They need not be Ramanujan graphs. I'm ok with a degree that's a constant factor (ideally ...
180 views

### Can $L=SL$ be shown with the replacement product instead of the zig-zag product?

(This is a bit of follow-up to https://cstheory.stackexchange.com/posts/comments/93266 but is a distinct enough question I though it should be on its own.) In Omer Reingold's logspace USTCON ...
369 views

### What are the obstructions to extending $L=SL$ to $L=NL$?

Omer Reingold's proof that $L=SL$ gives an algorithm for USTCON (In an Undirected graph with special vertices $s$ and $t$, are they Connected?) using only logspace. The basic idea is to build an ...
59 views

### A random ensemble of sparse boundary operators

The following question arises from the study of quantum error correction, and high-dimensional expanders: Is there an algorithm that for given numbers $n>0,d≤n,r≤n$ samples uniformly a linear ...
206 views

### Existence of $d$-regular expander graph that can be represented as a bipartite graph

It is easy to derive from the definition of expander graphs that a $n$-vertex expander graph $G$ does not have a $o(n)$-vertex/edge separator. I was wondering if we can build a $d$-regular expander ...
585 views

### Are social networks typically good expanders?

I am interested in the combinatorial properties of social networks as graphs. People have looked at things such as the distribution of the degrees, the clustering coefficient and the compressibility ...
71 views

### Explicit Ramanujan graph families (Reference Request)

I am looking for a reference for explicit families of $d$-regular Ramanujan graphs for fixed $d.$ In particular, I am looking for a family of $d$-regular graphs such that the associated reversible ...
183 views

### About some possible optimality properties of Ramanujan graphs

The Ramanujan graphs are optimal from the Alon-Bopanna point of view but.. Is there any sense in which one can call Ramanujan graphs to be the "optimal" spectral sparsifiers? (Reference : http://...
719 views

### $d$-regular bipartite expander graph

I have seen that there exists $d$-left regular bipartite graphs. My question is do there exists $d$-regular bipartite expander graphs in which both the degree of the left and the right vertices is ...
230 views

### Special properties of bipartite expanders

It is well known that expanders, and often the special case of bipartite expanders, have found many uses in derandomization, coding, etc. However, I am curious if there are any special properties of ...
741 views

397 views

### Existence of long induced paths in expander graphs

Let's say that a graph family $\mathcal{F}$ has long induced paths if there is a constant $\epsilon > 0$ such that every graph $G$ in $\mathcal{F}$ contains an induced path on $|V(G)|^{\epsilon}$ ...
166 views

### Expansion of the union of two expander graphs

Suppose that $G$ and $H$ are both expander graphs on the same node set $V$ with a second largest eigenvalue of $\lambda_G$ resp. $\lambda_H$. Let $G\cup H$ be the graph on $V$ with the smallest set of ...
171 views

### Building a “balanced” universal set

A set of length $n$ binary vectors $\mathcal{U}=\{u_1,..,u_r\}$ is called $(n,k)$-universal if for all $S\subset [n], |S|=k$, $|\mathcal{U}_{|S}|=2^k$, i.e. for every subset of indices of size $k$, ...
205 views

### Expansion vs Sparsest cut

let $G=(V,E)$ and $S\subsetneq V$ then expansion of set $S$ is $$\alpha(S)=\frac{|E(S,\overline{S})|}{\min\{|S|,|\overline{S}|)\}}$$ where $\bar{S}=V\setminus{S}$ and $E(S,\bar{S})$ are edges ...
353 views

### Second eigenvalue and the last eigenvalue

Note : All eigenvalues that I would referring to below would of the adjacency matrix of the graph My question arises from having read about Expander Graphs from a few different sources. The most ...
102 views

### Delocalization of eigenvectors in Expanding Graphs

Given an adjacency matrix $A$, can we say something about whether the eigenvectors corresponding to its highest (or second-highest) eigenvalues are de-localized ? By de-localization I mean that ...
117 views

### Do expander graphs have the property that with high probability an s-t cut is size min{degree(s),degree(t)}?

If we want a specific example, then how about the Erdos-Renyi random graph?
565 views

### Regularity Lemma for Sparse Graphs

Szemeredi's Regularity Lemma says that every dense graph can be approximated as a union of $O(1)$ many bipartite expander graphs. More accurately, there's a partition of most vertices into $O(1)$ sets ...
211 views

### Minimum weight expander

Expander constructions given an expander which is a sub-graph of a complete graph. Sometimes we don't want to construct an arbitrary expander, want to find an expander inside another given graph. In a ...
93 views

### Explicit combinatorial construction minimizing intersection of sets

I'd like to know if anything is known about the following problem: Suppose we choose positive integer $t$ to be constant. Let $S = \{1,2,\dots,n\}$, where $n$ is sufficiently large. Consider a ...
144 views

231 views

### Combinatorial Expansion implies Algebraic Expansion

Arora/Barak, in Chapter 21, Theorem 21.9, Page 428, proves: Algebraic Expansion implies Combinatorial Expansion If G is a $(n, d, x)$ expander graph, then it is an $(n, d, (1-x)/2)$ edge ...
245 views

### Self-intersecting walk in expander graphs

Consider a random walk in an expander graph. How much time it typically takes to visit the same vertex twice. It seems to me that it should be something between $\sqrt{n}$ to $\sqrt{n}\log n$. Is ...
179 views

### Expansion of constant-size sets

My question refers to the expansion of constant size sets of an expander graph. Suppose we are given an expander graph with Cheeger constant $\alpha$. What can be said about the edge expansion of sets ...
484 views

1k views

### Why Ramanujan graphs are named after Ramanujan?

I recently taught expanders, and introduced the notion of Ramanujan graphs. Michael Forbes asked why they are called this way, and I had to admit I don't know. Anyone?
In a 2006 presentation titled EXPANDER GRAPHS - ARE THERE ANY MYSTERIES LEFT? , Nati Linial posed the following open problem: Which $NP$-hard computational problem on graph remain hard when ...
I am looking for unbalanced expanders that are "good" and "space-efficient". Specifically, a bipartite left-regular graph $G=(A,B,E)$, $|A|=n$, $|B|=m$, with left degree $d$ is a $(k,\epsilon)$-...