On minimally non-firm binary matrices

DOI10.1007/978-3-031-18530-4_6zbMATH Open1528.90222arXiv2206.04089OpenAlexW4313116916MaRDI QIDQ6166892FDOQ6166892

Authors: Réka Ágnes Kovács 

Publication date: 3 August 2023

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

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.

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

zbMATH Keywords

Boolean rankrectangle covering numberfirm matrices

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Algorithmic graph theory and perfect graphs
• Title not available (Why is that?)
• The strong perfect graph theorem
• On edge perfectness and classes of bipartite graphs
• Communication Complexity
• Title not available (Why is that?)
• A Combinatorial Decomposition Theory
• Title not available (Why is that?)
• Doubly Lexical Orderings of Matrices
• Title not available (Why is that?)
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• A minimax theorem on intervals
• Alternating cycle-free matchings
• The Boolean Basis Problem and How to Cover Some Polygons by Rectangles
• A notion of cross-perfect bipartite graphs

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)