On minimally non-firm binary matrices

DOI10.1007/978-3-031-18530-4_6MaRDI QIDQ6166892zbMATH OpenOpenAlexFDO

Authors Réka Ágnes Kovács

Publication date 3 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

Boolean rankfirm matricesrectangle covering number

Mathematics Subject Classification ID

Boolean programming (90C09) Combinatorial optimization (90C27)

Abstract: For a binary matrix X, the Boolean rank br(X) is the smallest integer k for which X equals the Boolean sum of k rank-1 binary matrices, and the isolation number i(X) is the maximum number of 1s no two of which are in a same row, column and a 2x2 submatrix of all 1s. In this paper, we continue Lubiw's study of firm matrices. X is said to be firm if i(X)=br(X) and this equality holds for all its submatrices. We show that the stronger concept of superfirmness of X is equivalent to having no odd holes in the rectangle cover graph of X, the graph in which br(X) and i(X) translate to the clique cover and the independence number, respectively. A binary matrix is minimally non-firm if it is not firm but all of its proper submatrices are. We introduce two matrix operations that lead to generalised binary matrices and use these operations to derive four infinite classes of minimally non-firm matrices. We hope that our work may pave the way towards a complete characterisation of firm matrices via forbidden submatrices.

Recommendations

• Isolation number versus Boolean rank
• scientific article; zbMATH DE number 1185595
• scientific article; zbMATH DE number 1439493
• The Boolean rank of the uniform intersection matrix and a family of its submatrices
• On the binary and Boolean rank of regular matrices

Cites work

• A Combinatorial Decomposition Theory
• A minimax theorem on intervals
• A notion of cross-perfect bipartite graphs
• Algorithmic graph theory and perfect graphs
• Alternating cycle-free matchings
• Communication Complexity
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• Doubly Lexical Orderings of Matrices
• scientific article; zbMATH DE number 4008576 (Why is no real title available?)
• scientific article; zbMATH DE number 3779513 (Why is no real title available?)
• scientific article; zbMATH DE number 3781471 (Why is no real title available?)
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 3582190 (Why is no real title available?)
• On edge perfectness and classes of bipartite graphs
• The Boolean Basis Problem and How to Cover Some Polygons by Rectangles
• The strong perfect graph theorem

Cited in

(1)

• Nonsingularity of some classes of matrices, and minimal solutions of Silverman's game on discrete sets

This page was built for publication: On minimally non-firm binary matrices

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