2021/05/31 by Do, Tuan Anh, Erde, Joshua, Kang, Mihyun +1 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2105.14883
The binomial random bipartite graph G(n,n,p) is the random graph formed by taking two partition classes of size n and including each edge between them independently with probability p. It is known that this model exhibits a similar phase transition as that of the binomial random graph G(n,p) as p passes the critical point of (1)/(n). We study the component structure of this model near to the critical point. We show that, as with G(n,p), for an appropriate range of p there is a unique `giant' component and we determine asymptotically its order and excess. We also give more precise results for the distribution of the number of components of a fixed order in this range of p. These results rely on new bounds for the number of bipartite graphs with a fixed number of vertices and edges, which we also derive.