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á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
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^{n-1}\) 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 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.
|