(This is problem 9.2 from Alon and Spencer's The Probabilistic Method)
Let $G = (V,E)$ be an $(n,d,\lambda)$-graph, suppose $n$ is divisible by $k$, and let $C:V \to \{1,2,\ldots,k\}$ be a coloring of $V$ by $k$ colors, so that each color appears precisely $n/k$ times. Prove that there is a vertex of $G$ which has a neighbor of each of the $k$ colors, provided $k\lambda \leq d$.
The Notation: Just to interpret some notation: an $(n,d,\lambda)$-graph means that $G$ has $n$ vertices with degree $d$---i.e. every vertex has exactly $d$ neighbors. The $\lambda$ part means that the adjacency matrix for $G$ has second-largest eigenvalue equal to $\lambda$; since $G$ is a regular graph, the vector $(1,1,\ldots,1)^T$ is an eigenvector corresponding to $d$, the largest eigenvalue. Thus, the second-largest eigenvalue characterizes the graph more than the largest does (once we know the degree).
Discussion: Let $A$ be the adjacency matrix for $G$; if we order the vertices so that the colors are blocked together, then we can write $A$ as $$ A = \left( \begin{array}{c|c|c|c} A_{11} & A_{12} & \cdots & A_{1k} \\ \hline A_{21} & A_{22} & \cdots & A_{2k} \\ \hline \vdots & \vdots & \ddots & \vdots \\ \hline A_{k1} & A_{k2} & \cdots & A_{kk} \end{array}\right) $$ i.e. to break it up into submatrices of size $n/k \times n/k$, where the first $n/k$ rows correspond to vertices of the first color, and so on. The problem asks to prove that once column (or row) has at least one $1$ in every block. The typical approach to these kind of problems is to let $v = (1,1\ldots, 1)^T$; now, cleverly choose some vector $x$ s.t. $\langle v,x \rangle = 0$. Then we have $\langle Ax, Ax \rangle \leq \lambda^2 \langle x, x\rangle$; if $x$ is chosen well, then this inequality gives the desired result. I haven't been able to choose such an $x$ well.
I haven't made any progress on this problem, despite spending quite a bit of time on it. Any help, or hints, would be greatly appreciated. Since this can be thought of strictly as a linear algebra problem, I have also tagged it as such.