A Ramsey-type result for the hypercube

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

doi:10.1002/jgt.20181

A Ramsey-type result for the hypercube

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

Research output: Contribution to journal › Article › peer-review

22 Scopus citations

Abstract

We prove that for every fixed k and ℓ ≥ 5 and for sufficiently large n, every edge coloring of the hypercube Q_n 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 Q_n contains a monochromatic copy of H.

Original language	English (US)
Pages (from-to)	196-208
Number of pages	13
Journal	Journal of Graph Theory
Volume	53
Issue number	3
DOIs	https://doi.org/10.1002/jgt.20181
State	Published - Nov 2006
Externally published	Yes

All Science Journal Classification (ASJC) codes

Geometry and Topology

Keywords

Hypercube
Monochromatic cycles
Ramsey theory

Access to Document

10.1002/jgt.20181

Cite this

@article{01e88383478e41f7b1a1ea2ea5aa952a,

title = "A Ramsey-type result for the hypercube",

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.",

keywords = "Hypercube, Monochromatic cycles, Ramsey theory",

author = "Noga Alon and Rado{\v s} Radoi{\v c}i{\'c} and Benny Sudakov and Jan Vondr{\'a}k",

year = "2006",

month = nov,

doi = "10.1002/jgt.20181",

language = "English (US)",

volume = "53",

pages = "196--208",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - A Ramsey-type result for the hypercube

AU - Alon, Noga

AU - Radoičić, Radoš

AU - Sudakov, Benny

AU - Vondrák, Jan

PY - 2006/11

Y1 - 2006/11

N2 - 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.

AB - 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.

KW - Hypercube

KW - Monochromatic cycles

KW - Ramsey theory

UR - http://www.scopus.com/inward/record.url?scp=33750471208&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33750471208&partnerID=8YFLogxK

U2 - 10.1002/jgt.20181

DO - 10.1002/jgt.20181

M3 - Article

AN - SCOPUS:33750471208

SN - 0364-9024

VL - 53

SP - 196

EP - 208

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

A Ramsey-type result for the hypercube

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this