MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In Gowers' paper on quasirandom groups, he suggests a spectral theory of bipartite graphs employ the singular values of the bipartite adjacency matrix. Accordingly, singular values appear to be a natural tool in the study of digraphs.

Let $G=(V,E)$ be a regular directed graph with adjacency matrix $A$. Using $\langle , \rangle$ for the standard inner product and setting $||x|| = \langle x, x \rangle ^{1/2}$ we define

$$ \lambda(G) = \max_{x \in {\mathbb R}^V : \langle x , 1 \rangle = 0} \frac{ ||Ax||}{||x||}. $$

Let ${\mathcal D}^n_d$ denote the class of all $d$-regular digraphs (all indegrees and outdegrees equal to $d$) with at least $n$ vertices. Then the adjacency matrix for every $G \in {\mathcal D}^n_d$ will have largest singular value equal to $d$ and second largest $\lambda(G)$. My question concerns bounding the quantity $$ \Lambda(d) = \lim_{n \rightarrow \infty} \inf_{G \in {\mathcal D}_d^n} \lambda(G). $$ Since the sum of the squares of the singular values from the adjacency matrix of a $d$-regular digraph with $n$ vertices will be $nd$, it follows that $\Lambda(d) \ge \sqrt{d}$. On the other hand, existing constructions of Ramanujan Graphs show that for certain values of $d$ we have $\Lambda(d) \le 2 \sqrt{d-1}$. Can anyone improve on these bounds?

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.