## Abstract

We are motivated by the analogue of Turán's theorem in the hypercube Q_{n}: How many edges can a Q_{d}-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 Q_{n} 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 (_{2}^{d+1}) + 1 colors is not possible. The corresponding question for vertices is also considered. It is not possible to color the vertices of Q_{n} 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 language | English (US) |
---|---|

Pages (from-to) | 66-72 |

Number of pages | 7 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 21 |

Issue number | 1 |

DOIs | |

State | Published - 2007 |

## All Science Journal Classification (ASJC) codes

- Mathematics(all)

## Keywords

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