# 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
Filter by
Sorted by
Tagged with
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 ...
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. ...
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 ...
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 ...
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$, ...
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)$) ...
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) = \...
48 views

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$, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
203 views

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