A352472 -id:A352472 - cp's OEIS frontend

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

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

A191966 Number of n X n symmetric (0,1) matrices that achieve the record mentioned in A191965.

Original entry on oeis.org

1, 1, 1, 12, 15, 900, 6615, 90720, 1995840, 1360800, 197920800, 359251200, 1297296000, 7264857600, 119870150400, 2615348736000, 29640619008000, 533531142144000, 101370917007360000, 101370917007360000, 425757851430912000, 3325168819675422720000

Offset: 1

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

nonn

Number of labeled squarefree graphs on n nodes with A006855(n) edges. - Max Alekseyev, Jan 29 2022

Max Alekseyev, Table of n, a(n) for n = 1..37

Labeled version of A335820. Rightmost values in A352472.

Cf. A006786, A006855, A077269, A191965, A300756.

a191966 = lambda n: sum( factorial(n) // g.automorphism_group(return_group=False, order=True) for g in graphs.nauty_geng(options=f'-c -f {n} {oeis(6855)(n)}:0') ) # Max Alekseyev, Jan 29 2022

a(11)-a(21) from Max Alekseyev, Jan 29 2022

Corrected and extended to a(37) by Max Alekseyev, Mar 12 2023

A350189 Triangle T(n,k) read by rows: the number of symmetric binary n X n matrices with k ones and no all-1 2 X 2 submatrix.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 2, 1, 3, 6, 10, 9, 9, 4, 1, 4, 12, 28, 46, 72, 80, 80, 60, 16, 1, 5, 20, 60, 140, 296, 500, 780, 1005, 1085, 992, 560, 170, 1, 6, 30, 110, 330, 876, 1956, 4020, 7140, 11480, 16248, 19608, 20560, 16500, 9720, 3276, 360, 1, 7, 42, 182, 665, 2121, 5852, 14792, 33117, 68355, 126994, 214158

Offset: 0

R. J. Mathar, Mar 09 2022

There are 2^(n^2) binary n X n matrices (entries of {0,1}). There are 2^(n*(n+1)/2) symmetric binary matrices. There are A184948(n,k) symmetric binary n X n matrices with k ones.
This sequence is the triangle T(n,k) of symmetric binary n x n matrices with k ones but no 2 X 2 submatrix with all entries = 1. [So in the display of these matrices there is no rectangle with four 1's at the corners.]
The row lengths minus 1 are 0, 1, 3, 6, 9, 12, 17, 21, 24, 29, ... and indicate the maximum number of 1's than can be packed into a symmetric binary n X n matrix without creating an all-1 quadrangle/submatrix of order 2.

			The triangle starts
  1;
  1 1;
  1 2 2 2;
  1 3 6 10 9 9 4;
  1 4 12 28 46 72 80 80 60 16;
  1 5 20 60 140 296 500 780 1005 1085 992 560 170;
  ...
To place 4 ones, one can place 2 of them in C(n,2) ways on the diagonal and the other 2 in n*(n-1)/2 ways outside the diagonal, avoiding one matrix that builds an all-1 submatrix, which are C(n,2)*(n*(n-1)/2-1) matrices. One can place all 4 on the diagonal in C(n,4) ways. One can place 2 outside the diagonal (the other 2 mirror symmetrically) in C(n*(n-1)/2,2) ways. Sum of the 3 terms is T(n,4) = C(n,3)*(5*n+3)/2. - _R. J. Mathar_, Mar 10 2022

Max Alekseyev, Table of n, a(n) for n = 0..361 (rows 0..14; rows 0..9 from R. J. Mathar)
P. Erdos and D. Kleitman, On collections of subsets containing no 4-member boolean algebra, Proc. Am. Math. Soc. 28 (1) (1971) 87.
R. J. Mathar, Illustration of graphs with these incidence matrices
Index entries for sequences of binary matrices
Index entries for sequences of squarefree graphs

Cf. A001197 (conjectured row lengths), A352258 (row sums), A352801 (rightmost terms), A350296, A350304, A350237, A352472 (traceless symmetric).

Cf. A002378, A006331, A000217, A147875.

T(n,0) = 1.
T(n,1) = n.
T(n,2) = A002378(n-1).
T(n,3) = A006331(n-1).
T(n,4) = n*(n-1)*(n-2)*(5*n+3)/12 = A147875(n)*A000217(n-1)/3. - R. J. Mathar, Mar 10 2022
T(n,5) = n*(n-1)*(n-2)*(13*n^2-n-24)/60. T(n,6) = n*(n-1)*(n-2)*(19*n^3-18*n^2-97*n+60)/180. T(n,7) = n*(n-1)*(n-2)*(n-3)*(58*n^3+75*n^2-223*n+180)/1260. - Conjectured by R. J. Mathar, Mar 11 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^u(G) / |Aut(G)| ), where G runs over the connected squarefree graphs with loops, n(G) is the number of nodes in G, u(G) the number of ones in the adjacency matrix of G, and Aut(G) is the automorphism group of G. It follows that F(x,y) = exp(x) * (1 + x*y + x^2*y^2 + (2/3*x^3 + x^2)*y^3 + (5/12*x^4 + 3/2*x^3)*y^4 + (13/60*x^5 + 3/2*x^4 + 3/2*x^3)*y^5 + (19/180*x^6 + 7/6*x^5 + 8/3*x^4 + 2/3*x^3)*y^6 + (29/630*x^7 + 3/4*x^6 + 19/6*x^5 + 10/3*x^4)*y^7 + O(y^8)), implying the above formulas for T(n,k). - Max Alekseyev, Apr 02 2022
Conjecture: the largest k such that T(n,k) is nonzero is k = A072567(n) = A001197(n) - 1. - Max Alekseyev, Apr 03 2022

cp's OEIS Frontend

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

A191966 Number of n X n symmetric (0,1) matrices that achieve the record mentioned in A191965.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Sage

Extensions

A350189 Triangle T(n,k) read by rows: the number of symmetric binary n X n matrices with k ones and no all-1 2 X 2 submatrix.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A345249 Number of labeled simple graphs on n vertices without cycles of length 4.

Views

Author

Keywords

Links

Crossrefs