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

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Any reference or proof for your claim? I dont get it at once $\endgroup$
    – vidyarthi
    Commented Jul 15, 2022 at 5:21
  • 1
    $\begingroup$ Two finite sets of the same cardinality are not comparable by strict inclusion. $\endgroup$
    – Jan Kyncl
    Commented Jul 16, 2022 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.

Improve this answer
$\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
    Commented Jul 7, 2022 at 12:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .