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

Area of Science:

• Graph theory
• Combinatorics
• Hypercube structures

Background:

• Cubical graphs are subgraphs of hypercubes.
• Turán density determines if a graph H has a positive proportion of edges in a hypercube subgraph.
• Layered graphs are a specific subset of cubical graphs.

Purpose of the Study:

• Characterize layered graphs within hypercubes.
• Investigate the Turán density of various cubical graphs, particularly layered and non-layered ones.
• Extend understanding of Turán density for cycles and subdivisions in hypercubes.

Main Methods:

• Focusing on layered graphs within hypercubes.
• Utilizing edge-colorings for graph characterization.
• Analyzing subdivisions and cycles for Turán density properties.

Main Results:

• Layered graphs are characterized by edge-colorings.
• Most non-trivial subdivisions exhibit zero Turán density in hypercubes.
• Discovered non-layered cubical graphs with positive Turán density and girth 8.

Conclusions:

• Layered graphs have distinct properties within hypercubes.
• The Turán density of the 10-cycle remains an open question, but its extremal number behaves uniquely.
• This research advances the understanding of graph properties and density within hypercube structures.