Portal de Periódicos da CAPES

Two results about the hypercube

2018; Elsevier BV; Volume: 247; Linguagem: Inglês

10.1016/j.dam.2018.03.086

1872-6771

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

Advanced Graph Theory Research

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 ) ) 1 k + 1 n k ≤ m ( n , k ) ≤ n ( 1 + o ( 1 ) ) n k . We close the gap by showing that log m ( n , k ) = ( 1 + o ( 1 ) ) n k log n . 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 2 n n ≤ I ( Q n ) ≤ C 2 n n log n 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 2 n n log n .