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,2

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

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

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

Formula

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

Crossrefs

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

Sequence in context: A226485 A213638 A376456 * A173064 A111367 A105059

Adjacent sequences: A191962 A191963 A191964 * A191966 A191967 A191968

Keyword

nonn,more

Author

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

Extensions

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

Status

approved