Convex (0, 1)-matrices and their epitopes

DOI10.1016/J.DAM.2021.02.038MaRDI QIDQ2022503zbMATH OpenOpenAlexFDO

Authors Richard A. Brualdi, Geir Dahl

Publication date 29 April 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

convexityessential setpermutation matrixpolyominozero-one matrix

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Polyominoes (05B50) Matrices of integers (15B36)

Abstract: We investigate $(0,1)$-matrices that are {em convex}, which means that the ones are consecutive in every row and column. These matrices occur in discrete tomography. The notion of ranked essential sets, known for permutation matrices, is extended to convex sets. We show a number of results for the class $mcC(R,S)$ of convex matrices with given row and column sum vectors $R$ and $S$. Also, it is shown that the ranked essential set uniquely determines a matrix in $mcC(R,S)$.

Recommendations

• On certain convex matrix sets
• Rank of convex combinations of matrices
• Matrices with prescribed row and column sums
• scientific article; zbMATH DE number 3557805
• Optimization and reconstruction of hv-convex (0,1)-matrices

Cites work

• 3412, 4231 patterns produce singular points of essential sets.
• A new characterization of matrices with the consecutive ones property
• Bijection between bigrassmannian permutations maximal below a permutation and its essential set
• Combinatorial matrix theory
• Combinatorics of Fulton's essential set
• Decomposition algorithms for reconstructing discrete sets with disjoint components
• Enumeration of bigrassmannian permutations below a permutation in Bruhat order
• Flags, Schubert polynomials, degeneracy loci, and determinantal formulas
• Incidence matrices and interval graphs
• Matrices of zeros and ones with given line sums and a zero block
• More combinatorics of Fulton's essential set
• On comparability of bigrassmannian permutations
• Optimization and reconstruction of \(hv\)-convex (0,1)-matrices
• Reconstructing binary matrices under window constraints from their row and column sums
• Reconstruction of \(hv\)-convex binary matrices from their absorbed projections
• Reconstruction of convex 2D discrete sets in polynomial time
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The reconstruction of polyominoes from their orthogonal projections
• The size of Fulton's essential set

This page was built for publication: Convex \((0, 1)\)-matrices and their epitopes

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