Geodesic
$S$-constrained random matrices
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities (2006).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2006_special_252_a4,
     author = {Gravier, Sylvain and Ycart, Bernard},
     title = {$S$-constrained random matrices},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities},
     year = {2006},
     doi = {10.46298/dmtcs.3480},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3480/}
}
TY  - JOUR
AU  - Gravier, Sylvain
AU  - Ycart, Bernard
TI  - $S$-constrained random matrices
JO  - Discrete mathematics & theoretical computer science
PY  - 2006
VL  - DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3480/
DO  - 10.46298/dmtcs.3480
LA  - en
ID  - DMTCS_2006_special_252_a4
ER  - 
%0 Journal Article
%A Gravier, Sylvain
%A Ycart, Bernard
%T $S$-constrained random matrices
%J Discrete mathematics & theoretical computer science
%D 2006
%V DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3480/
%R 10.46298/dmtcs.3480
%G en
%F DMTCS_2006_special_252_a4
Gravier, Sylvain; Ycart, Bernard. $S$-constrained random matrices. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities (2006). doi : 10.46298/dmtcs.3480. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3480/

Cité par Sources :