Abstract
A family (Formula presented.) of subsets of (Formula presented.) shatters a set (Formula presented.) if for every (Formula presented.), there is an (Formula presented.) such that (Formula presented.). We develop a framework to analyze (Formula presented.), the maximum possible number of subsets of (Formula presented.) of size (Formula presented.) that can be shattered by a family of size (Formula presented.). Among other results, we determine (Formula presented.) exactly for (Formula presented.) and show that if (Formula presented.) and (Formula presented.) grow, with both (Formula presented.) and (Formula presented.) tending to infinity, then for any (Formula presented.) satisfying (Formula presented.), we have (Formula presented.), where (Formula presented.), roughly 0.289, is the probability that a large square matrix over (Formula presented.) 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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 456-470 |
| Number of pages | 15 |
| Journal | Journal of Combinatorial Designs |
| Volume | 33 |
| Issue number | 12 |
| DOIs | |
| State | Published - Dec 2025 |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
Keywords
- covering array
- extremal set theory
- hypergraph Lagrangian
- set shattering