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

0, 2, 6, 12, 19, 27, 39, 51, 65, 81, 98, 116, 139, 163, 188, 214, 242, 272, 303, 335, 375, 413, 453

Offset

2,2

Comments

Related to Zarankiewicz's problem k_2(n) (cf. A001197 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 2 X 2 submatrix. This complementarity leads to the given formula which was used to compute the given values.

See A347473 and A347474 for the similar problem with a 3 X 3 resp. 4 X 4 zero submatrix.

Links

Table of n, a(n) for n=2..24.

Formula

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

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

Example

For n = 2, there must not be any nonzero entry in an n X n = 2 X 2 matrix, if one wants a 2 X 2 zero submatrix, whence a(2) = 0.
For n = 3, having at most 2 nonzero entries in the n X n matrix still guarantees that there is a 2 X 2 zero submatrix (delete the row of the first nonzero entry and then the column of the remaining nonzero entry, if any), but if one allows 3 nonzero entries and they are placed on the diagonal, then there is no 2 X 2 zero submatrix. Hence, a(3) = 2.

Crossrefs

Cf. A001197 (k_2(n)), A001198 (k_3(n)), A006613 - A006626.

Cf. A347473, A347474 (analog for 3 X 3 resp. 4 X 4 zero submatrix).

Cf. A350296.

Sequence in context: A104969 A065005 A299016 * A033154 A340663 A354759

Adjacent sequences: A347469 A347470 A347471 * A347473 A347474 A347475

Keyword

nonn,hard,more

Author

M. F. Hasler, Sep 28 2021

Extensions

a(22)-a(24) computed from A001197 by Max Alekseyev, Feb 08 2022

Status

approved