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.

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

This page as a plain text file.
%I A355336 #11 Jul 02 2022 14:37:34
%S A355336 1,1,1,6,7,5,1,372,326
%N A355336 Number of unlabeled n-node graphs with the largest possible bipartite dimension (or biclique covering number).
%C A355336 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.
%C A355336 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.
%C A355336 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.
%H A355336 Wikipedia, <a href="https://en.wikipedia.org/wiki/Bipartite_dimension">Bipartite dimension</a>
%Y A355336 Cf. A057359, A355334, A355335.
%K A355336 nonn,more
%O A355336 1,4
%A A355336 _Pontus von Brömssen_, Jun 29 2022