The ACO Seminar (2010-2011)

We think of the vertices of the n-cube Qn as the set of all subsets of {1,2,3,...,n}, with two vertices joined by an edge if and only if one is contained in the other and their sizes differ by one. We say a subset S of the vertices of Qd is t-cube-Ramsey if for sufficiently large n, whenever the vertices of Qn are colored with t colors there must be a monochromatic copy of S embedded in the Qn. If all sets in S have the same size, then it follows immediately from Ramsey's theorem that S is t-cube-Ramsey, for all t. If S contains sets of different parities then it is not 2-cube-Ramsey, because if all odd size vertices are red and all even size vertices are blue, then there is no monochromatic copy of S. In general it is quite difficult to determine if a set S is t-cube-Ramsey.

A clique in Qd is the set of all subsets of a given size of a fixed subset of {1,2,...,d}. We determine which sets S which are the union of two or three vertex disjoint cliques are 2-cube-Ramsey. We use the Lovasz Local Lemma and a probabilistic argument to show that no set which is the union of at least 40 vertex disjoint cliques can be 2-cube-Ramsey.

We say a t-coloring of the vertices of Qd is layered if all the vertices of the same size get the same color. A key ingredient in our proofs is the following: For each positive integer d, there exists a positive integer N such that for each n greater than N, in every t-coloring of the vertices of Qn there is an embedded copy of Qd with a layered coloring.

This is joint work with John Talbot of University College, London.