Matrices with forbidden subconfigurations
type: Item
instance of: scholarly article
title: Matrices with forbidden subconfigurations
zbMATH Open document ID: 0567.05012
DOI: 10.1016/0012-365X(85)90069-X
author: U. S. R. Murty
author: R. P. Anstee
published in: Discrete Mathematics
publication date: 1985-01-01T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05B20
zbMATH DE Number: 3904600
zbMATH Keywords: configurations
zbMATH Keywords: matrices
reviewed by: S. S. Agayan
MaRDI profile type: Publication
cites work: General forbidden configuration theorems
cites work: Q3941433
cites work: Q4147993
cites work: A Fundamental Matrix Equation for Finite Sets
cites work: On the density of families of sets
cites work: A combinatorial problem; stability and order for models and theories in infinitary languages
description: scientific article; zbMATH DE number 3904600