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

coloringgraph theory

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!

Best Answer

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.

Related Question