13
votes

Accepted

### Groups without property (T) but all finite quotients are expanders

I think your condition (4) is called "property ($\tau$)". (See Theorem 4.3.2 of Lubotzky's very nice book "Discrete Groups, Expanding Graphs and Invariant Measures".) An example is $G = \mathrm{SL}_2\...

- 3,861

10
votes

### An introductory text on expanders

The recent book of Emmanuel Kowalksi "An introduction to expander graphs" is very nicely written and covers a lot of material, from background to applications, with the description of the ...

- 800

10
votes

### An introductory text on expanders

Elementary Number Theory, Group Theory and Ramanujan Graphs (Giuliana Davidoff, Peter Sarnak, and Alain Valette, 2003) is intended to make the construction of expander graphs accessible to advanced ...

- 18.2k

9
votes

Accepted

### Cheeger Numbers for 3-regular Graphs

I did this calculation a few years ago (according to the timestamps on my programs).
Here is the summary of my results for $n=18$ (total of $41301$ graphs), with each line being the number of graphs ...

- 11.3k

9
votes

Accepted

### When are (Abelian) Cayley graphs also expanders?

To add to Anthony's comment, one can make an explicit connection between the large number of walks between vertices and the spectra of Abelian Cayley graphs. It turns out that constant-degree Abelian ...

- 431

8
votes

### Where does $2\sqrt{d-1}$ come from in Ramanujan graphs?

If you take an infinite regular tree of degree $d$ and fix one vertex $v$, then the number of closed walks of length $2k$ (there are none of odd length) starting at $v$ grows like $4^k(d-1)^k$ as $k\...

- 34.4k

8
votes

### Matching polynomials and Ramanujan graphs

One approach that goes some way to explaining this is through the path-tree of a graph. This is defined as follows. Choose a vertex $u$ in the graph $G$, The vertices of the path-tree $T(G,u)$ are the ...

- 11.8k

8
votes

Accepted

### Where does $2\sqrt{d-1}$ come from in Ramanujan graphs?

Yes, see this paper by Ram Murty. The basic point is that the sum of squares of the eigenvalues is the trace of the square of the adjacency matrix, which is equal to $d n.$

- 94k

8
votes

### An introductory text on expanders

One should mention Lubotzky's lovely book "Discrete groups, expanding graphs and invariant measures" (1994), I think the first book written on the subject, which shows how the problem of ...

- 10.7k

7
votes

### Groups without property (T) but all finite quotients are expanders

A bit late, but let me draw your attention to my first paper:
http://arxiv.org/abs/1005.4566
It shows that property (T) is not determined by the finite quotients, and gives in particular an answer ...

- 628

6
votes

### Where does $2\sqrt{d-1}$ come from in Ramanujan graphs?

Heuristically, an expander $G$ looks locally like the $d$-regular tree $T$. Let $r$ be a positive real number and let $f_x$ be the function on the vertices of $T$ given by $f_x(y) = r^{d(x,y)}$. We ...

- 141k

5
votes

Accepted

### Spectral radius of Markov averaging operator on graphs

The Markov averaging operator $M$ is also known as the transition matrix for simple random walk on the graph (often denoted by $P$). With this terminology, its spectral radius and spectral gap are ...

- 13k

5
votes

Accepted

### Minimum size of regular graph with no short cycles

The problem of determining the smallest regular graphs with degree $k$ and girth $g$ is normally known as the cage problem.
It has a large literature which is nicely summarised in the Dynamic Cage ...

- 11.3k

5
votes

### Non-Cayley expander graphs

The first existence proof (due to Mark Pinsker, in 1973) for expanders relied on the probabilistic method. As such these expanders are (with probability one) not Cayley graphs.
https://en.wikipedia....

- 20.4k

4
votes

### Matching polynomials and Ramanujan graphs

The moments of the adjacency matrix eigenvalues count closed walks in the graph, while the moments of the matching polynomial roots count tree-like closed walks. When the graph has few short cycles, ...

- 34.4k

4
votes

Accepted

### Random walk and isoperimetric constant

Given the proper keywords, a quick search gives
https://ocw.mit.edu/courses/mathematics/18-409-topics-in-theoretical-computer-science-an-algorithmists-toolkit-fall-2009/lecture-notes/...

- 4,244

4
votes

### Existence of connected set with large edge boundary

I think I have a counter-example to Statement B:
Start with a $K_r$ and connect every vertex to one vertex of a new $K_4$. This is the graph $\Gamma=(V,E)$, which has $5r$ vertices. Any set $S\subset ...

- 98

4
votes

Accepted

### Existence of connected set with large edge boundary

If I am not mistaken, then the following recursive construction disproves statement A:
Let $G_1$ consist of a $K_8$ and an additional vertex $r_1$ connected to half of the vertices of this $K_8$
For $...

- 2,446

3
votes

### Sums over products over short paths in an expander graph

I don't know your purpose, but here's some not-probably-sharp estimate that works for any $k$.
Put $\rho=\frac{1}{d}\|A|_{({\mathbb C}1)^\perp}\|$ and $\gamma$ to be the positive root of $t^2-\rho t -\...

- 8,951

3
votes

Accepted

### Does it make sense to talk about expansion in irregular graphs?

All the inequalities relating the three "definitions" of expander graphs are known in fully explicit forms, so that one can see what happens in first approximation for not completely regular graph (...

3
votes

Accepted

### Ramanujan graphs from varieties over finite fields

The assumptions mean that the eigenvalues of the Cayley graph are of the form $\sum_{x\in S} \psi (x)$ for $\psi \colon \mathbb F_q\to \mathbb C^\times$ an additive character, which is $\sum_{x\in \...

- 119k

3
votes

### Construction of graphs of high girth and chromatic number

Yes, there are many explicit constructions, although some of them are rather complicated. See this talk of Noga Alon, where he presents a very comprehensive history of the problem. Probably the ...

- 29.1k

2
votes

### How many edges guarantee an expander?

Depends on your definition of 'expansion', but the answer will always be to remove all edges across some cut, and you should make this as small as possible. So for example if you insist on all sets of ...

- 1,677

2
votes

### How should one define expansion for irregular graphs?

The answer rather depends what you want. It looks to me like you're interested in `two-sided' expansion, that is, you want to know that the graph in some sense looks random, as opposed to 'one-sided' ...

- 237

2
votes

### Non-Cayley expander graphs

The answer to your question is yes. The existence of such expanders which proved by probabilistic method, give us an optimistic view for search to find non-Cayley expanders. But, a first class of such ...

- 4,658

2
votes

### Is a single randomly generated graph sufficient to prove an almost all colorability result?

The answer to your main question is no. As monkeymaths has mentioned, there is no way to get a theorem about statements of the form 'almost all' from a single example. However, the computation you are ...

- 1,741

2
votes

Accepted

### Reference request: maximal Cheeger constant for 3-regular graphs

This is expander territory and someone will doubtless give a reference soon.
Meanwhile, here's a simple proof that $\liminf h_n \le 1$.
Consider a connected induced subgraph $H$ with $n_1,n_2,n_3$ ...

- 34.4k

2
votes

### An introductory text on expanders

I recommend "Elementary Number Theory, Group Theory and Ramanujan Graphs", quoted above in David Eppstein's answer.
There is also the following reference, that I know only a little bit but ...

- 321

1
vote

### Expansion in hypergraphs

There is a lot of work for simplicial complexes. One starting point was the work of Lubotzky--Samuels--Vishne on Ramanujan Complexes (with further work by First) and later Gromov introduced a ...

- 2,590

1
vote

### Random walk and isoperimetric constant

Some further intuitions: Let $A$ be the normalized adjacency matrix of $G$, let $A_L$ be the normalized adjacency matrix of $G$ w a self-loop at each vertex; so $A_L =\frac{d}{d+1}A +\frac{1}{d+1}I$ ...

- 1,032

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

expander-graphs × 54graph-theory × 33

spectral-graph-theory × 19

co.combinatorics × 18

gr.group-theory × 8

reference-request × 6

nt.number-theory × 5

pr.probability × 4

finite-groups × 4

mg.metric-geometry × 3

finite-fields × 3

extremal-graph-theory × 3

fa.functional-analysis × 2

rt.representation-theory × 2

algebraic-number-theory × 2

computational-complexity × 2

sp.spectral-theory × 2

geometric-group-theory × 2

eigenvalues × 2

graph-colorings × 2

random-walks × 2

random-graphs × 2

spanning-tree × 2

ag.algebraic-geometry × 1

oa.operator-algebras × 1