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.

learn more… | top users | synonyms

5
votes
1answer
180 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 ...
4
votes
1answer
135 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 ...
0
votes
0answers
37 views

Calculate Upper bound on second largest Eigenvalue?

Suppose we have a line graph on $(n+1)$ vertices with vertex set $ \{ 0,1, \ldots, n \} $ and edge set $\{(k,k+1)\},$ $k \in \{0,\ldots, n-1\}$. How to calculate upper bound on second largest ...
8
votes
1answer
293 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 - ...
0
votes
0answers
119 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
1answer
323 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}$ ...
7
votes
0answers
104 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 ...
3
votes
0answers
118 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$, ...
0
votes
1answer
130 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 ...
1
vote
1answer
236 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
92 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 ...
1
vote
0answers
104 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?
22
votes
0answers
362 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
174 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
84 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
137 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
132 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
160 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
204 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
212 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
167 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 ...
20
votes
2answers
431 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 ...
13
votes
1answer
553 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} ...
13
votes
0answers
419 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
260 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
416 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
297 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
441 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 ...
27
votes
2answers
593 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 ...
24
votes
2answers
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?
14
votes
2answers
794 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
729 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 ...