Matrices with forbidden subconfigurations (Q1059636): Difference between revisions

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\).