On Minimum Saturated Matrices

Details On Minimum Saturated Matrices On Minimum Saturated Matrices

2009-09-10

arxiv.org/abs/0909.1970v2

Mathematics

Combinatorics

31 pages, included a C code

Scientific paper

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). Moreover, M 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.

Affiliated with

Also associated with

No associations

Rating

On Minimum Saturated Matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Minimum Saturated Matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Minimum Saturated Matrices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-132052