Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #27 Oct 31 2022 09:33:23
%S 0,0,1,3,5,10,16,22,32,40,52,64,77,91,105,128
%N Minimum number of 1's in an n X n binary matrix with no zero 3 X 3 submatrix.
%C The submatrix's rows and columns need not be contiguous, so the following matrix does not show a(4) = 1:
%C ....
%C .1..
%C ....
%C ....
%H Jeremy Tan, <a href="https://gist.github.com/Parcly-Taxel/705747d9b62b29967647eb680ca4cdd4">Python program with illustration of initial terms</a>
%H Jeremy Tan, <a href="https://puzzling.stackexchange.com/q/114135">Two genies and their kind of chess</a>, Puzzling Stack Exchange, Dec 19 2021. (shows a(8) = 22)
%H Jeremy Tan, <a href="https://math.stackexchange.com/q/4335395">What's the minimum number of people required?</a>, Mathematics Stack Exchange, Dec 20 2021.
%H Jeremy Tan, <a href="https://arxiv.org/abs/2203.02283">An attack on Zarankiewicz's problem through SAT solving</a>, arXiv:2203.02283 [math.CO], 2022.
%F a(n) = A347473(n) + 1 = n^2 - A001198(n) + 1.
%F a(n) = n^2 - A350304(n). - _Max Alekseyev_, Oct 31 2022
%e 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:
%e 1...
%e .1..
%e ..1.
%e ....
%Y Column 3 of A339635.
%Y Cf. A001198, A347473, A350304.
%K nonn,hard,more
%O 1,4
%A _Jeremy Tan_, Dec 21 2021
%E a(12)-a(13) from _Andrew Howroyd_, Dec 23 2021
%E a(14)-a(15) from _Jeremy Tan_, Jan 03 2022
%E a(16) from _Jeremy Tan_, added by _Max Alekseyev_, Oct 31 2022