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