𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the maximum density of 0–1 matrices with no forbidden rectangles

✍ Scribed by David Peleg

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
215 KB
Volume
140
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 combinatorics (cf. [1,2]) involves the maximum density of a 0-1 matrix with a certain forbidden configuration. This note handles a specific question of this type, arising from [3].

Consider an N x N 0-1 matrix M. The rows and columns of M are numbered 0 ..... N-I.

A rectanffle in the matrix M is a quadruple (011,0~2, fll, f12) , for 0 ~< ctt, 0t2, fl,, f12 ~< N-1. The rectangle (~q, ~2, fl,, f12) is said to be full if

It is well known that the maximum density in an N x N 0-1 matrix with no full rectangle is O (N a/2) (cf. [2] ). The question we are actually interested in is slightly more complex. It is assumed that the size of the matrix is a power of 2, N = 2 n. We think of the row and column numbers of the matrix as given in binary representation, i.e., each row or column number is represented as a string of n bits ~=~n-t ...~lCtO • In the problem we consider, not all rectangles are forbidden. Rather, a rectangle Supported in part by an AIIon Fellowship, by a Bantrell Fellowship and by a Walter and Elise Haas Career Development Award.

📜 SIMILAR VOLUMES

(0,1)-Matrices with No Half–Half Submatr
(0,1)-Matrices with No Half–Half Submatrix of Ones
✍ J.R. Griggs; J. Ouyang 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 137 KB

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

Advising on the law. Policestation skill
Advising on the law. Policestation skills for legal advisers. Eric Shepherd and the Law Society. The Law Society, London. Price £110.00 for complete kit, comprising: Becoming skilled. A resource book. Eric Shepherd. No. of pages: 428. ISBN 1-85328-207-3; Putting skills into practice. A workbook. Eric Shepherd. No. of pages: 223. ISBN 1-85328-222-7; A supervisor's guide. Eric Shepherd. No. of pages 126. ISBN 1-85328-217-0; A pocket reference. Eric Shepherd. No. of pages: 53. ISBN 1-85328-227-8; Advising a suspect in the plice station. Guidelines for solicitors. Criminal Law Committee of the Law Society. No. of pages: 95 ISBN 1-85328-049-6; Police station activity log. Record sheets, with no author or ISBN number
✍ Isabel Clare 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 265 KB 👁 3 views
H. B. N. HYNES: A Key to the Adults and
H. B. N. HYNES: A Key to the Adults and Nymphs of British Stoneflies (Plecoptera) with Notes on their Ecology and Distribution. Third edition. = Scientific Publication No. 17.- With 47 fig., 1 map, 92 pp. Far Sawrey, Ambleside: Freshwater Biological Association 1977. ISBN 900386 28 2. £ 0.40
✍ H. Caspers 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 95 KB 👁 1 views

Buchbesprechungen 171 flos-aquae-und Aphanizomenon-Wasserbliiten sind nicht immer toxisch, wie der nicht vorbelastete Leser aus der Passage auf S. 23 schlielen wiirde; wieso sind ,,Blaualgen oft nahezu die einzigen Algen, die in stark mit organischen Abwassern verschmutztem Wasser noch wachsen konne