A350237 Minimum number of 1's in an n X n binary matrix with no zero 3 X 3 submatrix.

0, 0, 1, 3, 5, 10, 16, 22, 32, 40, 52, 64, 77, 91, 105, 128

Offset

1,4

Comments

The submatrix's rows and columns need not be contiguous, so the following matrix does not show a(4) = 1:

....

.1..

....

....

Links

Table of n, a(n) for n=1..16.

Jeremy Tan, Python program with illustration of initial terms

Jeremy Tan, Two genies and their kind of chess, Puzzling Stack Exchange, Dec 19 2021. (shows a(8) = 22)

Jeremy Tan, What's the minimum number of people required?, Mathematics Stack Exchange, Dec 20 2021.

Jeremy Tan, An attack on Zarankiewicz's problem through SAT solving, arXiv:2203.02283 [math.CO], 2022.

Formula

a(n) = A347473(n) + 1 = n^2 - A001198(n) + 1.

a(n) = n^2 - A350304(n). - Max Alekseyev, Oct 31 2022

Example

a(4) = 3 because the following 4 X 4 binary matrix with 3 1's has no zero 3 X 3 submatrix, and all such matrices with fewer 1's have at least one zero 3 X 3 submatrix:
   1...
   .1..
   ..1.
   ....

Crossrefs

Column 3 of A339635.

Cf. A001198, A347473, A350304.

Sequence in context: A358406 A287563 A184800 * A267151 A209008 A032279

Adjacent sequences: A350234 A350235 A350236 * A350238 A350239 A350240

Keyword

nonn,hard,more

Author

Jeremy Tan, Dec 21 2021

Extensions

a(12)-a(13) from Andrew Howroyd, Dec 23 2021

a(14)-a(15) from Jeremy Tan, Jan 03 2022

a(16) from Jeremy Tan, added by Max Alekseyev, Oct 31 2022

Status

approved