A Ramsey-type result for the hypercube

Noga Alon, Radoš Radoičić, Benny Sudakov, Jan Vondrák

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

We prove that for every fixed k and ℓ ≥ 5 and for sufficiently large n, every edge coloring of the hypercube Qn with k colors contains a monochromatic cycle of length 2ℓ. This answers an open question of Chung. Our techniques provide also a characterization of all subgraphs H of the hypercube which are Ramsey, that is, have the property that for every k, any k-edge coloring of a sufficiently large Qn contains a monochromatic copy of H.

Original languageEnglish (US)
Pages (from-to)196-208
Number of pages13
JournalJournal of Graph Theory
Volume53
Issue number3
DOIs
StatePublished - Nov 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • Hypercube
  • Monochromatic cycles
  • Ramsey theory

Fingerprint Dive into the research topics of 'A Ramsey-type result for the hypercube'. Together they form a unique fingerprint.

Cite this