On Minimum Saturated Matrices - Mathematics > CombinatoricsReportar como inadecuado

On Minimum Saturated Matrices - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: Motivated by the work of Anstee, Griggs, and Sali on forbidden submatricesand the extremal sat-function for graphs, we introduce sat-type problems formatrices. Let F be a family of k-row matrices. A matrix M is calledF-admissible if M contains no submatrix G\in F as a row and column permutationof G. A matrix M without repeated columns is F-saturated if M is F-admissiblebut the addition of any column not present in M violates this property. In thispaper we consider the function satn,F which is the minimum number of columnsof an F-saturated matrix with n rows. We establish the estimatesatn,F=On^{k-1} for any family F of k-row matrices and also compute thesat-function for a few small forbidden matrices.

Autor: Andrzej Dudek, Oleg Pikhurko, Andrew Thomason

Fuente: https://arxiv.org/

Documentos relacionados