Two refinements of the bound of Sauer, Perles and Shelah, and of Vapnik and Chervonenkis

We say that a matrix is simple if it is a (0, 1)-matrix with no repeated columns. Given m and a k × l (0, 1)-matrix F , we seek the bound forb ( m , F ) on the maximum number of columns that a simple m -rowed matrix A can have if the simple matrix A has the property that it has no k × l submatrix which is a row and column permutation of F . Let K k denote the k × 2 k (0, 1)-matrix of all columns in k rows. Sauer, Perles and Shelah, and Vapnik and Chervonenkis established that forb ( m , K k ) is Θ ( m k − 1 ) . (An alternative description for the absence of a configuration K k is to say that the matrix has no shattered k -set.) We identify an easy but exact condition on a k -rowed simple matrix F for which forb ( m , F ) is O ( m k − 2 ) . A consequence is a classification of the asymptotics of forb ( m , F ) for simple four-rowed matrices F . In addition we identify an easy but exact description for all k -rowed non-simple matrices F which contain K k and for which forb ( m , F ) is still O ( m k − 1 ) . The results are further evidence for the conjecture of Anstee and Sali on the asymptotics of forb ( m , F ) for fixed F .