Two results about the hypercube

József Balogh, Tamás Mészáros, Adam Zsolt Wagner

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)322-326
Number of pages5
JournalDiscrete Applied Mathematics
Volume247
DOIs
StatePublished - Oct 1 2018

Keywords

  • Hypercube
  • Integrity
  • Network vulnerability
  • VC-dimension

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Two results about the hypercube'. Together they form a unique fingerprint.

Cite this