Geodesic
Component behaviour and excess of random bipartite graphs near the critical point
Tuan Do1 ; Joshua Erde2 ; Mihyun Kang3 ; Michael Missethan3
1Tu Graz
2Universität Hamburg
3TU Graz
The electronic journal of combinatorics, Tome 30 (2023) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/11065
Classification : 05C80, 05A16, 05C75
Mots-clés : weakly supercritical regime, inhomogeneous random graphs

Tuan Do  1   ; Joshua Erde  2   ; Mihyun Kang  3   ; Michael Missethan  3

1 Tu Graz
2 Universität Hamburg
3 TU Graz 
@article{10_37236_11065,
     author = {Tuan Do and Joshua Erde and Mihyun Kang and Michael Missethan},
     title = {Component behaviour and excess of random bipartite graphs near the critical point},
     journal = {The electronic journal of combinatorics},
     year = {2023},
     volume = {30},
     number = {3},
     doi = {10.37236/11065},
     zbl = {1519.05217},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11065/}
}
TY  - JOUR
AU  - Tuan Do
AU  - Joshua Erde
AU  - Mihyun Kang
AU  - Michael Missethan
TI  - Component behaviour and excess of random bipartite graphs near the critical point
JO  - The electronic journal of combinatorics
PY  - 2023
VL  - 30
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11065/
DO  - 10.37236/11065
ID  - 10_37236_11065
ER  - 
%0 Journal Article
%A Tuan Do
%A Joshua Erde
%A Mihyun Kang
%A Michael Missethan
%T Component behaviour and excess of random bipartite graphs near the critical point
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/11065/
%R 10.37236/11065
%F 10_37236_11065
Tuan Do; Joshua Erde; Mihyun Kang; Michael Missethan. Component behaviour and excess of random bipartite graphs near the critical point. The electronic journal of combinatorics, Tome 30 (2023) no. 3. doi: 10.37236/11065

Cité par Sources :