Largest density of a layered subgraph of a hypercube

2026/07/17 by Maria Axenovich, Arsenii Sagdeev
#math.CO

paper · pdf

Abstract

Let L(t) denote the largest number of edges induced by t vertices from two vertex layers of a hypercube. We show that \frac14 tlog₂ t+\frac18 tlog₂log₂ t-O(t) ≤ L(t) ≤ \frac14 tlog₂ t+ (1+o(1))tlog₂log₂ t.

Citations

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

Related

• Layered subgraphs of the hypercube
• Extremal numbers for cycles in a hypercube
• C10 Has Positive Turán Density in the Hypercube
• Two results about the hypercube
• The number of colorings of the middle layers of the Hamming cube