A note on short cycles in a hypercube

Original · EN

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ₗ) be the largest number of edges in a subgraph of a hypercube Qₙ containing no cycle of length l. It is known that f(n, Cₗ) = o(|E(Qₙ)|), when l= 4k, k≥ 2 and that f(n, C₆) ≥ 1/3 |E(Qₙ)|. It is an open question to determine f(n, Cₗ) for l=4k+2, k≥ 2. Here, we give a general upper bound for f(n,Cₗ) when l=4k+2 and provide a coloring of E(Qₙ) by 4 colors containing no induced monochromatic C₁₀.