# Coloring of a graph representing the power set

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$$.

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.

• Any reference or proof for your claim? I dont get it at once Jul 15, 2022 at 5:21
• Two finite sets of the same cardinality are not comparable by strict inclusion. Jul 16, 2022 at 1:50

It's easy to prove that for k< n there is coloring such that maximum $$2^n-{n \choose \lfloor n/2 \rfloor}-{n \choose \lfloor n/2+1\rfloor}-{n \choose \lfloor n/2 -1 \rfloor}-...-{n \choose \lfloor n/2 +k/2 \rfloor}$$ vertexes has neighbour with the same color (we divide sets by their cardinalities and color the most numerous groups on different colours and rest sets on other color)
e.g for n=5, k=3 with coloring
blue: {1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}
red:{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5}
purple: rest
The answer is $$2^5-{5 \choose 3}-{5 \choose 2}$$.
However I'm not sure if that's the lower bound.

• If k is about epsilon*n then that's good enough to show that the ratio of the number of such vertices to the size of P tends to 1, as the relative sizes of the cardinality classes are given by Binomial(n, 1/2) and if we divide that by n it gets arbitrarily concentrated around 1/2 as n increases. Jul 7, 2022 at 12:46