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

57 questions
Filter by
Sorted by
Tagged with
1 vote
151 views

### Do balls in expander graphs have small expansion?

Consider a $d$-regular infinite transitive expander graph $G$, and let $B_r$ be a ball of radius $r$ in $G$. Can one place any upper bounds on the expansion of $B_r$? My intuition is that $B_r$ will ...
1 vote
67 views

### Does a two-sided expander remain an expander after removing vertices on one side?

Let $G=(L,R,E)$ be a bipartite d-regular $(\alpha, \varepsilon)$ 1-sided expander (from left to right), and let $\gamma \geq 1/d$ a constant. for every $v \in R$ let $r_v$ be an equivalence relation ...
248 views

### Explicit constructions of Ramanujan graphs

I am trying to find a list of all the explicit constructions of Ramanujan graphs. By a Ramanujan graph I mean a $k$-regular multi-graph $G$ such that all the non-trivial eigenvalues $\lambda$ of the ...
172 views

### Property $(T)$ for $\mathrm{SL}_2(\mathbb{Z}) \ltimes \mathbb{Z}^2$

(This is in part a request for references and in part a somewhat pedagogical question.) I gave a course on expanders seven years ago, and I am giving a course on expanders again now. We will soon do ...
529 views

305 views

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

Are there any concrete constructions of graphs of both high girth and chromatic number? Of course there is the seminal paper of Erdős which proves the existence of such graphs via the probabilistic ...
178 views

### Can connectivity be less than min cut/degree?

Suppose we have a graph with min-cut $\lambda$ and minimum degree $> \lambda$. Is it possible for there to be a vertex that is at most $\lambda$-connected to every other vertex in the graph? ...
151 views

### Ramanujan graphs from varieties over finite fields

Let $G$ be a $d$-regular graph. Let $d= \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n \ge -d$ be the eigenvalues of the adjacency matrix of $G$, and set $\lambda = \max (|\lambda_2| , |\lambda_n|)$...
129 views

### Is there a notion of "rapid" expansion for graphs?

I'll be as intuitive and hand-wavy as possible so as to get to what I am looking for. Suppose we have a graph $G=(V,E)$. One notion of expansion, namely vertex expansion, can be intuitively described ...
906 views

### An introductory text on expanders

I am looking for a book that covers expander graphs rigorously. Preferably a book aimed at beginners.
178 views

### Spectral norm and "operator norm" for hypergraphs

Consider a $d$-regular, $k$-uniform hypergraph: the elements $S$ of its set $E$ of edges are subsets of $V$ of size $k$, and each vertex $v\in V$ is in $d$ edges. We can then define its adjacency ...
368 views

### Expansion in hypergraphs

Is there a useful concept of expansion in hypergraphs, generalizing the concept for graphs (see: expander graphs)? Of course, expander graphs can be characterized in several qualitatively equivalent ...
70 views

### (Weakly) connected sets with large (out-)boundary

Let $\Gamma=(V,E)$ be a connected undirected graph with n vertices such that every vertex has degree at least $4$. Now draw arrows on some of the edges, in such a way that the in-degree of every ...
132 views

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

For $d \geq 3$ (degree) and $r \geq 3$ (radius), say that a $d$-regular (finite, simple, non-oriented) graph $G$ is $r$-almost-tree if it contains no cycle of length $\leq 2 r$: in other words, we ...
179 views

### Expansion of random subgraphs of a bi-regular bipartite graph

Let $G = (L, R, E)$ be a bi-regular bipartite graph, with $|L|=n$ and $|R| = C \cdot n$, where $C$ is a large constant. Let $d$ be its (constant) right-degree. We know $G$ is a good spectral expander. ...
251 views

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

Let $\Gamma=(V,E)$ be an undirected graph of degree $d$. (Say $d$ is a large constant and the number of vertices $n=|V|$ is much larger.) Let $W_0$ be the space of functions $f:V\to \mathbb{C}$ with ...
151 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 ...
60 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. ...
143 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 ...
178 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 ...
478 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$, ...
295 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
247 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
90 views

395 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$, ... 215 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
149 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 ...
120 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 ...
1 vote
166 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 ...
517 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 ...
1k 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 ...
588 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 ...
578 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 ...
498 views

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