For a positive integer $n$, let $\mathcal{P}$ be the power set of $[n]$. Consider the graph $G$ with $\mathcal{P}$ as its vertex set, and, for $S\_1,S\_2 \in \mathcal{P}$, the edge $(S\_1,S\_2)$ exists iff $S\_1 \subset S\_2$.
(That is, $G$ is the transitive closure of the Hasse diagram of the "$\subset$" relation.)


**Question:** Suppose we can color the vertices of $G$ using $k$ colors. How many vertices $v$ are there such that $v$ has at least one neighbor that has the same color as $v$?


Remarks:


* Note that the question asks for a lower bound on the number of such vertices that holds no matter how $G$ is colored with $k$ colors.
* Obviously, the bound will depend on $k$. I'm mostly interested in large $k$, e.g., $k \approx \epsilon|\mathcal{P}|$, for some small constant $\epsilon>0$.



Coloring of a graph representing the power set
For $k\ge n+1$ there is a proper coloring of $G$ where each set in $\mathcal{P}$ is colored by its cardinality. Then no vertex $v$ has a neighbor with the same color.


