A note on short cycles in a hypercube (Q2509296): Difference between revisions

The graph \(Q_n\) (called hypercube of dimension \(n\)) is defined as follows: The set of vertices of \(Q_n\) consists of subsets of \(\{1,\dots,n\}\), and the set of edges \(E(Q_n)\) corresponds to pairs of sets with symmetric difference of size \(1\). Let \(f(n,C_l)\) be the largest number of edges in a subgraph of \(Q_n\) with no cycle of length \(l\). It is known for example that \(f(n,C_4)\leq 0.623\cdot | E(Q_n)| \). The authors provide a general upper bound for \(f(n,C_l)\) when \(l=4k+2\) as well as a coloring of \(E(Q_n)\) by four colors containing no induced monochromatic \(C_{10}\).