2013/01/27 by Anant P. Godbole, Godbole, Anant P., Samantha Pinella +3
Computer Science · #05A05 #05D40 #Algorithms and Data Compression #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Machine Learning and Algorithms #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1301.6371
openalex publication_date 2013/01/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper considers a problem that relates to the theories of covering arrays, permutation patterns, Vapnik-Chervonenkis (VC) classes, and probability thresholds. Specifically, we want to find the number of subsets of [n]:=1,2,....,n we need to randomly select, in a certain probability space, so as to respectively "shatter" all t-subsets of [n]. Moving from subsets to words, we ask for the number of n-letter words on a q-letter alphabet that are needed to shatter all t-subwords of the qn words of length n. Finally, we explore the number of random permutations of [n] needed to shatter (specializing to t=3), all length 3 permutation patterns in specified positions. We uncover a very sharp zero-one probability threshold for the emergence of such shattering; Talagrand's isoperimetric inequality in product spaces is used as a key tool.