Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Could someone give me a hint for exercise 2.iii of these lecture notes? The exercise asks to show that a $k$-regular undirected graph (without loops) whose adjacency matrix $A$ has eigenvalues $k=\lambda_1(A) \geq \lambda_2(A) \geq \cdots \geq \lambda_n(A)$ satisfies $$\max(|\lambda_2(A)|, |\lambda_n(A)|) \geq \sqrt{k} - o(1).$$

share|cite|improve this question
What parameter is the little-o depending on? $k$? $n$? – Qiaochu Yuan Jan 1 '12 at 21:07
It goes to zero as $n \rightarrow \infty$ but $k$ is fixed. – robinson Jan 1 '12 at 21:07
From previous parts and the discussion before, you know $\lambda_1$, you know both $\sum \lambda_i$ and $\sum \lambda_i^2$, and you know that $\max(\lambda_2^2,\lambda_n^2)\geq \lambda_i$ for $i\neq 1$. Note that the minimum possible maximum will be achieved when every $|\lambda_i|^2$ ($i\neq 1$) is equal. – Aaron Jan 1 '12 at 22:13
Typo above. Should be $\max(\lambda_2^2,\lambda_n^2)\geq \lambda_i^2$. – Aaron Jan 1 '12 at 22:19
Ah, yes. Thanks! – robinson Jan 1 '12 at 22:21

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.