# 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.

40
questions

**1**

vote

**1**answer

109 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 ...

**2**

votes

**0**answers

54 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.
...

**3**

votes

**1**answer

58 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 ...

**2**

votes

**0**answers

100 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 ...

**7**

votes

**1**answer

370 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$, ...

**3**

votes

**1**answer

176 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)$) ...

**1**

vote

**0**answers

125 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) = \...

**1**

vote

**0**answers

48 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

84 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 ...

**2**

votes

**2**answers

253 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$ ...

**1**

vote

**0**answers

121 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 ...

**-4**

votes

**2**answers

205 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

376 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**

vote

**1**answer

342 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 ...

**8**

votes

**1**answer

256 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 ...

**3**

votes

**0**answers

80 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$, ...

**4**

votes

**0**answers

69 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-...

**4**

votes

**2**answers

259 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 ...

**10**

votes

**2**answers

431 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 \...

**8**

votes

**1**answer

324 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$, ...

**2**

votes

**2**answers

188 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 ...

**1**

vote

**0**answers

128 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 ...

**2**

votes

**1**answer

110 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 ...

**0**

votes

**1**answer

141 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 ...

**7**

votes

**2**answers

420 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 ``...

**7**

votes

**1**answer

781 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 ...

**5**

votes

**3**answers

468 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 ...

**4**

votes

**0**answers

449 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 ...

**5**

votes

**1**answer

203 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 $\...

**3**

votes

**1**answer

172 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-...

**2**

votes

**0**answers

79 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, ...

**10**

votes

**0**answers

571 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, ...

**15**

votes

**3**answers

586 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 (...

**4**

votes

**0**answers

202 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**

votes

**1**answer

231 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( ...

**11**

votes

**1**answer

292 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.,...

**5**

votes

**1**answer

423 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:
...

**12**

votes

**2**answers

981 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 ...

**7**

votes

**1**answer

403 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)...

**20**

votes

**0**answers

865 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 ...