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 } . ecture 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.