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

Source abstract

For a graph $H$, let $\operatorname{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$. The Turán density of $H$ in a hypercube, denoted $π_\square(H)$, is defined as $\lim_{n\rightarrow \infty} \operatorname{ex}(Q_n, H)/|E(Q_n)|$. Determining $π_\square(H)$ remains a widely open question for general $H$. Conlon found a large class of graphs with zero Turán density in a hypercube. In this note, we address the case when $π_{\square} (H)>0$. If a graph $H$ is not embeddable in an edge-layer of a hypercube, then $π_{\square} (H)\geq 1/2$, as can be seen by taking every other edge layer of $Q_n$. Among the layered graphs, the only ones known to have positive Turán density in a hypercube are graphs containing cycles of length $6$ or $10$. We show that, for every $g \geq 3$, there is a layered graph of girth at least $g$ whose Turán density in a hypercube is at least $1/2$.