| Abstrakt: |
We consider matrices with entries from the set {0, 1, …, q−1}. Suppose that Skis a k×qkmatrix having all possible k-tuples as columns. We determine the best possible bound f(m, k) with the property that if Ais any m×(f(m, k)+1) matrix of distinct columns, then some row and column permutation of Acontains Skas a submatrix. Our result generalizes a number of the results for q= 2 due to Anstee, Füredi, Quinn, Sauer, Perles and Shelah, and is obtained by means of a simple inductive argument. Interesting matrices meeting the bound are constructed. |
