A note on short cycles in a hypercube

Abstract: How many edges can a quadrilateral-free subgraph of a hypercube have? This question was raised by Paul ErdH{o}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 g e q 2

and that

f (n, C_{6}) g e q f r a c 13 | E (Q_{n}) |

. It is an open question to determine

f (n, C_{l})

for

l = 4 k + 2

,

k g e q 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}

.

Recommendations

Cites work

Cited in

(22)

This page was built for publication: A note on short cycles in a hypercube