# Tag Info

Accepted

• 34.4k

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

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

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

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

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

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

• 2,446

• 119k

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

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

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

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

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

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