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

\begin{problem} Bound the extremal number of $C_{10}$ in the hypercube. \end{problem}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

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.

Bibliography

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

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