UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Vertex Ramsey problems in the hypercube

Goldwasser, J; Talbot, J; (2012) Vertex Ramsey problems in the hypercube. SIAM Journal on Discrete Mathematics , 26 (2) 838 - 853.

Full text not available from this repository.

Abstract

If we 2-color the vertices of a large hypercube, what monochromatic substructures are we guaranteed to find? 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 configurations in the hypercube to questions about monochromatic translates of sets of integers

Type:Article
Title:Vertex Ramsey problems in the hypercube
Publisher version:http://epubs.siam.org/doi/pdf/10.1137/110832239
Keywords:Ramsey problem, Hypercube
UCL classification:UCL > School of BEAMS > Faculty of Maths and Physical Sciences > Mathematics

Archive Staff Only: edit this record