Vertex Ramsey problems in the hypercube.
SIAM Journal on Discrete Mathematics
If we 2-color the vertices of a large hypercube, what monochromatic substructures are we guaranteed to ﬁnd? Call a set S of vertices from Q_d, the d-dimensional hypercube, Ramsey if any 2-coloring of the vertices of Q_n, for n sufficiently large, contains a monochromatic copy of S. Ramsey’s theorem tells us that for any r ≥ 1 every 2-coloring of a sufficiently large r-uniform hypergraph will contain a large monochromatic clique (a complete subhypergraph): hence any set of vertices from Q_d that all have the same weight is Ramsey. A natural question to ask is: which sets S corresponding to unions of cliques of different weights from Q_d are Ramsey? The answer to this question depends on the number of cliques involved. In particular we determine which unions of two or three cliques are Ramsey and then show, using a probabilistic argument, that any nontrivial union of 39 or more cliques of different weights cannot be Ramsey. A key tool is a lemma which reduces questions concerning monochromatic conﬁgurations in the hypercube to questions about monochromatic translates of sets of integers
|Title:||Vertex Ramsey problems in the hypercube|
|Keywords:||Ramsey problem, Hypercube|
|UCL classification:||UCL > School of BEAMS
UCL > School of BEAMS > Faculty of Maths and Physical Sciences
Archive Staff Only