On minimum saturated matrices

DOI10.1007/S00373-012-1199-2zbMATH Open1272.05016arXiv0909.1970OpenAlexW2101850362MaRDI QIDQ367048FDOQ367048

Authors: Oleg Pikhurko, Andrzej Dudek, Andrew Thomason 

Publication date: 26 September 2013

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

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.

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

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

zbMATH Keywords

forbidden configurationsforbidden submatricessaturated matrices

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• Saturation of Multidimensional 0-1 Matrices
• Almost all permutation matrices have bounded saturation functions
• Min of Mat is not necessarily Mat
• Saturation of Ordered Graphs
• Title not available (Why is that?)
• 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)