login

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”).

A347474
Maximum number of nonzero entries allowed in an n X n matrix to ensure there is a 4 X 4 zero submatrix.
9
0, 2, 4, 6, 12, 19, 25, 34, 43, 51
OFFSET
4,2
COMMENTS
Related to Zarankiewicz's problem k_4(n) (cf. A006616 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 4 X 4 submatrix. This complementarity leads to the given formula which was used to compute the given values.
FORMULA
a(n) = n^2 - A006616(n).
a(n) = A339635(n,4) - 1. - Andrew Howroyd, Dec 23 2021
EXAMPLE
For n < 4, there is no solution, since there cannot be a 4 X 4 submatrix in a matrix of smaller size.
For n = 4, there must not be any nonzero entry in an n X n = 4 X 4 matrix, if one wants a 4 X 4 zero submatrix, whence a(4) = 0.
For n = 5, having at most 2 nonzero entries in the n X n matrix guarantees that there is a 4 X 4 zero submatrix (delete, e.g., the row with the first nonzero entry, then the column with the second nonzero entry, if any), but if one allows 3 nonzero entries and they are placed on the diagonal, then there is no 4 X 4 zero submatrix. Hence, a(5) = 2.
CROSSREFS
Cf. A347472, A347473 (analog for 2 X 2 resp. 3 X 3 zero submatrix).
Cf. A006616 (k_4(n)), A001198 (k_3(n)), A001197 (k_2(n)), A006613 - A006626.
Cf. A339635.
Sequence in context: A358650 A357546 A294918 * A370638 A331872 A307067
KEYWORD
nonn,hard,more
AUTHOR
M. F. Hasler, Sep 28 2021
EXTENSIONS
a(9)-a(12) from Andrew Howroyd, Dec 23 2021
a(13) computed from A006616 by Max Alekseyev, Feb 02 2024
STATUS
approved