(0, 1)-matrices with no half-half submatrix of ones
type: Item
instance of: scholarly article
title: (0, 1)-matrices with no half-half submatrix of ones
zbMATH Open document ID: 0887.05037
author: J. Ning
published in: European Journal of Combinatorics
publication date: 1997-12-14T00:00:00Z
review text: If \(m\), \(n\) are arbitrary positive integers, let \(f(m,n)\) denote the minimum number of zeroes in a \(2m\times 2n\) matrix whose all entires are \(0\) or \(1\), and which contains no \(m\times n\) submatrix of ones. The authors prove that then \(f(m,n)\leq 2m+ 2n-\text{gcd}(m, n)+1\) and \(f(m, n)\geq m+2n+ 1\) for \(m\leq n\). If \(m\leq n\) and \(m\) is fixed, they also prove that \(f(m,n)= m+2n+1\) if and only if \(n= m\) or all but finitely many \(n\) are greater than \(m\).
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05B20
zbMATH DE Number: 1088572
zbMATH Keywords: zeroes
zbMATH Keywords: matrix
reviewed by: Aleksandar Torgašev
MaRDI profile type: Publication
full work available at URL: eujc.1996.0133
OpenAlex ID: W2041071418
DOI: 10.1006/EUJC.1996.0133
description: scientific article; zbMATH DE number 1088572