Maximum shattering
| Autor: | Alon, Noga, Sivashankar, Varun, Zhu, Daniel G. |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | A family $\mathcal{F}$ of subsets of $[n]=\{1,2,\ldots,n\}$ shatters a set $A \subseteq [n]$ if for every $A' \subseteq A$ there is an $F \in \mathcal{F}$ such that $F \cap 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 \leq 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 \leq k \leq (1+o(1))2^d$, we have $f(n,k,d)=(1+o(1))c\binom{n}{d}$, 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\'esz\'aros. As an application, we improve bounds for the existence of covering arrays for certain alphabet sizes. Comment: 15 pages, 2 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|