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 $$\frac{1}{4}t{\log }_{2}t+\frac{1}{8}t{\log }_2{\log }_{2}t-O(t)\le L(t)\le \frac{1}{4}t{\log }_{2}t+(1+o(1))t{\log }_2{\log }_{2}t.$$

5 pages