On Minimum Saturated Matrices |
| |
Authors: | Andrzej Dudek Oleg Pikhurko Andrew Thomason |
| |
Institution: | 1. Department of Mathematics, Western Michigan University, Kalamazoo, MI, 49008, USA 2. Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA, 15213, USA 3. Mathematics Institute, University of Warwick, Coventry, CV4 7AL, UK 4. Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge, CB3 0WB, UK
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|