$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.
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
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

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

Collections

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〉

Partager

Métriques

Consultations de la notice

101

Téléchargements de fichiers

32