Forbidden Configurations: Boundary Cases

A simple matrix is a (0,1)-matrix with no repeated columns. For a (0,1)-matrix F, we say a (0,1)-matrix A has F⊀A, if no submatrix of A is a row and column permutation of F. Let the number of columns of A be ‖A‖. Let forb(m,F)=max{‖A‖:A is m-rowed simple matrix and F⊀A}.A conjecture of Anstee and Sali predicts the asymptotics of forb(m,F) as a function of F. The conjecture identifies certain matrices F as boundary cases, namely k-rowed F with forb(m,F)=Θ(mℓ) while for any k×1 column α that is not already present two or more times in F, we have forb(m,[F|α]) being Ω(mℓ+1). We establish two new boundary cases and review two other newly identified boundary cases. This is further evidence for the conjecture.