6
$\begingroup$

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$.
$\endgroup$
0

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Any reference or proof for your claim? I dont get it at once $\endgroup$
    – vidyarthi
    Jul 15 at 5:21
  • 1
    $\begingroup$ Two finite sets of the same cardinality are not comparable by strict inclusion. $\endgroup$
    – Jan Kyncl
    Jul 16 at 1:50
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Cong Chen
    Jul 7 at 12:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.