Questions tagged [expander-graphs]
An expander graph is a graph in which small sets of vertices have large 'boundary'. Ramanujan graphs are examples of expanders.
57
questions
20
votes
0
answers
1k
views
Could unramified Galois groups satisfy a version of property tau?
This is an experiment: there is a question I want to mention in an article I'm writing, and I am not sure it's a sensible question, so I will ask it here first, in the hopes that if it's insensible ...
- 19.1k
15
votes
3
answers
699
views
Embedding expanders in CAT(0) spaces
It is well-known that expanders are hard to embed into Hilbert (or $\ell^p$) spaces - any embedding of an expander with $n$ vertices has distortion $\Omega(\log n)$.
Can anyone provide a reference (...
- 2,429
13
votes
2
answers
1k
views
An expander (?) graph
For a prime $p$, consider the graph on the vertex set ${\mathbb F}_p$, in
which every vertex $z$ is adjacent to $z\pm 1$ and also to $z^{-1}$ (unless
$z=0$). I was told that this graph is known to be ...
- 22.6k
11
votes
2
answers
514
views
Groups without property (T) but all finite quotients are expanders
What is an example of a group $G$ which
1- is finitely generated by $S$,
2- does not have property (T),
3- admits infinitely many finite quotients which do not factor through an homomorphism $G \...
- 4,342
11
votes
1
answer
303
views
Variant of an Expander graph: Probability that S random points cast a shadow/projection of size at most S/2 on each face of a cube.
Consider an integer cube of size $\sqrt{k} \times \sqrt{k} \times \sqrt{k}$, where $k$ is an asymptotically large perfect square number. Place k points in this cube at uniformly random locations, i.e.,...
- 111
10
votes
4
answers
916
views
An introductory text on expanders
I am looking for a book that covers expander graphs rigorously. Preferably a book aimed at beginners.
- 885
10
votes
0
answers
615
views
Connections between Riemann hypothesis for curves over finite fields and Ramanujan property for graphs
this question relates to the beautiful construction of expander graphs using Cayley graphs of $PGL_2(\mathbb{F}_q)$, as exposited by Davidoff-Sarnak-Valette in their book, Elementary Number Theory, ...
- 6,043
9
votes
2
answers
442
views
Does it make sense to talk about expansion in irregular graphs?
Usually, one defines an expander graph to be a regular graph satisfying one of the following properties:
Either the edge-expansion is large, or
the spectral gap is large, or
the mixing time is at most ...
- 1,574
9
votes
1
answer
500
views
Are there two-sided $\varepsilon$-expanders with independent sets of size $(1-\varepsilon)n$?
Terry Tao's notes on expander graphs has the following exercise:
Exercise 13 Let $G$ be a $k$-regular graph on $n$ vertices that is a two-sided $\epsilon$-expander for some $n > k \geq 1$ and $\...
- 716
8
votes
3
answers
478
views
Where does $2\sqrt{d-1}$ come from in Ramanujan graphs?
Ramanujan graphs are the best spectral expanders: $\lambda_2 \le 2\sqrt{d-1}$. I'm looking for some intuition for this value $2\sqrt{d-1}$.
Friedman showed that every random $d$-regular graph ...
- 1,151
8
votes
1
answer
404
views
Cheeger Numbers for 3-regular Graphs
A student wanted a challenging Graph Theory programming project and I had
him try to determine the maximum value of the Cheeger number (isoperimetric number) among all 3-regular graphs of order $n$, ...
user71114
8
votes
1
answer
251
views
Do there exist "expanding" $1$-skeletons of simple $4$-polytopes?
Let $\{ G_n \}_{n \ge 1}$ be a sequence of graphs such that the number of vertices of $G_n$ tends to $\infty$ as $n \to \infty$. We say that $\{ G_n \}_{n \ge 1}$ is an expander family if
$\lambda_2( ...
- 7,675
8
votes
0
answers
258
views
Explicit constructions of Ramanujan graphs
I am trying to find a list of all the explicit constructions of Ramanujan graphs. By a Ramanujan graph I mean a $k$-regular multi-graph $G$ such that all the non-trivial eigenvalues $\lambda$ of the ...
- 234
7
votes
1
answer
1k
views
When are (Abelian) Cayley graphs also expanders?
I want to ask the question in two parts,
(1)
Is there some fundamental distinguishing property between Abelian and non-Abelian Cayley graphs? (say some specific proof technique which distinguishes ...
- 1,863
7
votes
2
answers
520
views
Constructing Ramanujan graphs from elliptic curves
Is there an exposition which explains how to do this step-by-step? (I see stray references and allusions to such a thing being possible but can't locate anything concretely)
Something to do with ``...
- 1,863
7
votes
1
answer
421
views
Constructing expanders in Z/pZ
Fix a positive integer $k>0$. For $p>k$ a prime, let $A_p$ be a subset of the finite field $\mathbb{Z}/p\mathbb{Z}$ of size $k$ which contains a primitive element.
Define $G_p$ to be the (di)...
- 11.1k
7
votes
1
answer
478
views
Understanding Gillman's proof of the Chernoff bound for expander graphs
My question is about the proof of Claim 1 in this paper: Gillman (1993).
At the end of the proof, the author says:
The matrix product $U^\top\sqrt{D^{-1}}(P+(\mathrm{e}^x-1)B(0)-\mu I)\sqrt{D}U$, ...
- 105
6
votes
5
answers
529
views
Existence of connected set with large edge boundary
Let $\Gamma=(V,E)$ be a finite connected graph.
Pretty standard notation. Given a set $S\subset V$, write $\Gamma|_S$ for the restriction of $\Gamma$ to $S$, i.e., the subgraph $(S,\{\{v,w\}\in E: v,w\...
- 19.1k
6
votes
1
answer
248
views
Arbitrary-dimensional expanders?
Rephrasing expansion (slightly). Consider the following slightly tweaked version of the usual definition of a (spectral) expander graph.
(We write a weighted graph as $(V,\beta)$, where the weight $\...
- 19.1k
5
votes
2
answers
590
views
Matching polynomials and Ramanujan graphs
Is it purely coincidental that the same number $2\sqrt{d-1}$ appears in these two following apparently disparate concepts?
A $d-$regular graph is said to be called Ramanujan if its adjacency ...
- 1,863
5
votes
1
answer
441
views
More expanders?
Having received several exhausting answers to my recent question about
the expansion properties of a certain graph, I now wonder whether anything is
known on the following graphs of a similar nature:
...
- 22.6k
4
votes
2
answers
291
views
Non-Cayley expander graphs
When I search about expander graphs in google I see a lot of articles about expander Cayley graphs. Now my questions are as follows:
Are all expander regular graphs are Cayley, or there is a special ...
4
votes
1
answer
317
views
Construction of graphs of high girth and chromatic number
Are there any concrete constructions of graphs of both high girth and chromatic number?
Of course there is the seminal paper of Erdős which proves the existence of such graphs via the probabilistic ...
- 128
4
votes
0
answers
73
views
Group of Lie type as expanders: explicit estimates
In a paper Finite simple groups as expanders by M. Kassabov, A. Lubotzky and N. Nikolov there is a theorem, stating that there exists $\varepsilon>0$ and $k\in\mathbb{N}$, such that for every non-...
- 3,081
4
votes
0
answers
580
views
The Bilu-Linial conjecture and Ramanujan graphs
The Bilu-Linial conjecture claims that every $d-$regular graph has a $2-$lift such that for the signing matrix has its eigenvalues between $[-2\sqrt{d-1},2\sqrt{d-1}]$ (the ``signing matrix" is the ...
- 1,863
4
votes
0
answers
249
views
What are the best bounds to date on the maximum girth of a cubic graph?
The girth of a graph is the length of its smallest cycle. Studying the maximum possible girth for a $k$-regular graph on $n$ vertices is a very well-studied problem.
In the 1988 paper "Ramanujan ...
- 7,675
3
votes
1
answer
134
views
Minimum size of regular graph with no short cycles
For $d \geq 3$ (degree) and $r \geq 3$ (radius), say that a $d$-regular (finite, simple, non-oriented) graph $G$ is $r$-almost-tree if it contains no cycle of length $\leq 2 r$: in other words, we ...
- 284
3
votes
1
answer
296
views
Spectral radius of Markov averaging operator on graphs
The definition of Markov operator which I am familiar with:
For a graph $G=(V,E)$, Markov's operator upon a function
$\varphi:V\rightarrow\mathbb{C}$ , $\varphi\in L^2(G,\nu)$ ($\nu(v):=\deg(v)$) ...
- 33
3
votes
1
answer
251
views
Sums over products over short paths in an expander graph
Let $\Gamma=(V,E)$ be an undirected graph of degree $d$. (Say $d$ is a large constant and the number of vertices $n=|V|$ is much larger.) Let $W_0$ be the space of functions $f:V\to \mathbb{C}$ with ...
- 19.1k
3
votes
1
answer
148
views
Reference request: maximal Cheeger constant for 3-regular graphs
Given a connected graph $G$, the Cheeger constant $h(G)$ (a.k.a. Cheeger number or isoperimetric number) roughly measures the "bottleneckedness" of $G$. See Wikipedia for the precise definition.
I ...
- 1,754
3
votes
1
answer
205
views
Expanding graphs from iterated zig-zag product
Let $\Gamma \, zz\, G$ denote the zig-zag product of graphs $\Gamma$ and $G$.
Reingold, Vadhan, and Wigderson proved that the second largest eigenvalue of the normalized adjacency matrix of the zig-...
3
votes
0
answers
173
views
Property $(T)$ for $\mathrm{SL}_2(\mathbb{Z}) \ltimes \mathbb{Z}^2$
(This is in part a request for references and in part a somewhat pedagogical question.)
I gave a course on expanders seven years ago, and I am giving a course on expanders again now. We will soon do ...
- 19.1k
3
votes
0
answers
178
views
Spectral norm and "operator norm" for hypergraphs
Consider a $d$-regular, $k$-uniform hypergraph: the elements $S$ of its set $E$ of edges are subsets of $V$ of size $k$, and each vertex $v\in V$ is in $d$ edges. We can then define its adjacency ...
- 19.1k
3
votes
0
answers
87
views
Analogues of relative property $(\tau)$ for Schreier graphs
Suppose I have an expanding family of Schreier graphs $Z_n=\text{Sch}(G_n,S_n,X_n)$ of groups $G_n=\underbrace{G\wr\ldots\wr G}_{\text{$n$ times}}$ acting on sets $S_n=S^n$ by generating sets $X_n$, ...
- 987
2
votes
2
answers
290
views
Random walk and isoperimetric constant
I assume that a result of the following kind is known, and I would really appreciate a reference for it... Or at least, some hints as to where to start looking.
Theorem(?): Let $\varepsilon>0$ ...
- 11.1k
2
votes
2
answers
154
views
Ramanujan graphs from varieties over finite fields
Let $G$ be a $d$-regular graph. Let $d= \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n \ge -d $ be the eigenvalues of the adjacency matrix of $G$, and set $\lambda = \max (|\lambda_2| , |\lambda_n|) $...
- 7,675
2
votes
1
answer
120
views
How many edges guarantee an expander?
Complete graphs are good expanders. Deleting few edges from a complete graph leaves a good expander. What's the proportion of edges that one needs to remove to make the graph a bad expander? Or, is ...
- 2,521
2
votes
1
answer
371
views
Expansion in hypergraphs
Is there a useful concept of expansion in hypergraphs, generalizing the concept for graphs (see: expander graphs)?
Of course, expander graphs can be characterized in several qualitatively equivalent ...
- 19.1k
2
votes
2
answers
215
views
How does one calculate/estimate/guarantee the girth of a non-Abelian Cayley graph?
This question is in reference to this other question,
Can someone point out references (or explain!) which give techniques of being able to prove for any Cayley graph this property of having a girth ...
- 545
2
votes
1
answer
180
views
Can connectivity be less than min cut/degree?
Suppose we have a graph with min-cut $\lambda$ and minimum degree $> \lambda$.
Is it possible for there to be a vertex that is at most $\lambda$-connected to every other vertex in the graph?
...
- 23
2
votes
0
answers
181
views
Expansion of random subgraphs of a bi-regular bipartite graph
Let $G = (L, R, E)$ be a bi-regular bipartite graph, with $|L|=n$ and $|R| = C \cdot n$, where $C$ is a large constant. Let $d$ be its (constant) right-degree.
We know $G$ is a good spectral expander. ...
- 215
2
votes
1
answer
151
views
Examples of 3-transitive expander family of Schreier graphs
What are examples of expander family of 3-transitive Schreier graphs?
Meaning for an action that is 3-transitive.
It is better to have an option for randomization. We know that choosing 2 elements ...
- 340
2
votes
0
answers
61
views
Expansion of product of simple Lie group
(a quite technical question if you want to skip).
I am looking at the paper Breuillard, Green, Guralnick, and Tao - Expansion in finite simple groups of Lie type; Specifically, proposition 8.4.
...
- 340
2
votes
0
answers
178
views
Expander graphs with many 4-cycles
The question is not strictly well-defined. But it goes like this:
Could you find an infinite family of graphs $G_i$, that are all $\epsilon$-expanders, but have many 4-cycles?
$\epsilon$ should ...
- 340
2
votes
0
answers
82
views
Asymptotic results in unbalanced left $d$-regular expander graphs
Let $U = [n]$ and $V = [m]$ be sets of nodes with $n > m$ and $E = U\times V$ be a set of edges. Let $\mathcal{N}(S)$ be the set of neighbors of a subset $S$ from $U$ or $V$.
Call a graph $G = (U, ...
- 399
1
vote
1
answer
581
views
How should one define expansion for irregular graphs?
This question is related to a previous question:
Does it make sense to talk about expansion in irregular graphs?
A family of expanders can be defined as a sequence of graphs whose spectral gap is ...
- 1,574
1
vote
1
answer
193
views
Do balls in expander graphs have small expansion?
Consider a $d$-regular infinite transitive expander graph $G$, and let $B_r$ be a ball of radius $r$ in $G$. Can one place any upper bounds on the expansion of $B_r$?
My intuition is that $B_r$ will ...
- 21
1
vote
1
answer
167
views
A particular argument in the review on expanders by Hoory-Linial-Wigderson
I am thinking about the third bullet point on page 455 here, http://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/
Can someone explain what is the argument there which seems to conclude ...
- 1,863
1
vote
0
answers
67
views
Does a two-sided expander remain an expander after removing vertices on one side?
Let $G=(L,R,E)$ be a bipartite d-regular $(\alpha, \varepsilon)$ 1-sided expander (from left to right), and let $\gamma \geq 1/d $ a constant. for every $v \in R$ let $r_v$ be an equivalence relation ...
- 19
1
vote
0
answers
249
views
Expander mixing lemma in combinatoric expanders
There is a well-known relation between combinatoric expansion and the gap between the first and the second largest eigenvalues (Dodziuk 1984)
:
$$ h(G) \le d \sqrt{2 (1 - \alpha)} $$
where
$$h(G) = \...
- 231