Home » Subject » Combinatorics

Turán Problem for $10$-Cycles in the Hypercube

Importance: Medium ✭✭
Author(s): Erdos, Paul
Subject: Combinatorics
Keywords: cycles
extremal combinatorics
hypercube
Recomm. for undergrads: no
Posted by: Jon Noel
on: September 20th, 2015
Problem   Bound the extremal number of $ C_{10} $ in the hypercube.

The problem of bounding the extremal number for cycles in the hypercube was first considered by Erdős [Erd1,Erd2] who conjectured that $ \text{ex}(Q_d,C_4) = (1/2 +o(1)) |E(Q_d)| $ and that $ \text{ex}(Q_d,C_{2t}) = o(|E(Q_d)|) $ for all $ t\geq3 $. The first conjecture is still open, and the second is known to be false in the case $ t=3 $ (see [BDT, Chu, Cond]).

Chung [Chu] proved that $ \text{ex}(Q_d,C_{2t}) = o(|E(Q_d)|) $ for even $ t\geq 4 $ and Füredi and Özkahya [FO1,FO2] proved the same for odd $ t\geq 7 $. Conlon [Conl] gave a unified proof of these results, which also applies to more general subgraphs of the hypercube. However, the case of $ C_{10} $ remains unsolved.

Related problems

Saturation in the Hypercube

Bibliography

[BDT] A. E. Brouwer, I. J. Dejter and C. Thomassen, Highly symmetric subgraphs of hypercubes, J. Algebraic Combin. 2 (1993), 25–29.

[Chu] F. Chung, Subgraphs of a hypercube containing no small even cycles, J. Graph Theory 16 (1992), 273–286.

[Cond] M. Conder, Hexagon-free subgraphs of hypercubes, J. Graph Theory 17 (1993), 477–479.

[Conl] D. Conlon, An extremal theorem in the hypercube, Electron. J. Combin. 17 (2010), no. 1, Research Paper 111, 7 pages

[Erd1] P. Erdős, On some problems in graph theory, combinatorial analysis and combinatorial number theory, in: Graph Theory and Combinatorics (Cambridge, 1983), Academic Press, London, 1984, 1–17.

[Erd2] P. Erdős, Some of my favourite unsolved problems, in: A tribute to Paul Erdős, Cambridge University Press, 1990, 467–478.

[FO1] Z. Füredi and L. Özkahya, On 14-cycle-free subgraphs of the hypercube, Combin. Probab. Comput. 18 (2009), 725–729.

[FO2] Z. Füredi and L. Özkahya, On even-cycle-free subgraphs of the hypercube, Electronic Notes in Discrete Mathematics 34 (2009), 515–517.


* indicates original appearance(s) of problem.
add new comment