MathDB

Given positive integers

k \ge 2

and

m

sufficiently large. Let

\mathcal{F}_m

be the infinite family of all the (not necessarily square) binary matrices which contain exactly

m

1's. Denote by

f(m)

the maximum integer

L

such that for every matrix

A \in \mathcal{F}_m

, there always exists a binary matrix

B

of the same dimension such that (1)

B

has at least

L

1-entries; (2) every entry of

B

is less or equal to the corresponding entry of

A

; (3)

B

does not contain any

k \times k

all-1 submatrix. Show the equality

\lim_{m \to \infty} \frac{\ln f(m)}{\ln m}=\frac{k}{k+1}.

Problem Statement