Asymptotics for the number of bipartite graphs with fixed surplus

Abstract

In a recent work on the bipartite Erdős-Rényi graph, Do et al. (2023) established upper bounds on the number of connected labeled bipartite graphs with a fixed surplus. We use some recent encodings of bipartite random graphs in order to provide a probabilistic formula for the number of bipartite graphs with fixed surplus. Using this, we obtain asymptotics as the number of vertices in each class tend to infinity.

arXiv comment15 pages, 2 figures