View PDF HTML (experimental)

Abstract:A graph is cubical if it is a subgraph of a hypercube. For a cubical graph $H$ and a hypercube $Q_n$, $ex(Q_n, H)$ is the largest number of edges in an $H$-free subgraph of $Q_n$. If $ex(Q_n, H)$ is equal to a positive proportion of the number of edges in $Q_n$, $H$ is said to have positive Turán density in a hypercube; otherwise it has zero Turán density. Determining $ex(Q_n, H)$ and even identifying whether $H$ has positive or zero Turán density remains a widely open question for general $H$.
In this paper we focus on layered graphs, i.e., graphs that are contained in an edge-layer of some hypercube. Graphs $H$ that are not layered have positive Turán density because one can form an $H$-free subgraph of $Q_n$ consisting of edges of every other layer. For example, a $4$-cycle is not layered and has positive Turán density.
However, in general it is not obvious what properties layered graphs have. We give a characterisation of layered graphs in terms of edge-colorings. We show that most non-trivial subdivisions have zero Turán density, extending known results on zero Turán density of even cycles of length at least $12$ and of length $8$. However, we prove that there are cubical graphs of girth $8$ that are not layered and thus having positive Turán density. The cycle of length $10$ remains the only cycle for which it is not known whether its Turán density is positive or not. We prove that $ex(Q_n, C_{10})= \Omega(n2^n/ \log^a n)$, for a constant $a$, showing that the extremal number for a $10$-cycle behaves differently from any other cycle of zero Turán density.

Submission history

From: Maria Axenovich [view email]
[v1] Mon, 27 Mar 2023 18:11:16 UTC (91 KB)
[v2] Thu, 11 May 2023 18:32:11 UTC (92 KB)
[v3] Sun, 19 May 2024 21:07:21 UTC (93 KB)
[v4] Mon, 20 Jul 2026 09:11:38 UTC (93 KB)