Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Two results about the hypercube   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 maximal families
of VC dimension $k$. Alon, Moran and Yehudayoff showed that
$$n^{(1+o(1))\frac{1}{k+1}\binom{n}{k}}\leq m(n,k)\leq
n^{(1+o(1))\binom{n}{k}}.$$ We close the gap by showing that $\log
\left(m(n,k)\right)= {(1+o(1))\binom{n}{k}}\log n$ and show how a tight
asymptotic for the logarithm of 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 \setminus S) : S \subseteq 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\frac{2^n}{\sqrt{n}} \leq I(Q_n)\leq C\frac{2^n}{\sqrt{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)\leq C
\frac{2^n}{\sqrt{n}}\sqrt{\log n}$.

37
The categories of this paper are: supr-con
33
The categories of this paper are: plasm-ph
35
The categories of this paper are: mtrl-th
4
The categories of this paper are: cond-mat
3
The categories of this paper are: physics
32
The categories of this paper are: atom-ph
12
The categories of this paper are: nucl-th
18
The categories of this paper are: econ
27
The categories of this paper are: comp-gas
30
The categories of this paper are: q-alg
22
The categories of this paper are: chao-dyn
14
The categories of this paper are: math-ph
11
The categories of this paper are: hep-lat
5
The categories of this paper are: gr-qc
34
The categories of this paper are: chem-ph
25
The categories of this paper are: patt-sol