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-3 of 3 results.

A355333 Triangle read by rows: T(n,k) is the number of n X n Boolean matrices with Schein rank k, 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 9, 6, 1, 49, 306, 156, 1, 225, 8550, 40656, 16104, 1, 961, 194850, 5771100, 21165720, 6421800
Offset: 0

Views

Author

Pontus von Brömssen, Jun 29 2022

Keywords

Comments

Also, T(n,k) is the number of spanning subgraphs of the complete bipartite graph K_{n,n} that have bipartite dimension (or biclique covering number) k.

Examples

			Triangle begins:
  n\k | 0   1      2       3        4       5
  ----+--------------------------------------
   0  | 1
   1  | 1   1
   2  | 1   9      6
   3  | 1  49    306     156
   4  | 1 225   8550   40656    16104
   5  | 1 961 194850 5771100 21165720 6421800

Links

Crossrefs

Cf. A002416 (row sums), A064230, A286331, A354741, A355334.

A355335 Triangle read by rows: T(n,k) is the number of unlabeled connected graphs with n nodes and bipartite dimension (or biclique covering number) k, 0 <= k < n.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 4, 0, 0, 2, 13, 6, 0, 0, 3, 38, 67, 4, 0, 0, 3, 94, 550, 205, 1, 0, 0, 4, 214, 3996, 6543, 360, 0, 0, 0, 4, 441, 25037, 176012, 59266, 320, 0, 0
Offset: 1

Views

Author

Pontus von Brömssen, Jun 29 2022

Keywords

Examples

			Triangle begins:
  n\k | 0  1   2     3      4     5   6  7  8
  ----+--------------------------------------
   1  | 1
   2  | 0  1
   3  | 0  1   1
   4  | 0  2   4     0
   5  | 0  2  13     6      0
   6  | 0  3  38    67      4     0
   7  | 0  3  94   550    205     1   0
   8  | 0  4 214  3996   6543   360   0  0
   9  | 0  4 441 25037 176012 59266 320  0  0

Links

Crossrefs

Cf. A001349 (row sums), A004526 (column k=1), A355334, A355336.

Formula

T(n,1) = floor(n/2) = A004526(n).

A355336 Number of unlabeled n-node graphs with the largest possible bipartite dimension (or biclique covering number).

Original entry on oeis.org

1, 1, 1, 6, 7, 5, 1, 372, 326
Offset: 1

Views

Author

Pontus von Brömssen, Jun 29 2022

Keywords

Comments

Let b(n) be the largest bipartite dimension of an n-node graph. Then b(n) >= A057359(n). If, for all n >= 8, there exists a disconnected n-node graph with bipartite dimension b(n), then b(n) = A057359(n) for all n >= 1. Proof: Since the bipartite dimension of a graph equals the sum of the bipartite dimensions of its connected components, we have that b(n) >= max_{k=1..n-1} b(k)+b(n-k) (i.e., the sequence is superadditive), with equality if there exists a disconnected n-node graph with bipartite dimension b(n). It is easily checked that A057359(n) = max_{k=1..n-1} A057359(k)+A057359(n-k) for n >= 8. Since b(n) = A057359(n) for 1 <= n <= 7 (checked by brute force), the result follows.
Since (b(n)) is superadditive, it follows from Fekete's subadditive lemma that the limit of b(n)/n exists and equals the supremum of b(n)/n. It is easy to see that b(n) <= b(n-1) + 1, so this limit is between 5/7 = b(7)/7 and 1.
The numbers of disconnected n-node graphs with bipartite dimension b(n) for 1 <= n <= 9 are 0, 0, 0, 2, 1, 1, 0, 12, 6.

Links

Crossrefs

Cf. A057359, A355334, A355335.
Showing 1-3 of 3 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.