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.

Filter by
Sorted by
Tagged with
8 votes
0 answers
108 views

improved analysis of spectral gap of zigzag product?

I am reading the paper introducing zigzag products of expander graphs (https://arxiv.org/abs/math/0406038). The paper mentions the following observation in the introduction: Moreover, the variational ...
user avatar
  • 81
0 votes
0 answers
73 views

Is the following graph an expander graph?

Let's say we have the following bipartite-graph, denoted $G=(L,R,E)$: It has the following adjacency matrix: I am having problems decoding a received word from what I was told is an expander code ...
user avatar
4 votes
2 answers
183 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 ...
user avatar
12 votes
1 answer
473 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 + ...
user avatar
  • 4,323
9 votes
0 answers
232 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}$...
user avatar
5 votes
1 answer
181 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. ...
user avatar
  • 153
9 votes
0 answers
49 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 ...
user avatar
  • 101
4 votes
1 answer
220 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 ...
user avatar
13 votes
1 answer
477 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 ...
user avatar
2 votes
0 answers
65 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 ...
user avatar
  • 1,214
3 votes
1 answer
325 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 ...
user avatar
  • 143
12 votes
2 answers
715 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 ...
user avatar
  • 345
4 votes
0 answers
78 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 ...
user avatar
  • 453
5 votes
1 answer
194 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://...
user avatar
  • 644
7 votes
1 answer
1k 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 ...
user avatar
  • 181
4 votes
1 answer
291 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 ...
user avatar
  • 2,295
9 votes
1 answer
1k views

About the small set expansion conjecture

Given a graph $G=(V,E)$ and a $\delta > 0$ one wants to calculate $h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert } \phi(S)$. ($\phi(S) = \frac{ E(S,\bar{S}) }{d min \{\vert S \vert , n - \...
user avatar
  • 271
0 votes
0 answers
250 views

Spectral Gap in Expander Graphs

Does Spectral Gap remains same after removal of some edges from a Expander Graph ? Suppose we take a d-regular graph and remove m edges from it. For a $d$-regular graph We have $\lambda_1 = d$ and $\...
user avatar
12 votes
1 answer
465 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}$ ...
user avatar
  • 5,225
7 votes
0 answers
194 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 ...
user avatar
  • 1,241
3 votes
0 answers
180 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$, ...
user avatar
  • 9,348
1 vote
1 answer
221 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 ...
user avatar
1 vote
1 answer
403 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 ...
user avatar
  • 656
3 votes
0 answers
108 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 ...
user avatar
  • 656
1 vote
0 answers
129 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?
user avatar
  • 735
25 votes
1 answer
764 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 ...
user avatar
7 votes
0 answers
224 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 ...
user avatar
  • 3,993
4 votes
0 answers
94 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 ...
user avatar
  • 41
11 votes
0 answers
146 views

expansion with respect to p-norms for p other than 2

Suppose I have an $d$-regular expander graph with $n$ vertices, where the stochastic version of its adjacency matrix $A$ (with entries $1/d$ and zero) has second eigenvalue $\lambda$. Let $x \in {\...
user avatar
8 votes
0 answers
179 views

Lossless, constant-degree expanders that expand large sets

It is known how to construct "lossless" unbalanced bipartite expanders with the following properties: the bipartite graph has $n$ left vertices, $m$ right vertices, left-degree $D$, and for all left-...
user avatar
  • 3,698
9 votes
0 answers
179 views

Pseudorandom object yielding shrinkage in $\ell_p$ norm?

Extractors have the following property: For a random variable $X$ of min-entropy $k$ and a seed $Y$, denote the output of an $(k,\epsilon)$-extractor by $\mathrm{Ext}(X,Y)$. Then $\|\mathrm{Ext}(X,Y)-...
user avatar
  • 651
2 votes
1 answer
248 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 ...
user avatar
6 votes
1 answer
261 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 ...
user avatar
  • 757
4 votes
0 answers
192 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 ...
user avatar
  • 1,214
21 votes
2 answers
555 views

Are edge-vertex graphs of polytopes (decent) expanders?

This question is inspired by the polynomial Hirsch conjecture (PHC). Given a $n$-facet polytope $P$ in $\mathbb R^d$, is the spectral gap of its edge-vertex graph (call it $G$) lower bounded by $\...
user avatar
14 votes
1 answer
1k views

Conductance and diameter in regular graphs

Given an undirected, regular graph $G=(V,E)$, what is the relationship between its diameter - defined as the largest distance between two nodes - and its conductance, defined as $$\min_{S \subset V} ~\...
user avatar
  • 775
14 votes
0 answers
489 views

Bi-partite expander graphs

My question relates to bi-partite expander graphs, defined as bi-partite graphs on $n$ left vertices, $m$ right vertices, constant left-degree $k$, such that For any linear-sized subset $S$ of the ...
user avatar
  • 1,214
6 votes
1 answer
357 views

Error reduction with expanders and derandomization

In "standard" error reduction with an expander, if a randomize algorithm uses $n^d$ random bits, we need $n^d+O(n)$ random bits to achieve $2^{-O(n)}$ error probability. Now, if the algorithm has a ...
user avatar
5 votes
1 answer
604 views

Simple Constructions of Special Graph Families

Consider the following definition, taken from Chung's 1978 paper: An $(n, m)$-concentrator is a graph with $n$ input vertices and $m$ output vertices, $n \ge m$, having the property that, for ...
user avatar
  • 16.3k
7 votes
2 answers
525 views

Terminology for sparse cuts in graphs

I have found some ambiguity in how the graph parameters edge-expansion, uniform sparsest cut and conductance are defined and denoted. My questions are: what are the definitions that best match the ...
user avatar
4 votes
2 answers
556 views

Resources on Cryptographic Applications of Expander Graphs

I want to read papers on cryptography like How to Recycle Random Bits or Security Preserving Amplification of Hardness. They use random walks on expander graphs. I need a short introduction to the ...
user avatar
  • 16.3k
27 votes
2 answers
782 views

Papers to credit for spectral partitioning of graphs

If $G=(V,E)$ is an undirected $d$-regular graph and $S$ is a subset of the vertices of cardinality $\leq |V|/2$, call the edge expansion of $S$ the quantity $\phi(S) := \frac {Edges(S,V-S)}{d\cdot |S|...
user avatar
25 votes
2 answers
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?
user avatar
15 votes
2 answers
1k views

NP-hard problems on expander graphs?

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 ...
user avatar
24 votes
2 answers
881 views

Space efficient "industrial" unbalanced expanders

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)$-...
user avatar
  • 971