On Graphs Embeddable in a Layer of a Hypercube and Their Extremal Numbers

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 at least a positive
proportion of the number of edges in Q$_n$, then H is said to have positive
Tur´an density in the 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 characterization
of layered graphs in terms of edge-colorings. 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
... mehr
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}$) = Ω($_n$2$^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´an density.