# $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.
Keywords :
Type de document :
Communication dans un congrès
Chassaing, Philippe and others. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, pp.357-364, 2006, DMTCS Proceedings
Domaine :

Littérature citée [23 références]

https://hal.inria.fr/hal-01184682
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 14:22:48
Dernière modification le : jeudi 11 janvier 2018 - 06:14:33
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 10:44:09

### Fichier

dmAG0127.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01184682, version 1

### Citation

Sylvain Gravier, Bernard Ycart. $S$-constrained random matrices. Chassaing, Philippe and others. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, pp.357-364, 2006, DMTCS Proceedings. 〈hal-01184682〉

### Métriques

Consultations de la notice

## 151

Téléchargements de fichiers