Component behaviour and excess of random bipartite graphs near the critical point

Tuan Anh Do, Joshua Erde, Mihyun Kang, Michael Missethan

Research output: Working paper

Abstract

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 $\frac{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.
Original languageEnglish
Number of pages35
Publication statusPublished - 31 May 2021

Keywords

  • random bipartite graph
  • giant component
  • excess

Fingerprint

Dive into the research topics of 'Component behaviour and excess of random bipartite graphs near the critical point'. Together they form a unique fingerprint.

Cite this