TITLE: An inequality involving the independence number of a $k$-regular graph and the smallest eigenvalue of its adjacency matrix
QUESTION [1 upvotes]: Let $G$ be a graph with $n$ vertices, and let $k=\lambda_1, ...,\lambda_n$ be the eigenvalues of the adjacency matrix of $A$ where $\lambda_1\geq \lambda_2\geq...\geq\lambda_n$. 
A subset $S$ of the vertices of $G$ is independent if no two vertices of $S$ are adjacent in $G$. The independence number $\alpha(G)$ of $G$ is the size of the largest independent subset of vertices.

Show that $$\alpha (G)\leq \frac{-n \lambda_n}{k -\lambda_n}.$$

REPLY [2 votes]: In the interest of full disclosure, I will largely be following the last few pages of these notes. Also, let $\alpha=\alpha(G)$.
The following claim can be shown by considering an orthonormal eigenvector basis of the real symmetric matrix $A$. I will use it without proof.
Claim. Let $A$ be a real symmetric matrix. The function 
$$R({\bf x}) = \frac{\langle {\bf x}, A {\bf x}\rangle}{\langle {\bf x}, {\bf x} \rangle}$$
 has maximum and minimum values $\lambda_1$ and $\lambda_n$ respectively, and the max and min occur at the corresponding eigenvectors ${\bf u}_1$ and ${\bf u}_n$. 
Let $S\subset V=\{v_1,\dots,v_n\}$ be the largest independent subset. Thus $\alpha=|S|$. Define ${\bf 1}_S$ to be the vector with entry $1$ in position $i$ if vertex $v_i\in S$ and with entry $0$ in position $i$ if vertex $v_i\notin S$. Define ${\bf 1}_n$ to be the vector with $n$ entries of $1$. Finally define ${\bf y} = n {\bf 1}_S - \alpha{\bf 1}_n$. In order to compute $R({\bf y})$, we need to make some observations first:

$\langle {\bf 1}_S,A{\bf 1}_S\rangle = \sum_{v_i,v_j\in S}A_{i,j}=0$,
$\langle {\bf 1}_S,{\bf 1}_n\rangle = \alpha$,
$A{\bf 1}_n = k{\bf 1}_n$ since $G$ is $k$-regular,
$\langle{\bf 1}_S,A{\bf 1}_n\rangle =\langle {\bf 1}_S,k{\bf 1}_n\rangle = k\alpha$,
Since $A$ is symmetric, $\langle{\bf 1}_n, A{\bf 1}_S\rangle=\langle A{\bf 1}_n,{\bf 1}_S\rangle = k\alpha$, and
$\langle{\bf 1}_n,A{\bf 1}_n\rangle = \langle {\bf 1}_n,k{\bf 1}_n\rangle = kn$.

Then
\begin{align*}
\langle {\bf y}, A {\bf y}\rangle = &\; \langle n{\bf 1}_S - \alpha{\bf 1}_n, n A{\bf 1}_S - \alpha A{\bf 1}_n\rangle\\
= &\; \langle n{\bf 1}_S,nA{\bf 1}_S\rangle - \langle n{\bf 1}_S,\alpha A{\bf 1}_n\rangle - \langle \alpha{\bf 1}_n,nA{\bf 1}_S\rangle + \langle \alpha{\bf 1}_n, \alpha A{\bf 1}_n\rangle\\
= & \; n^2 \langle {\bf 1}_S,A{\bf 1_S}\rangle - n\alpha\langle {\bf 1}_S,A {\bf 1}_n\rangle - n \alpha \langle{\bf 1}_n,A{\bf 1}_S\rangle + \alpha^2 \langle {\bf 1}_n,A{\bf 1}_n\rangle\\
= & \; 0 -nk\alpha^2 -nk\alpha^2 + nk\alpha^2\\
= & \; -nk\alpha^2.
\end{align*}
Also,
\begin{align*}
\langle {\bf y},{\bf y}\rangle = & \; \langle n{\bf 1}_S - \alpha{\bf 1}_n, n {\bf 1}_S - \alpha {\bf 1}_n\rangle\\
= & \;\langle n{\bf 1}_S,n{\bf 1}_S\rangle - \langle n{\bf 1}_S,\alpha {\bf 1}_n\rangle - \langle \alpha{\bf 1}_n,n{\bf 1}_S\rangle + \langle \alpha{\bf 1}_n, \alpha {\bf 1}_n\rangle\\
= & \; n^2 \alpha - n\alpha^2 - n\alpha^2 + n\alpha^2\\
= & \; \alpha n(n-\alpha).
\end{align*}
By our claim, we have that $\lambda_n \leq R({\bf y})$. Hence
\begin{align*}
\lambda_n \leq &\; R({\bf y})\\
= & \; \frac{\langle {\bf y},A{\bf y}\rangle}{\langle{\bf y},{\bf y}\rangle}\\
= & \; \frac{-nk\alpha^2}{\alpha n(n-\alpha)}\\
= & \; \frac{-k\alpha}{n-\alpha}.
\end{align*}
Solving this inequality for $\alpha$ yields
$$\alpha \leq \frac{-n\lambda_n}{k-\lambda_n}$$
as desired.
{"set_name": "stack_exchange", "score": 1, "question_id": 2579067}