Title: $S$-constrained random matrices.
Authors: S. Gravier and B. 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=m_n$ the number
of rows, then the threshold is at $m_n=\alpha_d\log(n)$, where
$\alpha_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.
AMS 2000 subject classification: 94B65, 68Q32
Key words and phrases:
random matrix, Poisson approximation, superimposed code,
shattering, VC dimensions, Sidon families