A191965 A problem of Zarankiewicz: maximal number of 1's in a symmetric n X n matrix of 0's and 1's with 0's on the main diagonal and no "rectangle" with 1's at the four corners.

0, 2, 6, 8, 12, 14, 18, 22, 26, 32, 36, 42, 48, 54, 60, 66, 72, 78, 84, 92, 100, 104, 112, 118, 126, 134, 142, 152, 160, 170, 180, 184, 192, 204, 212, 220, 226, 234, 244, 254

Offset: 1

Author

R. H. Hardin and N. J. A. Sloane, Jun 18 2011

Keywords

• nonn
• more

Comments

In other words, the pattern

1...1

.....

1...1

is forbidden.

Such matrices are adjacency matrices of squarefree graphs (cf. A006786). The number of matrices with a(n) ones is given by A191966 and A335820 (up to permutations of rows/columns). - Max Alekseyev, Jan 29 2022

References

• B. Bollobas, Extremal Graph Theory, pp. 309ff.

Links

• D. Bienstock E. Gyori, An extremal problem on sparse 0-1 matrices. SIAM J. Discrete Math. 4 (1991), 17-27.

Crossrefs

Cf. A006786, A006855, A077269, A191873 A191874, A191966, A300756, A335820, A352472.

Formula

a(n) = 2 * A006855(n). - Max Alekseyev, Jan 29 2022

Extensions

a(11)-a(40) computed from A006855 by Max Alekseyev, Jan 28 2022; Apr 02 2022; Mar 14 2023