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.
1
vote
1answer
101 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 ...
3
votes
0answers
47 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 delocalized ? By delocalization I mean that every ...
1
vote
0answers
60 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?
19
votes
0answers
217 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 ...
7
votes
0answers
122 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
votes
0answers
63 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 ...
11
votes
0answers
124 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 ...
8
votes
0answers
109 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 ...
9
votes
0answers
140 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 ...
2
votes
1answer
182 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
1answer
177 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 ...
4
votes
0answers
144 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 ...
19
votes
2answers
375 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 ...
11
votes
1answer
305 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} ...
12
votes
0answers
379 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 ...
6
votes
1answer
223 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
1answer
348 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 ...
6
votes
2answers
255 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
votes
2answers
334 views
Resources on Cryptographic Applications of Expander Graphs
I want to read papers on cryptography like
How to Recycle Random Bits
or Security Preserving Ampliļ¬cation of Hardness. They use random walks on expander graphs.
I need a short introduction to the ...
25
votes
2answers
490 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 ...
17
votes
2answers
742 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?
11
votes
2answers
707 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 ...
23
votes
2answers
668 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 ...
