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.
18
votes
0answers
210 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 ...
12
votes
0answers
376 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 ...
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 ...
9
votes
0answers
138 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 ...
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 ...
7
votes
0answers
119 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 ...
4
votes
0answers
141 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 ...
3
votes
0answers
43 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
55 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?