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.
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.
Publisher Copyright:
© 2018 Elsevier B.V.
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
SN - 0166-218X
VL - 247
SP - 322
EP - 326
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -