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