A350304 Maximum number of 1's in an n X n binary matrix without an all-ones 3 X 3 submatrix.

1, 4, 8, 13, 20, 26, 33, 42, 49, 60, 69, 80, 92, 105, 120, 128

Offset

1,2

Comments

Equivalently, the maximum number of edges in a bipartite graph that is a subgraph of K_{n,n} and has no K_{3,3} induced subgraph.

References

W. Sierpiński, Sur un problème concernant un réseau à 36 points, Ann. Soc. Polon. Math., 24: 173-174 (1951).

Links

Table of n, a(n) for n=1..16.

Wikipedia, Zarankiewicz problem

Formula

a(n) = A001198(n) - 1 = n^2 - A350237(n) = n^2 - A347473(n) - 1.

Example

Examples of a(3)=8, a(4)=13, a(5)=20, a(6)=26:
  x x x    x x x x    x x x x .    x x x x x .
  x x x    x x x .    x x x . x    x x x x . x
  x x .    x x . x    x x . x x    x x . . x x
           x . x x    x . x x x    x . x . x x
                      . x x x x    . x . x x x
                                   . . x x x x

Crossrefs

Cf. A001198, A072567, A339635, A347473, A350237.

Sequence in context: A312216 A312217 A312218 * A368612 A265382 A056738

Adjacent sequences: A350301 A350302 A350303 * A350305 A350306 A350307

Keyword

nonn,more

Author

Andrew Howroyd, Dec 24 2021

Extensions

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

Status

approved