Subgraphs of a hypercube containing no small even cycles
✍ Scribed by Fan R. K. Chung
- Publisher
- John Wiley and Sons
- Year
- 1992
- Tongue
- English
- Weight
- 490 KB
- Volume
- 16
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
We investigate several Ramsey‐Turán type problems for subgraphs of a hypercube. We obtain upper and lower bounds for the maximum number of edges in a subgraph of a hypercube containing no four‐cycles or more generally, no 2__k__‐cycles C~2k~. These extermal results imply, for example, the following Ramsey theorems for hypercubes: A hypercube can always be edge‐partitioned into four subgraphs, each of which contains no six‐cycle. However, for any integer t, if the n‐cube is edge‐partitioned into t sub‐graphs, then one of the subgraphs must contain an edight‐cycle, provided only than n is sufficiently large (depending only on t).