Two results about the hypercube

Publication date 6 September 2018

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}�inom{n}{k}}leq m(n,k)leq n^{(1+o(1))�inom{n}{k}}.

We close the gap by showing that

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 f r a c 2^{n} s q r t n l e q I (Q_{n}) l e q C f r a c 2^{n} s q r t n l o g 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}) l e q C f r a c 2^{n} s q r t n s q r t l o g n

.

Recommendations

Cited in

(8)

This page was built for publication: Two results about the hypercube