Subgraphs of the cube without a \(2k\)cycle
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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ántype 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^{n1}. \]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
The best upper bound known is due to Chung[2]:
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^{n1}\) edges. Conder [3] gives a \( 3\)coloring of the edges of \( Q_n\) containing no \( C_6\) and therefore
In general, the limit
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 edgecoloring 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, 467478, Cambridge Univ. Press,
Cambridge, 1990.

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

3 
M. Conder, Hexagonfree subgraphs of hypercubes,
J. Graph Theory 17 (1993), 477479.

4  M. R. EmanyK, P. Guan and P. I. RiveraVega. 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), 97109.

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