A Ramsey-Sperner theorem (Q1070227): Difference between revisions

Suppose we color the elements of an n-element set in k colors. How many subsets can we take so that no one contains another and their difference is all one color? Graham and Chung have shown that one cannot take more than \(\sqrt{k}\) times the binomial coefficient C(n,[n/2]). In this paper this result is improved, for large n to roughly \(\sqrt{k\pi /4 \log k}\) times the binomial coefficient. A bound asymptotic to this is shown, and it is shown that one can come asymptotically close to it for any coloring. The construction lower bound is obtained by choosing all sets that lie within t/2 of half the members of each color set, whose sizes are congruent mod t, for appropriate t. The upper bound uses a probabilistic argument using symmetric chain decompositions of each color set. Only a proportion given by the inverse of the largest dimension of a block can lie in a difference-one-color collection. The result follows by bounding the number of sets in blocks for which this largest dimension is small.