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

Author

Andrew Howroyd, Dec 24 2021

Keywords

• nonn
• more

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.

Examples

			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
		

References

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

Links

• Wikipedia, Zarankiewicz problem

Crossrefs

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

Formula

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

Extensions

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