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.
All Science Journal Classification (ASJC) codes
- Anti-Ramsey problems
- Ramsey's theorem
- Turán-type problems