On Minimum Saturated Matrices

Motivated both by the work of Anstee, Griggs, and Sali on forbidden submatrices and also by the extremal sat-function for graphs, we introduce sat-type problems for matrices. Let ${\mathcal{F}}$ be a family of k-row matrices. A matrix M is called ${\mathcal{F}}$ -admissible if M contains no submatrix ${F \in \mathcal{F}}$ (as a row and column permutation of F). A matrix M without repeated columns is ${\mathcal{F}}$ -saturated if M is ${\mathcal{F}}$ -admissible but the addition of any column not present in M violates this property. In this paper we consider the function sat( ${n, \mathcal{F}}$ ) which is the minimal number of columns of an ${\mathcal{F}}$ -saturated matrix with n rows. We establish the estimate sat ${(n, \mathcal{F})=O(n^{k-1})}$ for any family ${\mathcal{F}}$ of k-row matrices and also compute the sat-function for a few small forbidden matrices.