Abstract
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 q^n 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.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.