S-constrained random matrices
Sylvain Gravier, Bernard Ycart
Abstract
Let S be a set of d-dimensional row vectors with entries in a q-ary alphabet. A matrix M with entries in the same q-ary alphabet is S-constrained if every set of d columns of M contains as a submatrix a copy of the vectors in S, up to permutation. For a given set S of d-dimensional vectors, we compute the asymptotic probability for a random matrix M to be S-constrained, as the numbers of rows and columns both tend to infinity. If n is the number of columns and m=mn the number of rows, then the threshold is at mn=αd log(n), where αd only depends on the dimension d of vectors and not on the particular set S. Applications to superimposed codes, shattering classes of functions, and Sidon families of sets are proposed. For d=2, an explicit construction of a S-constrained matrix is given.
Full Text: PDF