Saturation problems about forbidden 0-1 submatrices

DOI10.1137/20M1376327MaRDI QIDQ4959655zbMATH OpenOpenAlexFDO

Authors Radoslav Fulek, Balázs Keszegh

Publication date 17 September 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

0-1 matrixexcluded submatrixforbidden patternsaturation

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Extremal problems in graph theory (05C35) Ramsey theory (05D10) Combinatorics of partially ordered sets (06A07) Boolean and Hadamard matrices (15B34)

Abstract: A $0$-$1$ matrix $M$ is saturating for a $0$-$1$ matrix $P$ if $M$ does not contain a submatrix that can be turned into $P$ by changing some $1$ entries to $0$ entries, and changing an arbitrary $0$ to $1$ in $M$ introduces such a submatrix in $M$. In saturation problems for $0$-$1$ matrices we are interested in estimating the minimum number of $1$ entries in an $mimesn$ matrix that is saturating for $P$, in terms of $m$ and $n$. In other words, we wish to give good estimates for the saturation function of $P$. Recently, Brualdi and Cao initiated the study of saturation problems in the context of $0$-$1$ matrices. We extend their work in several directions. We prove that every $0$-$1$ forbidden matrix has its saturation function either in $Theta(1)$ or $Theta(n)$ in the case when we restrict ourselves to square saturating matrices. Then we give a partial answer to a question posed by Brualdi and Cao about the saturation function of $J_k$, which is obtained from the identity matrix $I_k$ by putting the first row after the last row. Furthermore, we exhibit a $5imes5$ permutation matrix with the saturation function bounded from the above by a fixed constant. We complement this result by identifying large classes of $0$-$1$ matrices with linear saturation function. Finally, we completely resolve the related semisaturation problem as far as the constant vs. linear dichotomy is concerned.

Recommendations

• Almost all permutation matrices have bounded saturation functions
• An exact characterization of saturation for permutation matrices
• On minimum saturated matrices
• Saturation of Ordered Graphs
• On linear forbidden submatrices

Cites work

• \(L_ 1\) shortest paths among polygonal obstacles in the plane
• A Problem in Graph Theory
• Cycle-saturated graphs with minimum number of edges
• Davenport-Schinzel theory of matrices
• Degrees of nonlinearity in forbidden 0-1 matrix problems
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Extremal functions of forbidden double permutation matrices
• Forbidden paths and cycles in ordered graphs and matrices
• scientific article; zbMATH DE number 1504588 (Why is no real title available?)
• Induced and non-induced poset saturation problems
• Linear bound on extremal functions of some forbidden patterns in 0-1 matrices
• On 0-1 matrices and small excluded submatrices
• On linear forbidden submatrices
• On minimum saturated matrices
• On the Turán number of ordered forests
• Saturated graphs with minimal number of edges
• Saturating Sperner families
• Saturation problems in the Ramsey theory of graphs, posets and point sets
• The maximum number of unit distances in a convex n-gon
• The saturation number of induced subposets of the Boolean lattice

Cited in

(10)

• Forbidden subposet problems in the grid
• On forbidden submatrices
• On minimum saturated matrices
• scientific article; zbMATH DE number 1463403 (Why is no real title available?)
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
• An exact characterization of saturation for permutation matrices
• Saturation of Multidimensional 0-1 Matrices
• Saturation of Ordered Graphs
• Extremal bounds for pattern avoidance in multidimensional 0-1 matrices
• Sequence saturation

This page was built for publication: Saturation problems about forbidden 0-1 submatrices

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