A191966 -id:A191966 - 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

A335820 Number of squarefree graphs on n nodes with maximal number of edges.

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 5, 5, 10, 2, 11, 3, 2, 1, 2, 2, 1, 1, 5, 1, 1, 13, 1, 20, 9, 8, 7, 1, 2, 1, 1, 9, 18, 1, 1, 5, 11

Offset: 1

Jason Zimba, Jul 22 2020

Number of squarefree graphs on n nodes with A006855(n) edges.

			There are 2 squarefree graphs on 10 nodes that have maximal number of edges.

C. R. J. Clapham, A. Flockhart, and J. Sheehan, Graphs without Four-Cycles, Journal of Graph Theory, 31 (1989), 29-47.
D. B. West, A. Bialostocki, and J. Schonheim, E3387 (Large Graphs with No 4-cycle), The American Mathematical Monthly, 98 (Aug. - Sep. 1991), 653-655.

Unlabeled version of A191966.

Cf. A006786, A006855, A077269, A300756.

a(22)-a(37) from Brendan McKay, Mar 08 2022

A352472 Triangle T(n,k) read by rows: the number of traceless symmetric binary n X n matrices with 2k one's and no all-1 2 X 2 submatrix.

Original entry on oeis.org

1, 1, 1, 1, 3, 3, 1, 1, 6, 15, 20, 12, 1, 10, 45, 120, 195, 162, 15, 1, 15, 105, 455, 1320, 2508, 2680, 900, 1, 21, 210, 1330, 5880, 18564, 40474, 54750, 35595, 6615, 1, 28, 378, 3276, 20265, 93240, 320040, 795120, 1333080, 1323840, 619920, 90720, 1, 36, 630, 7140, 58527, 364896

Offset: 1

R. J. Mathar, Mar 17 2022

Symmetry and traceless mean that the number of 1's is always even; the corresponding zeros for odd numbers are not shown here.

			The triangle starts at 1 X 1 matrices and 0,2,4,... ones as
1: 1;
2: 1  1;
3: 1  3   3    1;
4: 1  6  15   20    12;
5: 1 10  45  120   195    162      15;
6: 1 15 105  455  1320   2508    2680     900;
7: 1 21 210 1330  5880  18564   40474   54750    35595     6615;
8: 1 28 378 3276 20265  93240  320040  795120  1333080  1323840   619920    90720;
9: 1 36 630 7140 58527 364896 1763076 6578640 18514935 37535932 50808870 40684140 15892065 1995840;

Max Alekseyev, Table of n, a(n) for n = 1..205
Index entries for sequences of squarefree graphs

Cf. A350189 (allows nonzero trace), A345249 (row sums), A006855 (row lengths minus 1), A191966 (rightmost values).

T(n,1) = A000217(n-1). - R. J. Mathar, Mar 25 2022
T(n,2) = 3*A000332(n+1). T(n,3) = A093566(n+1). - Conjectured by R. J. Mathar, Mar 25 2022; proved by Max Alekseyev, Apr 02 2022
G.f.: F(x,y) = Sum_{n,k} T(n,k)*(x^n/n!)*y^k = exp( Sum_G x^n(G) * y^e(G) / |Aut(G)| ), where G runs over the connected squarefree graphs (cf. A077269), n(G) and e(G) are the numbers of nodes and edges in G, and Aut(G) is the automorphism group of G. It follows that F(x,y) = exp(x) * (1 + (1/2)*x^2*y + ((1/2)*x^3 + (1/8)*x^4)*y^2 + ((1/6)*x^3 + (2/3)*x^4 + (1/4)*x^5 + (1/48)*x^6)*y^3 + O(y^4)), implying the above formulas for T(n,2) and T(n,3). - Max Alekseyev, Apr 02 2022

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

A335820 Number of squarefree graphs on n nodes with maximal number of edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A352472 Triangle T(n,k) read by rows: the number of traceless symmetric binary n X n matrices with 2k one's and no all-1 2 X 2 submatrix.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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