𝔖 Bobbio Scriptorium
✦   LIBER   ✦

(0,1)-Matrices with No Half–Half Submatrix of Ones

✍ Scribed by J.R. Griggs; J. Ouyang

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
137 KB
Volume
18
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the minimum number of zeroes in a 2m × 2n (0, 1)-matrix M that contains no m × n submatrix of ones. We show that this number, denoted by f (m, n), is at least 2n + m + 1 for m ≤ n. We determine exactly when this bound is sharp and determine the extremal matrices in these cases. For any m, the bound is sharp for n = m and for all but finitely many n > m. A general upper bound due to Gentry, f (m, n) ≤ 2m + 2ngcd(m, n) + 1, is also derived. Our problem is a special case of the well-known Zarankiewicz problem.

📜 SIMILAR VOLUMES

On the maximum density of 0–1 matrices w
On the maximum density of 0–1 matrices with no forbidden rectangles
✍ David Peleg 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 215 KB

This note provides bounds for the maximal number of ones allowed in an N x N 0-1 matrix, N = 2 n, in which there are no 'forbidden rectangles' of a special type. ## 1. Introduction The density of a 0-1 matrix is defined as the number of l's that occur in it. A typical problem in extremal combinato