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

0, 2, 4, 9, 15, 21, 31, 39, 51, 63, 76, 90, 104, 127

Offset: 3

Author

M. F. Hasler, Sep 28 2021

Keywords

• nonn
• hard
• more

Comments

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.

Examples

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

Crossrefs

Cf. A001198 (k_3(n)), A001197 (k_2(n)), A006613 - A006626 (other sizes of the main matrix and the submatrix).

Cf. A347472, A347474 (analog for 2 X 2 resp. 4 X 4 zero submatrix).

Cf. A339635, A350237, A350304.

Formula

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

a(n) = A350237(n) - 1. - Andrew Howroyd, Dec 24 2021

a(n) = n^2 - A350304(n) - 1. - Max Alekseyev, Oct 31 2022

Extensions

a(11)-a(13) from Andrew Howroyd, Dec 24 2021

a(14)-a(16) computed from A350237 by Max Alekseyev, Apr 01 2022, Oct 31 2022