Maximum shattering

2024/09/19 by Alon, Noga, Sivashankar, Varun, Zhu, Daniel G.
#05D05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2409.12945

Abstract

A family F of subsets of [n]=\1,2,…,n\ shatters a set A ⊆ [n] if for every A' ⊆ A there is an F ∈ F such that F ∩ A=A'. 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 ≤ 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 ≤ k ≤ (1+o(1))2^d, we have f(n,k,d)=(1+o(1))c\binomnd, where c, roughly 0.289, is the probability that a large square matrix over \mathbbF₂ 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.

Related

• Classification of maximum hittings by large families
• Shattering k-sets with Permutations
• Small families of partially shattering permutations
• Shattering Thresholds for Random Systems of Sets, Words, and Permutations
• Shattering-extremal set systems from Sperner families