Two results about the hypercube

Abstract

First we consider families in the hypercube $Q_n$ with bounded VC dimension. Frankl raised the problem of estimating the number $m(n,k)$ of maximal families of VC dimension $k$. Alon, Moran and Yehudayoff showed that $$n^{(1+o(1))\frac{1}{k+1}\left(\genfrac{}{}{0ex}{}{n}{k}\right)}\le m(n,k)\le n^{(1+o(1))\left(\genfrac{}{}{0ex}{}{n}{k}\right)}.$$ We close the gap by showing that $\log \left(m(n,k)\right)=(1+o(1))\left(\genfrac{}{}{0ex}{}{n}{k}\right)\log n$ and show how a tight asymptotic for the logarithm of the number of induced matchings between two adjacent small layers of $Q_n$ follows as a corollary. Next, we consider the integrity $I(Q_n)$ of the hypercube, defined as $$I(Q_n)=\min \{|S|+m(Q_n\setminus S):S\subseteq V(Q_n)\},$$ where $m(H)$ denotes the number of vertices in the largest connected component of $H$. Beineke, Goddard, Hamburger, Kleitman, Lipman and Pippert showed that $c\frac{2^n}{\sqrt{n}}\le I(Q_n)\le C\frac{2^n}{\sqrt{n}}\log n$ and suspected that their upper bound is the right value. We prove that the truth lies below the upper bound by showing that $I(Q_n)\le C\frac{2^n}{\sqrt{n}}\sqrt{\log n}$.

7 pages