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
Examples
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. ....
Links
- 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) = n^2 - A350304(n). - Max Alekseyev, Oct 31 2022
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
Comments