# 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?

Bibliography
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.