cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-8 of 8 results.

A191874 Number of n X n (0,1) matrices that achieve the record mentioned in A191873.

Original entry on oeis.org

1, 1, 1, 8, 405, 2520, 4320, 32781000, 256556160, 10590199200, 2225341641600, 28746722188800
Offset: 1

Views

Author

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

Keywords

Comments

Also, number of directed graphs on n labeled nodes that do not contain a subgraph isomorphic to the complete directed bipartite graph K_{2,2} and have largest number of edges (=A191873(n)). - Max Alekseyev, Feb 07 2022

Crossrefs

Cf. A191873.

Extensions

a(8)-a(12) from Max Alekseyev, Feb 07 2022

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

Views

Author

Max Alekseyev, Feb 07 2022

Keywords

Comments

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.

Examples

			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.

Crossrefs

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

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

Views

Author

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

Keywords

Comments

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

References

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

Links

Crossrefs

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

Formula

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

Extensions

a(11)-a(40) computed from A006855 by Max Alekseyev, Jan 28 2022; Apr 02 2022; Mar 14 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

Views

Author

N. J. A. Sloane

Keywords

Comments

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

References

  • 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).

Crossrefs

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.

Extensions

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

Views

Author

N. J. A. Sloane

Keywords

References

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

Links

Crossrefs

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.

Extensions

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

Views

Author

N. J. A. Sloane

Keywords

References

  • 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).

Crossrefs

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.

Extensions

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

Views

Author

N. J. A. Sloane

Keywords

References

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

Links

Crossrefs

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.

Extensions

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

Views

Author

N. J. A. Sloane

Keywords

References

  • 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).

Crossrefs

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.

Extensions

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.