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.

Filter by
Sorted by
Tagged with
1 vote
0 answers
125 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 ...
total dependent random choice's user avatar
1 vote
0 answers
50 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 ...
Florentin Münch's user avatar
2 votes
1 answer
234 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 ...
user3521569's user avatar
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 ...
Ron  Tubman's user avatar
8 votes
0 answers
306 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 ...
richarddedekind's user avatar
3 votes
0 answers
178 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 ...
H A Helfgott's user avatar
  • 19.3k
6 votes
5 answers
532 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\...
H A Helfgott's user avatar
  • 19.3k
6 votes
1 answer
252 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 $\...
H A Helfgott's user avatar
  • 19.3k
4 votes
1 answer
392 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 ...
Felix Schröder's user avatar
2 votes
1 answer
197 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? ...
vayu251's user avatar
  • 23
2 votes
2 answers
172 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|) $...
Matthew Kahle's user avatar
0 votes
1 answer
135 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 ...
BharatRam's user avatar
  • 939
10 votes
4 answers
976 views

An introductory text on expanders

I am looking for a book that covers expander graphs rigorously. Preferably a book aimed at beginners.
mahdi meisami's user avatar
3 votes
0 answers
182 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 ...
H A Helfgott's user avatar
  • 19.3k
2 votes
1 answer
393 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 ...
H A Helfgott's user avatar
  • 19.3k
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 ...
H A Helfgott's user avatar
  • 19.3k
3 votes
1 answer
136 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 ...
Rémi Peyre's user avatar
2 votes
0 answers
191 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. ...
Daniel86's user avatar
  • 215
3 votes
1 answer
252 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 ...
H A Helfgott's user avatar
  • 19.3k
2 votes
1 answer
158 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 ...
user2679290's user avatar
2 votes
0 answers
62 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. ...
user2679290's user avatar
3 votes
1 answer
172 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 ...
Xin Nie's user avatar
  • 1,764
2 votes
0 answers
184 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 ...
user2679290's user avatar
7 votes
1 answer
482 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$, ...
Ella Sharakanski's user avatar
3 votes
1 answer
307 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)$) ...
user140823's user avatar
1 vote
0 answers
256 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) = \...
Artur Riazanov's user avatar
1 vote
0 answers
99 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 $\...
curiousperson's user avatar
0 votes
1 answer
97 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 ...
Ella Sharakanski's user avatar
2 votes
2 answers
294 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$ ...
Nick Gill's user avatar
  • 11.2k
1 vote
0 answers
194 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 ...
Hendrik Fichtenberger's user avatar
-5 votes
2 answers
236 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 ...
daniel pehoushek's user avatar
8 votes
3 answers
481 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 ...
Xiaoyu He's user avatar
  • 1,151
1 vote
1 answer
602 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 ...
Zur Luria's user avatar
  • 1,613
9 votes
2 answers
457 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 ...
Zur Luria's user avatar
  • 1,613
3 votes
0 answers
91 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$, ...
amakelov's user avatar
  • 987
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-...
Andrei Smolensky's user avatar
4 votes
2 answers
298 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 ...
Meysam Ghahramani's user avatar
11 votes
2 answers
524 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 \...
ARG's user avatar
  • 4,342
8 votes
1 answer
417 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$, ...
user avatar
2 votes
2 answers
216 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 ...
Student's user avatar
  • 555
1 vote
0 answers
151 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 ...
stefanbschneider's user avatar
2 votes
1 answer
122 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 ...
Hao Chen's user avatar
  • 2,541
1 vote
1 answer
175 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 ...
user6818's user avatar
  • 1,883
7 votes
2 answers
524 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 ``...
user6818's user avatar
  • 1,883
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 ...
user6818's user avatar
  • 1,883
5 votes
2 answers
602 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 ...
user6818's user avatar
  • 1,883
4 votes
0 answers
589 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 ...
user6818's user avatar
  • 1,883
10 votes
1 answer
548 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 $\...
JeremyKun's user avatar
  • 726
3 votes
1 answer
207 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-...
Ievgen Bondarenko's user avatar
2 votes
0 answers
83 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, ...
rodms's user avatar
  • 399