Matrices with forbidden subconfigurations (Q1059636)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Matrices with forbidden subconfigurations
scientific article

    Statements

    Matrices with forbidden subconfigurations (English)
    0 references
    0 references
    0 references
    1985
    0 references
    The problem of determining the largest number f(n,R) of distinct columns an m-roved matrix with entries from set (0,1,...,q-1) can have without containing the given matrix R as a subconfiguration (i.e. a submatrix of some row and column permutation) is considered. The best possible bound f(m,k) is determined when R is a k-roved matrix having all possible k- tuples as column. Certain matrices having columns with restricted number of nonzero entries and meeting the bound are constructed as well. The results generalize corresponding results of Anstee, Füredi, Perles, Quinn, Ryser, Saner and Shelah obtained for the case \(q=2\).
    0 references
    configurations
    0 references
    matrices
    0 references
    0 references

    Identifiers