TY - JOUR

T1 - Two results about the hypercube

AU - Balogh, József

AU - Mészáros, Tamás

AU - Wagner, Adam Zsolt

N1 - Funding Information:
The authors are grateful to Shagnik Das for his many insightful comments regarding the manuscript, and to the anonymous referee for many helpful comments and suggestions. The first author’s researchis partially supported by National Science Foundation Grant DMS-1500121 and Arnold O. Beckman Research Award (UIUC Campus Research Board 15006) and the Langan Scholar Fund (UIUC). The second author’s research is supported by the DRS POINT Fellowship Program at Freie Universität Berlin.

PY - 2018/10/1

Y1 - 2018/10/1

N2 - 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.

AB - 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.

KW - Hypercube

KW - Integrity

KW - Network vulnerability

KW - VC-dimension

UR - http://www.scopus.com/inward/record.url?scp=85046171305&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85046171305&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2018.03.086

DO - 10.1016/j.dam.2018.03.086

M3 - Article

AN - SCOPUS:85046171305

VL - 247

SP - 322

EP - 326

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -