On Minimum Saturated Matrices
| Autor: | Andrzej Dudek, Andrew Thomason, Oleg Pikhurko |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
010102 general mathematics
Block matrix 0102 computer and information sciences Function (mathematics) 01 natural sciences Theoretical Computer Science 05D05 Combinatorics Matrix (mathematics) Permutation 010201 computation theory & mathematics FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Combinatorics (math.CO) 0101 mathematics Mathematics |
| Zdroj: | Graphs and Combinatorics. 29:1269-1286 |
| ISSN: | 1435-5914 0911-0119 |
| DOI: | 10.1007/s00373-012-1199-2 |
| Popis: | Motivated by the work of Anstee, Griggs, and Sali on forbidden submatrices and the extremal sat-function for graphs, we introduce sat-type problems for matrices. Let F be a family of k-row matrices. A matrix M is called F-admissible if M contains no submatrix G\in F (as a row and column permutation of G). A matrix M without repeated columns is F-saturated if M is F-admissible but the addition of any column not present in M violates this property. In this paper we consider the function sat(n,F) which is the minimum number of columns of an F-saturated matrix with n rows. We establish the estimate sat(n,F)=O(n^{k-1}) for any family F of k-row matrices and also compute the sat-function for a few small forbidden matrices. 31 pages, included a C code |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink