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

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

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

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

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

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

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

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