Largest density of a layered subgraph of a hypercube

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 t\log_2 t+\frac18 t\log_2\log_2 t-O(t) \leq L(t) \leq \frac14 t\log_2 t+ (1+o(1))t\log_2\log_2 t.$$

Disclosure

“bound up to an o (t log log t) term. It would be interesting to find a closed-form expression for L(t), similar to Harper’s formula for C (t). Acknowledgements The proof of the main theorem was originally generated with the assis- tance of ChatGPT-5.5 Pro, then checked, shortened, and reworked by the authors. References [1] M. Axenovich, A class of graphs of zero Turán density in a hypercube, Combin. Probab. Comput., 33.3 (2024), 404–410. ↑2 [2] M. Axenovich, R. R. Martin, and”

PDF page 5

Classification

Substantial proof generation

Multiplier

10

Verified

2026-08-23T18:57:10.127640Z

Structural counts