DMTCS Proceedings, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities

Font Size:  Small  Medium  Large

S-constrained random matrices

Sylvain Gravier, Bernard Ycart


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

Valid XHTML 1.0 Transitional