Name
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00373-012-1199-2 | Graphs and Combinatorics |
Keywords | Field | DocType |
forbidden configurations,forbidden submatrices,saturated matrices | Graph,Combinatorics,Matrix (mathematics),Permutation,Block matrix,Mathematics | Journal |
Volume | Issue | ISSN |
29 | 5 | 1435-5914 |
Citations | PageRank | References |
1 | 0.36 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrzej Dudek | 1 | 114 | 23.10 |
| Oleg Pikhurko | 2 | 318 | 47.03 |
| Andrew Thomason | 3 | 71 | 16.01 |