A347474 Maximum number of nonzero entries allowed in an n X n matrix to ensure there is a 4 X 4 zero submatrix.

0, 2, 4, 6, 12, 19, 25, 34, 43, 51

Offset: 4

Author

M. F. Hasler, Sep 28 2021

Keywords

• nonn
• hard
• more

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.

Examples

			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.

Formula

a(n) = n^2 - A006616(n).

a(n) = A339635(n,4) - 1. - Andrew Howroyd, Dec 23 2021

Extensions

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

a(13) computed from A006616 by Max Alekseyev, Feb 02 2024