On the Turán Density of $C_{10}$ in the Hypercube

Abstract

The $n$-dimensional hypercube $Q_n$ is the graph with vertex set $\{0,1{\}}^n$ in which two vertices are adjacent if they differ in exactly one coordinate. For a graph $H$, let $\mathrm{ex}(Q_n,H)$ be the maximum number of edges in an $H$-free subgraph of $Q_n$. The hypercube Turán density of $H$ is defined by ${\pi }_{\square }(H)={\lim }_{n\to \infty }\mathrm{ex}(Q_n,H)/|E(Q_n)|$. In this note, we prove \[ \frac{1}{8} \leq π_{\square}(C_{10}) \leq 0.36577. \] For the upper bound, we prove ${\pi }_{\square }(C_{10})\le {\pi }_{\square }(C_6)$, which, together with a result of Baber, gives the stated upper bound. For the lower bound, we prove that $\mathrm{ex}(Q_n,C_{10})>|E(Q_n)|/8$ for every $n\ge 2$.

arXiv comment9 pages; lower bound construction added, references added, small changes in formatting and wording