Turán's theorem in the hypercube

Noga Alon, Anja Krech, Tibor Szabó

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

We are motivated by the analogue of Turán's theorem in the hypercube Qn: How many edges can a Qd-free subgraph of Q n have? We study this question through its Ramsey-type variant and obtain asymptotic results. We show that for every odd d it is possible to color the edges of Qn with (d=1)2/4 colors such that each subcube Qd is polychromatic, that is, contains an edge of each color. The number of colors is tight up to a constant factor, as it turns out that a similar coloring with (2d+1) + 1 colors is not possible. The corresponding question for vertices is also considered. It is not possible to color the vertices of Qn with d + 2 colors such that any Q d is polychromatic, but there is a simple d + 1 coloring with this property. A relationship to anti-Ramsey colorings is also discussed. We discover much less about the Turán-type question which motivated our investigations. Numerous problems and conjectures are raised.

Original languageEnglish (US)
Pages (from-to)66-72
Number of pages7
JournalSIAM Journal on Discrete Mathematics
Volume21
Issue number1
DOIs
StatePublished - 2007

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Anti-Ramsey problems
  • Hypercube
  • Ramsey's theorem
  • Turán-type problems

Fingerprint Dive into the research topics of 'Turán's theorem in the hypercube'. Together they form a unique fingerprint.

Cite this