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.
51
questions
-2
votes
0
answers
47
views
d-regular graphs and edge expanders
Show that there is no (n, d, ρ)-edge expander for ρ > 0.5
Is this statement even true?
My attempt: Let n = 2, then we can have 2 vertices, A and B. Let d = 1, therefore there is an edge between A ...
4
votes
1
answer
105
views
High-dimensional expanders through the lens of algebraic topology
High-dimensional expanders are used in a few areas of TCS (coding theory, sampling, probably some others). While I'm not too familiar with their usage, I know that in sampling they can be useful to ...
- 43
1
vote
0
answers
56
views
Constructing lossless conductors using zigzag product - a doubt
Reference - this survey: https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf
I am reading the section on constructing lossless conductors using a bipartite variant of zigzag product (section 10,...
- 91
2
votes
1
answer
45
views
Could an *implicitly* defined graph be a member of a *strongly-explicit* family of expanders?
There seems to be a slight difference in terminology among a couple of different traditions within theoretical computer science.
To have a quantum computer simulate the Hamiltonian evolution of $\exp(...
- 1,063
2
votes
0
answers
57
views
Is there a term for expander-like graphs that expand only large subsets?
I would like to find a bipartite graph $G(L, R)$ with the following properties/constraints:
For every subset $S \subseteq R$ with $\bf{|S| \geq \alpha |R|}$, its neighborhood $\Gamma(S)$ satisfies $|\...
- 21
2
votes
0
answers
105
views
Small set expansion and expanders
Given a graph $G=(V,E)$ on $n$ vertices and $0 \leq \delta \leq 1/2$, we can define the expansion of $G$ over small sets:
$$
h(G,\delta)= \min_{\vert S\vert \leq \delta n } \phi(S) \ ,
$$
with
$$\phi(...
- 41
5
votes
1
answer
210
views
Are all linear-rate and -distance classical linear codes expanding?
Consider a LDPC linear code defined as $\ker H$ for a $O(1)$ row- and column-sparse matrix $H \in \{0,1\}^{n \times r}$ with independent rows. Assume the code is linear-rate meaning $n - r = \Omega(n)$...
0
votes
0
answers
147
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 ...
4
votes
2
answers
198
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 ...
- 241
12
votes
1
answer
513
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 + ...
- 4,451
10
votes
0
answers
277
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}$...
- 101
5
votes
1
answer
202
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. ...
- 153
9
votes
0
answers
52
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 ...
- 101
4
votes
1
answer
232
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 ...
- 807
13
votes
1
answer
513
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 ...
- 807
2
votes
0
answers
67
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 ...
- 1,224
3
votes
1
answer
378
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 ...
- 143
12
votes
2
answers
757
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 ...
- 359
4
votes
0
answers
79
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 ...
- 453
5
votes
1
answer
201
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://...
- 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 ...
- 181
4
votes
1
answer
317
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 ...
- 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 - \...
- 271
0
votes
0
answers
260
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 $\...
12
votes
1
answer
515
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}$ ...
- 5,255
7
votes
0
answers
217
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 ...
- 1,251
3
votes
0
answers
183
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$, ...
- 9,438
1
vote
1
answer
232
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 ...
- 23
1
vote
1
answer
427
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 ...
- 666
3
votes
0
answers
110
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 ...
- 666
1
vote
0
answers
132
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?
- 735
25
votes
1
answer
817
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 ...
- 11k
7
votes
0
answers
230
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 ...
- 4,001
4
votes
0
answers
97
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 ...
- 41
11
votes
0
answers
147
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 {\...
- 119
8
votes
0
answers
187
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-...
- 3,758
9
votes
0
answers
180
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)-...
- 651
2
votes
1
answer
256
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 ...
6
votes
1
answer
271
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 ...
- 769
4
votes
0
answers
196
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 ...
- 1,224
21
votes
2
answers
583
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 $\...
14
votes
1
answer
2k
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} ~\...
- 775
14
votes
0
answers
498
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 ...
- 1,224
6
votes
1
answer
371
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 ...
5
votes
1
answer
622
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 ...
- 16.5k
8
votes
2
answers
553
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 ...
- 4,902
4
votes
2
answers
582
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 ...
- 16.5k
27
votes
2
answers
803
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|...
- 4,902
27
votes
2
answers
2k
views
Why are Ramanujan graphs 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?
- 11k
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 ...
- 20.8k