On minimum saturated matrices

DOI10.1007/S00373-012-1199-2MaRDI QIDQ367048zbMATH OpenOpenAlexFDO

Authors Oleg Pikhurko, Andrzej Dudek, Andrew Thomason

Publication date 26 September 2013

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0909.1970

zbMATH Keywords

forbidden configurationsforbidden submatricessaturated matrices

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20)

Abstract: 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 Gin 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.

Recommendations

• Saturation problems about forbidden 0-1 submatrices
• Almost all permutation matrices have bounded saturation functions
• An exact characterization of saturation for permutation matrices
• On forbidden submatrices
• Saturated graphs with minimal number of edges

Cites work

• scientific article; zbMATH DE number 4200236 (Why is no real title available?)
• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 1324671 (Why is no real title available?)
• scientific article; zbMATH DE number 3104192 (Why is no real title available?)
• A Note on Fisher's Inequality for Balanced Incomplete Block Designs
• A Problem in Graph Theory
• A combinatorial problem; stability and order for models and theories in infinitary languages
• A survey of forbidden configuration results
• A survey of minimum saturated graphs
• Bounding one-way differences
• Forbidden configurations: Induction and linear algebra
• Forbidden submatrices
• Induced subsets
• On minimum saturated matrices
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the density of families of sets
• Small forbidden configurations
• Small forbidden configurations. IV: The 3 rowed case
• The Minimum Size of Saturated Hypergraphs
• What we know and what we do not know about Turán numbers

Cited in

(9)

• Almost all permutation matrices have bounded saturation functions
• Saturation of Multidimensional 0-1 Matrices
• Min of Mat is not necessarily Mat
• Saturation of Ordered Graphs
• scientific article; zbMATH DE number 913545 (Why is no real title available?)
• Sequence saturation
• Saturation problems about forbidden 0-1 submatrices
• On minimum saturated matrices
• Saturating Sperner families

This page was built for publication: On minimum saturated matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q367048)