Return to Revisions

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.