paper

A note on short cycles in a hypercube

arXiv:1605.06572 · doi:10.1016/j.disc.2006.05.008

Abstract

How many edges can a quadrilateral-free subgraph of a hypercube have? This question was raised by Paul ErdÅs about $27$ years ago. His conjecture that such a subgraph asymptotically has at most half the edges of a hypercube is still unresolved. Let $f (n, C_{l})$ be the largest number of edges in a subgraph of a hypercube $Q_{n}$ containing no cycle of length $l$ . It is known that $f (n, C_{l}) = o (∣ E (Q_{n}) ∣)$ , when $l = 4 k$ , $k \geq 2$ and that $f (n, C_{6}) \geq \frac{1}{3} ∣ E (Q_{n}) ∣$ . It is an open question to determine $f (n, C_{l})$ for $l = 4 k + 2$ , $k \geq 2$ . Here, we give a general upper bound for $f (n, C_{l})$ when $l = 4 k + 2$ and provide a coloring of $E (Q_{n})$ by $4$ colors containing no induced monochromatic $C_{10}$ .

9 pages