Abstract
First we consider families in the hypercube Qn 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 Qn follows as a corollary. Next, we consider the integrity I(Qn) of the hypercube, defined as I(Qn)=min{|S|+m(Qn∖S):S⊆V(Qn)},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(Qn)≤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(Qn)≤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