A350304 - OEIS

%I #24 Oct 31 2022 09:35:46

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

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

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

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

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Zarankiewicz_problem">Zarankiewicz problem</a>

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

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

%e   x x x    x x x x    x x x x .    x x x x x .

%e   x x x    x x x .    x x x . x    x x x x . x

%e   x x .    x x . x    x x . x x    x x . . x x

%e            x . x x    x . x x x    x . x . x x

%e                       . x x x x    . x . x x x

%e                                    . . x x x x

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

%K nonn,more

%O 1,2

%A _Andrew Howroyd_, Dec 24 2021

%E a(14)-a(16) computed from A350237 by _Max Alekseyev_, Apr 01 2022, Oct 31 2022