Maximum shattering

Abstract

A family $\mathcal{F}$ of subsets of $[n]=\{1,2,\dots ,n\}$ shatters a set $A\subseteq [n]$ if for every $A^{\prime }\subseteq A$ there is an $F\in \mathcal{F}$ such that $F\cap A=A^{\prime }$. We develop a framework to analyze $f(n,k,d)$, the maximum possible number of subsets of $[n]$ of size $d$ that can be shattered by a family of size $k$. Among other results, we determine $f(n,k,d)$ exactly for $d\le 2$ and show that if $d$ and $n$ grow, with both $d$ and $n-d$ tending to infinity, then, for any $k$ satisfying $2^d\le k\le (1+o(1))2^d$, we have $f(n,k,d)=(1+o(1))c\left(\genfrac{}{}{0ex}{}{n}{d}\right)$, where $c$, roughly $0.289$, is the probability that a large square matrix over ${\mathbb{F}}_2$ is invertible. This latter result extends work of Das and Mészáros. As an application, we improve bounds for the existence of covering arrays for certain alphabet sizes.

15 pages, 2 figures