## 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 maximum families of VC dimension k. Alon, Moran and Yehudayoff showed that n^{(1+o(1))[Formula presented][Formula presented]}≤m(n,k)≤n^{(1+o(1))[Formula presented]}.We close the gap by showing that logm(n,k)=(1+o(1))[Formula presented]logn. We also show how a bound on 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}∖S):S⊆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[Formula presented]≤I(Q_{n})≤C[Formula presented]logn 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})≤C[Formula presented]logn.

Original language | English (US) |
---|---|

Pages (from-to) | 322-326 |

Number of pages | 5 |

Journal | Discrete Applied Mathematics |

Volume | 247 |

DOIs | |

State | Published - Oct 1 2018 |

## Keywords

- Hypercube
- Integrity
- Network vulnerability
- VC-dimension

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics