A191965 -id:A191965 - cp's OEIS frontend

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

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

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.

Original entry on oeis.org

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

A006855 Maximum number of edges in an n-node squarefree graph, or, in a graph containing no 4-cycle, or no C_4.

Original entry on oeis.org

0, 1, 3, 4, 6, 7, 9, 11, 13, 16, 18, 21, 24, 27, 30, 33, 36, 39, 42, 46, 50, 52, 56, 59, 63, 67, 71, 76, 80, 85, 90, 92, 96, 102, 106, 110, 113, 117, 122, 127

Offset: 1

N. J. A. Sloane

Keywords to help find this entry: C4-free. C_4-free, no 4-cycle, squarefree, quadrilateral-free, Zarankiewicz problem.
Lower bounds that have a good chance of being exact: a(41) >= 132, a(42) >= 137, a(43) >= 142, a(44) >= 148, a(45) >= 154, a(46) >= 157, a(47) >= 163, a(48) >= 168, a(49) >= 174. - Brendan McKay, Mar 08 2022
Upper bounds: a(41) <= 133, a(42) <= 139, a(43) <= 145, a(44) <= 151, a(45) <= 158, a(46) <= 165, a(47) <= 171, a(48) <= 176, a(49) <= 182. - Max Alekseyev, Jan 26 2023

M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 1999. Chap. 20 gives a simple proof of the upper bound (n/4)(sqrt(4n-3)+1) and of the fact that it is asymptotically tight. - Christopher E. Thompson, Aug 14 2001
P. Kovari, V. T. Sos, and P. Turan. On a problem of K. Zarankiewicz, Colloq. Math. (4th ed.), 3 (1954), pp. 50-57.
Brendan McKay, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Max A. Alekseyev, On computing sets of integers with maximum number of pairs summing to powers of 2, arXiv:2303.02872 [math.CO], 2023.
C. R. J. Clapham, A. Flockhart, and J. Sheehan, Graphs without four-cycles, J. Graph Theory 13 (1) (1989) 29-47
Zoltán Füredi, Quadrilateral-free graphs with maximum number of edges, Extended abstract, Proceedings of the Japan Workshop on Graph Th. and Combinatorics, University, Yokohama, Japan 1994, pp. 13-22 (see Section 6).
Zoltán Füredi, On the number of edges of quadrilateral-free graphs, J. Combin. Theory (B) 68 (1996), 1-6.
Jie Ma and Tianchi Yang, Upper bounds on the extremal number of the 4-cycle, arxiv:2107.11601 (2021).
Brendan McKay, Extremal Graphs and Turan numbers.

See A335820 for the number of graphs that achieve a(n).

a(n) <= n^(3/2)*(1/2 + o(1)) [Kovari, Sos, Turan]. But the upper bound mentioned in the Aigner-Ziegler reference (see above) is stronger. - N. J. A. Sloane, Mar 07 2022
a(n) = A191965(n)/2. - Max Alekseyev, Apr 02 2022
For n > 2, a(n) <= floor(a(n-1) * n / (n-2)). - Max Alekseyev, Jan 26 2023

a(23)-a(31) from Michel Marcus, Jul 23 2014
a(32)-a(39) from Brendan McKay, Mar 08 2022
a(40) from Brendan McKay, communicated by Max Alekseyev, Mar 13 2023

A006620 A variant of Zarankiewicz's problem: a(n) is the least k such that every n X (n+1) {0,1}-matrix with k ones contains an all-ones 2 X 2 submatrix.

Original entry on oeis.org

5, 8, 11, 15, 19, 23, 27, 32, 37, 43, 49, 54, 59, 64

Offset: 2

N. J. A. Sloane

a(n) <= A205805(2*n+1) + 1. - Max Alekseyev, Feb 02 2024

R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Cf. A006613, A006614, A006615, A006616, A006617, A006618, A006619, A006621, A006622, A006623, A006624, A006625, A006626.

Cf. A001197, A072567, A191965, A191873, A001198, A205805, A347473, A347474, A350304, A350237.

Name changed at the suggestion of Sean A. Irvine by Max Alekseyev, Feb 02 2024

A006614 A variant of Zarankiewicz's problem: a(n) is the least k such that every n X n {0,1}-matrix with k ones contains an all-ones 2 X 4 submatrix.

Original entry on oeis.org

14, 21, 26, 32, 41, 48, 56, 67

Offset: 4

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. K. Guy, A problem of Zarankiewicz, Research Paper No. 12, Dept. of Math., Univ. Calgary, Jan. 1967. [Annotated and scanned copy, with permission]
R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.
Dmitry I. Ignatov, When contranominal scales give a solution to the Zarankiewicz problem?, Workshop Notes, 12th Int'l Wksp. Formal Concept Analysis Artif. Intel. (FCA4AI 2024), 27-38. See p. 35.

Cf. A006613, A006615, A006616, A006617, A006618, A006619, A006620, A006621, A006622, A006623, A006624, A006625, A006626.

Cf. A001197, A072567, A191965, A191873, A001198, A205805, A347473, A347474, A350304, A350237.

Name updated at the suggestion of Sean A. Irvine by Max Alekseyev, Feb 02 2024

A006615 A variant of Zarankiewicz's problem: a(n) is the least k such that every n X n {0,1}-matrix with k ones contains an all-ones 3 X 4 submatrix.

Original entry on oeis.org

15, 22, 31, 38, 46, 57

Offset: 4

N. J. A. Sloane

R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Cf. A006613, A006614, A006616, A006617, A006618, A006619, A006620, A006621, A006622, A006623, A006624, A006625, A006626.

Cf. A001197, A072567, A191965, A191873, A001198, A205805, A347473, A347474, A350304, A350237.

Name changed at the suggestion of Sean A. Irvine and a(9) added by Max Alekseyev, Feb 02 2024

A006622 A variant of Zarankiewicz's problem: a(n) is the least k such that every n X (n+1) {0,1}-matrix with k ones contains an all-ones 3 X 4 submatrix.

Original entry on oeis.org

12, 18, 26, 33, 41, 51

Offset: 3

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. K. Guy, A problem of Zarankiewicz, Research Paper No. 12, Dept. of Math., Univ. Calgary, Jan. 1967. [Annotated and scanned copy, with permission]
R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.

Cf. A006613, A006614, A006615, A006616, A006617, A006618, A006619, A006620, A006621, A006623, A006624, A006625, A006626.

Cf. A001197, A072567, A191965, A191873, A001198, A205805, A347473, A347474, A350304, A350237.

Name edited at the suggestion of Sean A. Irvine and a(8) added by Max Alekseyev, Feb 02 2024

A006625 A variant of Zarankiewicz's problem: a(n) is the least k such that every n X (n+2) {0,1}-matrix with k ones contains an all-ones 3 X 4 submatrix.

Original entry on oeis.org

14, 21, 28, 36, 45, 55

Offset: 3

N. J. A. Sloane

R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Cf. A006613, A006614, A006615, A006616, A006617, A006618, A006619, A006620, A006621, A006622, A006623, A006624, A006626.

Cf. A001197, A072567, A191965, A191873, A001198, A205805, A347473, A347474, A350304, A350237.

Name changed at the suggestion of Sean A. Irvine and a(8) added by Max Alekseyev, Feb 02 2024

cp's OEIS Frontend

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

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

A006855 Maximum number of edges in an n-node squarefree graph, or, in a graph containing no 4-cycle, or no C_4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A006620 A variant of Zarankiewicz's problem: a(n) is the least k such that every n X (n+1) {0,1}-matrix with k ones contains an all-ones 2 X 2 submatrix.

Views

Author

Keywords

Comments

References

Crossrefs

Extensions

A006614 A variant of Zarankiewicz's problem: a(n) is the least k such that every n X n {0,1}-matrix with k ones contains an all-ones 2 X 4 submatrix.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A006615 A variant of Zarankiewicz's problem: a(n) is the least k such that every n X n {0,1}-matrix with k ones contains an all-ones 3 X 4 submatrix.

Views

Author

Keywords

References

Crossrefs

Extensions

A006622 A variant of Zarankiewicz's problem: a(n) is the least k such that every n X (n+1) {0,1}-matrix with k ones contains an all-ones 3 X 4 submatrix.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A006625 A variant of Zarankiewicz's problem: a(n) is the least k such that every n X (n+2) {0,1}-matrix with k ones contains an all-ones 3 X 4 submatrix.

Views

Author

Keywords

References

Crossrefs

Extensions