Subgraphs of the cube without a \(2k\)-cycle

For a finite family \( {\mathcal F}\) of graphs, let \( t(n, {\mathcal{F}})\) denote the smallest integer \( m\) that every graph on \( n\) vertices and \( m\) edges must contain a member of \( \mathcal{F}\) as a subgraph.

A variation of the Turán problem involves restricting the "host" graphs. Instead of considering unavoidable subgraphs of the complete graph, Erdös proposed Turán-type problems in an \( n\)-cube. In early 70's, he asked the following problem[1]:

Turán numbers in an \(n\)-cube [1]($100)

Let \(f_{2k}(n)\) denote the maximum number of edges in a subgraph of \(Q_n\) containing no \(C_{2k}\). Prove or disprove: \[ f_4(n) = (\frac 1 2 +o(1)) n 2^{n-1}. \]

For small \( n\), it is known that \( f_4(1)=1, f_4(2)=3, f_4(3)=9 \), \( f_4(4)=24,\) and \( f_4(5)=56\) (see [4]). The best general lower bound construction known is due to Guan[5] which gives

\(\displaystyle f_4(n) \geq (n+3)2^{n-2} -(n- 3 \lfloor \frac{n-1}{3} \rfloor)2^{2 \lfloor (n-1)/3 \rfloor}. \)

The best upper bound known is due to Chung[2]:

\(\displaystyle f_4(n) \leq (\alpha + o(1)) n 2^{n-1} \)

where \( \alpha \approx .623\) satisfies \( 9 \alpha^3+5 \alpha^2 - 5 \alpha-1 =0\).

In [2], it was also shown that a subgraph of \( Q_n\) containing no \( C_6\) can have at most \( (\sqrt{2}-1+o(1))n2^{n-1}\) edges. Conder [3] gives a \( 3\)-coloring of the edges of \( Q_n\) containing no \( C_6\) and therefore

\(\displaystyle f_6(n) \geq \frac 1 3 n 2^{n-1}. \)

For \( k \) even, it was shown[2] that every subgraph of \( Q_n\) containing \( cn^{1/2+1/2k}2^{n-1}\) edges must contain \( C_{2k}\). This implies the following Ramsey-type result: For any \( t\), any edge-coloring of \( Q_n\) in \( t\) colors must contain a monochromatic \( C_{2k}\), provided \( n\) is sufficiently large (depending only on \( t\) and \( k \)).

In general, the limit

\(\displaystyle \sigma_{2k} = \lim_{n \rightarrow \infty} \frac{f_{2k}(n)}{e(Q_n)} \)

exists. The best bounds known for \( \sigma_4\) are \( 1/2 \leq \sigma_4 \leq .623\) (see [2]).

Numerous questions of Turán and Ramsey types for the \( n\)-cube remain open:

Is it true that \( f_{2k} \geq f_{2k+2}\)? Does strict inequality hold?

Is it true that \( \sigma_6=1/3\)?

Is it true that \( \sigma_{10}=0\)?

Is it true that for every \( t\), any edge-coloring of \( Q_n\) in \( t\) colors must contain a monchromatic \( C_{2k}\) for \( k \geq 4\), if \( n\) is sufficiently large?

1 P. Erdös, Some of my favourite unsolved problems, A Tribute to Paul Erdös, 467-478, Cambridge Univ. Press, Cambridge, 1990.

2 F. R. K. Chung. Subgraphs of a hypercube containing no small even cycles, J. Graph Theory 16 (1992), 273-286.

3 M. Conder, Hexagon-free subgraphs of hypercubes, J. Graph Theory 17 (1993), 477-479.

4 M. R. Emany-K, P. Guan and P. I. Rivera-Vega. On the characterization of the maximum squareless subgraphs of \( 5\)-cube. Proceedings of the 23rd Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. 88 (1992), 97-109.

5 P. Guan, A class of critical squareless subgraphs of hypercubes. preprint.