|
%I #17 Oct 31 2022 09:38:41
%S 0,2,4,9,15,21,31,39,51,63,76,90,104,127
%N Maximum number of nonzero entries allowed in an n X n matrix to ensure there is a 3 X 3 zero submatrix.
%C Related to Zarankiewicz's problem k_3(n) (cf. A001198 and other crossrefs), which asks the converse: how many 1's must be in an n X n {0,1}-matrix in order to guarantee the existence of an all-ones 3 X 3 submatrix. This complementarity leads to the given formula which was used to compute the given values.
%F a(n) = n^2 - A001198(n).
%F a(n) = A350237(n) - 1. - _Andrew Howroyd_, Dec 24 2021
%F a(n) = n^2 - A350304(n) - 1. - _Max Alekseyev_, Oct 31 2022
%e For n = 3, there must not be any nonzero entry in an n X n = 3 X 3 matrix, if one wants a 3 X 3 zero submatrix, whence a(3) = 0.
%e For n = 4, having at most 2 nonzero entries in the n X n matrix guarantees that there is a 3 X 3 zero submatrix (delete, e.g., the row which has the first nonzero entry, then the column with the remaining nonzero entry, if any), but if one allows 3 nonzero entries and they are placed on the diagonal, then there is no 3 X 3 zero submatrix. Hence, a(4) = 2.
%Y Cf. A001198 (k_3(n)), A001197 (k_2(n)), A006613 - A006626 (other sizes of the main matrix and the submatrix).
%Y Cf. A347472, A347474 (analog for 2 X 2 resp. 4 X 4 zero submatrix).
%Y Cf. A339635, A350237, A350304.
%K nonn,hard,more
%O 3,2
%A _M. F. Hasler_, Sep 28 2021
%E a(11)-a(13) from _Andrew Howroyd_, Dec 24 2021
%E a(14)-a(16) computed from A350237 by _Max Alekseyev_, Apr 01 2022, Oct 31 2022
|
