Forbidden submatrices

DOI10.1016/0012-365X(86)90211-6MaRDI QIDQ1103620zbMATH OpenOpenAlexFDO

Authors R. P. Anstee, Zoltán Füredi

Publication date 1986

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(86)90211-6

zbMATH Keywords

(0,1)-matrix

Mathematics Subject Classification ID

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

Review text

We consider an \(m\times n\) (0,1)-matrix A, no repeated columns, which has no \(k\times \ell\) submatrix F. We may deduce bounds on n, polynomial in m, depending on F. The best general bound is \(O(m^{2k-1})\). We improve this and provide best possible bounds for \(k\times 1\) F's and certain \(k\times 2\) F's. In the case that all columns of F are the same, good bounds are obtained which are best possible for \(\ell =2\) and some other cases. Good bounds for \(1\ell \ell\) F's are provided, namely \(n\leq (\ell -1)m+1\), which are shown to be best possible for \(F=[1010...10]\). The paper finishes with a study of the 14 different \(3\times 2\) possibilities for F, solving all but 3.

Recommendations

• On forbidden submatrices
• Small forbidden configurations
• Forbidden submatrices: some new bounds and constructions
• General forbidden configuration theorems
• Matrices with forbidden subconfigurations

Cites work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• Domination, independent domination, and duality in strongly chordal graphs
• Extremal values of the interval number of a graph. II
• General forbidden configuration theorems
• scientific article; zbMATH DE number 3887691 (Why is no real title available?)
• On a packing and covering problem
• On the density of families of sets
• Totally-Balanced and Greedy Matrices

Cited in

(23)

• Bounding one-way differences
• A forbidden configuration theorem of Alon
• Small forbidden configurations
• (0, 1)-matrices with no half-half submatrix of ones
• Sperner families of bounded VC-dimension
• Forbidden configurations: Induction and linear algebra
• A generalization of Sauer's lemma
• Forbidden submatrices: some new bounds and constructions
• Partitioning ordered hypergraphs
• Shattering and more: Extending the complete object
• On forbidden submatrices
• On minimum saturated matrices
• scientific article; zbMATH DE number 4041978 (Why is no real title available?)
• Repeated columns and an old chestnut
• scientific article; zbMATH DE number 1463403 (Why is no real title available?)
• Forbidden Berge hypergraphs
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
• Matrices with forbidden submatrices
• Large homogeneous submatrices
• SOFSEM 2004: Theory and Practice of Computer Science
• Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix
• Multivalued matrices and forbidden configurations
• Design theory and some forbidden configurations

This page was built for publication: Forbidden submatrices

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