Maximum Shattering

ABSTRACT A family of subsets of shatters a set if for every , there is an such that . We develop a framework to analyze , the maximum possible number of subsets of of size that can be shattered by a family of size . Among other results, we determine exactly for and show that if and grow, with both and tending to infinity, then for any satisfying , we have , where , roughly 0.289, is the probability that a large square matrix over 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.