On high-girth layered graphs of large Turán density in a hypercube

Abstract

For a graph $H$, let $\mathrm{ex}(Q_n,H)$ be the largest number of edges in a subgraph of the hypercube $Q_n$ of dimension $n$ that contains no subgraph isomorphic to $H$. We define ${\pi }_{\square }(H)={\lim }_{n\to \infty }\mathrm{ex}(Q_n,H)/|E(Q_n)|$ as the Turán density of $H$ in the hypercube. Although determining ${\pi }_{\square }(H)$ for general $H$ remains widely open, Conlon found a large class of graphs with zero Turán density in a hypercube. In this note, we address the case when ${\pi }_{\square }(H)>0$. If a graph $H$ cannot be embedded in an edge layer of a hypercube, then ${\pi }_{\square }(H)\ge 1/2$, as can be seen by taking every other edge layer of $Q_n$. Previously known examples of layered graphs of positive Turán density in a hypercube include graphs containing cycles of length $6$ or $10$, as well as examples of girth $8$. Also, to the best of our knowledge, all previously known examples of graphs with Turán densities arbitrarily close to one are not layered. We show that for every $g\ge 3$, there are layered graphs of girth greater than $g$ whose Turán densities in a hypercube are arbitrarily close to one. Moreover, these graphs have an induced embedding into an edge layer of a hypercube.

arXiv comment10 pages; main theorem strengthened from Turán density at least 1/2 to Turán density arbitrarily close to one