Show that in this graph there is a vertex with a neighbor in every color.

Question

Let $G = (V,E)$ be an $(n,d,\lambda)$-expander. That is, the second largest eigenvalue of its adjacency matrix is $\lambda$ and all its vertices have degree $d$. 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$.

I tried to show the result by contradiction. Indeed, if the result is false, then for any set $K$ of size $|K|=k$ containing one vertex from each color class and a $v\in V\setminus K$ we have \begin{equation} \sum\limits_{u\in K} \mathbb{1}_{uv \in E} = e(K,\{v\}) \leq k-1. \end{equation} I tried to sum this inequality over all $(n-k)(n/k)^k$ pairs $(v,K)$ and obtaining a contradiction with the expansion properties of $G$ but I got nowhere.

Probably I need to use the spectral expansion properties instead of the combinatorial expansion properties...

Any ideas? Thanks!

Answer 1

Recall the statement of Theorem 9.2.4 from "The Probabilistic Method" by Alon and Spencer (at least in my version):

Let $G=(V,E)$ be a $d$-regular graph on $n$ vertices, and suppose that the absolute value of each of its eigenvalues but the first is at most $\lambda$. For a given $v\in V$ and a subset $B$ of $V$, let $N(v)$ denote the set of all neighbors of $v$, and let $N_B(v)=N(v)\cap B$ denote the set of all neighbors of $v$ in $B$. Then, for every subset $B$ of cardinality $bn$ of $V$, $$\sum_{v\in V} (\vert N_B(v)\vert-bd)^2\leq \lambda^2 b(1-b)n. $$

Let $B_i$ be the set of vertices with the $i$th color, and in the notation of the theorem, $b=1/k$ for all $i=1,\ldots,k$. Applying the theorem for each $B=B_i$ and summing, $$ \sum_{v\in V}\sum_{i=1}^k (\vert N_{B_i}(v)\vert-d/k)^2\leq k\lambda^2 (1/k)((k-1)/k)n\leq \lambda^2 n. $$ This implies there exists some $v\in V$ such that $$ \sum_{i=1}^k(\vert N_{B_i}(v)\vert-d/k)^2\leq \lambda^2. $$ For this $v$, suppose there is a color $j$ where $v$ has no neighbors with that color, so that $\vert N_{B_j}(v)\vert=0$. Then $$ (\vert N_{B_j}(v)\vert-d/k)^2=d^2/k^2< \sum_{i=1}^k(\vert N_{B_i}(v)\vert-d/k)^2\leq \lambda^2 $$ (the strict inequality is because it is not possible for $N_{B_i}(v)=d/k$ for all other $i$, as that gives strictly fewer than $d$ neighbors for $v$). This immediately implies $d<k\lambda$, a contradiction.