Skip to Main content Skip to Navigation
Conference papers

$S$-constrained random matrices

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.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184682
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 17, 2015 - 2:22:48 PM
Last modification on : Wednesday, May 19, 2021 - 3:37:36 PM
Long-term archiving on: : Wednesday, November 18, 2015 - 10:44:09 AM

File

dmAG0127.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184682, version 1

Collections

Citation

Sylvain Gravier, Bernard Ycart. $S$-constrained random matrices. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. pp.357-364. ⟨hal-01184682⟩

Share

Metrics

Record views

174

Files downloads

524