On graphs embeddable in a layer of a hypercube and their extremal numbers

arXiv2303.15529MaRDI QIDQ6431036FDOQ6431036

Authors: Maria Axenovich, Ryan R. Martin, Christian Winter 

Publication date: 27 March 2023

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'an density in a hypercube; otherwise it has zero Tur'an density. Determining $ex(Q_n,H)$ and even identifying whether $H$ has positive or zero Tur'an 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'an 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'an 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 and show that any $n$-vertex layered graphs has at most $frac14nlogn(1+o(1))$ edges. We show that most non-trivial subdivisions have zero Tur'an density, extending known results on zero Tur'an 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'an density. The cycle of length $10$ remains the only cycle for which it is not known whether its Tur'an density is positive or not. We prove that $ex(Q_n,C_{10})=Omega(n{2}^n/lo{g}^{a}n)$, for a constant $a$, showing that the extremal number for a $10$-cycle behaves differently from any other cycle of zero Tur'an density.

Mathematics Subject Classification ID

Combinatorics (05-XX)

This page was built for publication: On graphs embeddable in a layer of a hypercube and their extremal numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6431036)