$S$-constrained random matrices

$S$-constrained random matrices

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$-dimensi...

Full description

Bibliographic Details
Main Authors: Sylvain Gravier, Bernard Ycart
Format: Article
Language:English
Published: Discrete Mathematics & Theoretical Computer Science 2006-01-01
Series:Discrete Mathematics & Theoretical Computer Science
Subjects:
random matrix
poisson approximation
superimposed code
shattering
vc dimensions
sidon families
[info.info-ds] computer science [cs]/data structures and algorithms [cs.ds]
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
[math.math-co] mathematics [math]/combinatorics [math.co]
Online Access:https://dmtcs.episciences.org/3480/pdf

Internet

https://dmtcs.episciences.org/3480/pdf

Similar Items