The study develops a framework analyzing shattering subsets in sets, suggesting improved bounds for covering arrays.
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.
No takes yet. Share an insight, caveat, or question.
Alon et al. (2025) studied this question.
Synapse has enriched 3 closely related papers on similar clinical questions. Consider them for comparative context: