A191874 -id:A191874 - cp's OEIS frontend

A191873 A problem of Zarankiewicz: maximal number of 1's in an 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, 9, 12, 16, 21, 24, 29, 34, 39, 45

Offset: 1

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

In other words, the pattern
  1...1
  .....
  1...1
is forbidden.
From Don Knuth, Aug 13 2014: (Start)
Well, it is well known from A001197 that a(8)<25. A001197 is essentially the same problem, but increased by 1, and without restricting the diagonals. The diagonal restriction is however of little interest, because it's easy to permute rows and columns and get all 0's or all 1's or probably any of the 2^n possible settings of the diagonal. At least, this is true when n=8; hence a(8) in this sequence is 24.
Transposing cols 1<->4 and 5<->8 in the example by Guy 1967 page 130 as cited in A001197 gives a(8)=24:
  01110000
  10010100
  00010011
  01000101
  10100010
  11001000
  00101001
  00001110
But as stated above, I think this is quite trivial, and I believe this sequence should be downplayed. Readers should look at the sequence A001197 --- that's what Zarankiewicz's problem asked for in 1951, namely the min number that forces a rectangle, not the max number that doesn't exclude it. (End)
Conjecture: for n >= 3, a(n) = A072567(n) = A001197(n) - 1 (per above comment). - Max Alekseyev, Jan 29 2022

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

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

Cf. A072567, A191874, A191965, A191966.

a(8) confirmed, a(9)-a(12) added by Max Alekseyev, Feb 07 2022

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.

Original entry on oeis.org

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

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

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

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

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

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

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

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

A351335 Number of unlabeled directed graphs on n nodes without a subgraph isomorphic to directed K_{2,2} that have the maximal number of edges (=A191873(n)).

Original entry on oeis.org

1, 1, 1, 1, 6, 5, 4, 829, 707, 2938, 55779, 60084

Offset: 1

Max Alekseyev, Feb 07 2022

When adjacency matrices viewed as those of bipartite graphs, these bipartite graphs are pairwise isomorphic for each n <= 12, except for n = 5 and n = 8 with 2 and 3 distinct bipartite graphs, respectively.

			For n = 7 there are 4 such graphs with A191873(7) = 21 edges, described by the following adjacency matrices:
[0111000]   [0110100]   [0110010]   [0010101]
[1010100]   [1011000]   [1000011]   [1001001]
[1100010]   [1000101]   [0101001]   [0100011]
[0100101]   [1100010]   [1100100]   [1010010]
[0010011]   [0010011]   [1011000]   [0111000]
[1001001]   [0101001]   [0010101]   [1100100]
[0001110]   [0001110]   [0001110]   [0001110]
Absence of directed K_{2,2} subgraph means that these matrices do not contain a rectangle with four 1s at the corners.

Unlabeled version of A191874.
Directed version of A335820.
Cf. A191873.

A352801 Number of symmetric n X n 01-matrices with maximum number of 1s and no 2 X 2 all-1 submatrix.

Original entry on oeis.org

1, 1, 2, 4, 16, 170, 360, 840, 82320, 181440, 1512000, 19958400, 79833600, 259459200, 14529715200

Offset: 0

Max Alekseyev, Apr 03 2022

Cf. A072567, A191874, A191966, A335820, A350189, A351335, A352258.

a(n) is the last element in the n-th row of triangle A350189.

Conjecture: the maximum number of 1s equals A072567(n), and so a(n) = A350189(n, A072567(n)).

cp's OEIS Frontend

A191873 A problem of Zarankiewicz: maximal number of 1's in an 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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A351335 Number of unlabeled directed graphs on n nodes without a subgraph isomorphic to directed K_{2,2} that have the maximal number of edges (=A191873(n)).

Views

Author

Keywords

Comments

Examples

Crossrefs

A352801 Number of symmetric n X n 01-matrices with maximum number of 1s and no 2 X 2 all-1 submatrix.

Views

Author

Keywords

Crossrefs

Formula