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.
66 questions
0
votes
0
answers
29
views
Explicit Bound in Draganić's Hamiltonicity Result?
Earlier this year, Draganić et al published a remarkable piece of work that resolved Krivelevich and Sudakov's conjecture on the Hamiltonicity of expanders. Here's the abstract:
An n-vertex graph G ...
- 3,979
2
votes
1
answer
226
views
Expanders except for commutativity?
What would you call a graph that is an expander except for commutativity, in the following sense?
Say that, from every vertex, you have $d$ edges ($d$ large) labelled $x_1,\dotsc, x_d$. Say that your ...
- 20.1k
1
vote
0
answers
88
views
Ramanujan graph element in $\mathsf{PSL}(2, \mathbb{Z}_q)$
I am trying to follow the construction of the Ramanujan graph $X^{p, q}$ given in the paper 1. The first few steps of the construction proceed as follows:
Let $p$, $q$ be two unequal primes that are ...
- 333
4
votes
2
answers
219
views
Existence of disjoint expanders in a graph
Let $n$ be some sufficiently large positive integer and let $V$ be a set of $n$ vertices. Are there always disjoint sets of edges $E_1,\ldots, E_{\log n}$ such that $G_i = (V,E_i), \forall i = 1,\...
- 173
0
votes
0
answers
47
views
Strong notion of neighbors expanding
In the context of graphs, a $\Delta$-regular bipartite graph $G =(L, R, E)$ is called $(\beta, \varepsilon)$-left-expander if for any subset $S$ of $L$ at the size at most $|S| <\beta |L|$ the size ...
- 101
2
votes
0
answers
126
views
A reference for high girth expander graphs
I'm looking for a reference to the existence of family of constant (or bounded by constant) degree graphs which are both high-girth (meaning the ratio girth/diameter is uniformly bounded from below by ...
- 401
1
vote
0
answers
148
views
Exploring the Intersection of Expander Graphs, Number Theory, Representation Theory and Recent Computer Science Developments [closed]
I have a solid understanding of the basics of expander graphs and their properties and the recent development of High-Dimensional Expanders and their application to Random Walks, along with other ...
1
vote
0
answers
82
views
Clique complex of expander graphs simply connected?
Given an expander graph family (an injective sequence of graphs with uniformly bounded vertex degree and a Cheeger constant/Laplacian spectral gap uniformly bounded away from zero).
Can the ...
2
votes
1
answer
292
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 ...
- 31
1
vote
0
answers
72
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
10
votes
1
answer
523
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 ...
- 264
3
votes
0
answers
194
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 ...
- 20.1k
6
votes
5
answers
540
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\...
- 20.1k
6
votes
1
answer
260
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 $\...
- 20.1k
4
votes
1
answer
553
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 ...
- 132
2
votes
1
answer
255
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
2
answers
196
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,857
0
votes
1
answer
141
views
Is there a notion of "rapid" expansion for graphs?
I'll be as intuitive and hand-wavy as possible so as to get to what I am looking for.
Suppose we have a graph $G=(V,E)$. One notion of expansion, namely vertex expansion, can be intuitively described ...
- 949
10
votes
4
answers
1k
views
An introductory text on expanders
I am looking for a book that covers expander graphs rigorously. Preferably a book aimed at beginners.
- 883
3
votes
0
answers
199
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 ...
- 20.1k
2
votes
1
answer
473
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 ...
- 20.1k
0
votes
0
answers
70
views
(Weakly) connected sets with large (out-)boundary
Let $\Gamma=(V,E)$ be a connected undirected graph with n vertices such that every vertex has degree at least $4$. Now draw arrows on some of the edges, in such a way that the in-degree of every ...
- 20.1k
3
votes
1
answer
173
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
2
votes
0
answers
212
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. ...
- 225
3
votes
1
answer
255
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 ...
- 20.1k
2
votes
1
answer
172
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
63
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
4
votes
1
answer
213
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,804
2
votes
0
answers
202
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
7
votes
1
answer
497
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
3
votes
1
answer
341
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
1
vote
0
answers
271
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
1
vote
0
answers
118
views
Tight upper and lower bounds for unbalanced left-regular expander graphs
I am interested in finding the best expansion parameters for unbalanced left-regular expander graphs.
Specifically, fix $\delta\in(0,1/2)$, and a positive integer $d$. Let us call a bipartite graph $\...
0
votes
1
answer
99
views
Proof of reduction from random walks to martingales - why $T\le k$?
I'm trying to understand the proof of theorem 1.6 from the paper "A Matrix Expander Chernoff Bound".
In the proof they say: "Iterating this construction on the remainder a total of $T ≤ k$ times" and ...
- 105
2
votes
2
answers
312
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.2k
1
vote
0
answers
217
views
Short cycles in expander graphs
One often reads that expander graphs look locally like trees. In fact, there are many classes of expander graphs like random regular graphs or some Ramanujan graphs for which it has been shown that ...
-7
votes
2
answers
243
views
Is a single randomly generated graph sufficient to prove an almost all colorability result?
I have generated a single random 17th degree 100 vertex graph, with self-loops and multiple edges rerandomized out of existence, so the graph is highly 17 regular, and after long computation with a ...
8
votes
3
answers
498
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,161
1
vote
1
answer
671
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,633
10
votes
2
answers
502
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,633
3
votes
0
answers
99
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$, ...
- 997
4
votes
0
answers
74
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,186
4
votes
2
answers
312
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 ...
11
votes
2
answers
537
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,422
8
votes
1
answer
436
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
2
votes
2
answers
220
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 ...
- 617
1
vote
0
answers
157
views
Probabilistic proof for expander existence [closed]
I am new to probabilistic proofs and trying to understand them better. Apparently, a common probabilistic proof focuses on the existence of expanders (eg. vertex expanders).
I've been using the search ...
- 111
2
votes
1
answer
133
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,581
1
vote
1
answer
181
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,893
7
votes
2
answers
538
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,893