We study the joint components in a random 'double graph' that is obtained by superposing red and blue binomial random graphs on $n$~vertices. A joint component is a maximal set of vertices that supports both a red and a blue spanning tree. We show that there are critical pairs of red and blue edge densities at which a giant joint component appears. In contrast to the standard binomial graph model, the phase transition is first order: the size of the largest joint component jumps from $O(1)$ vertices to $\Theta(n)$ at the critical point. We connect this phenomenon to the properties of a certain bicoloured branching process.
@article{10_37236_8846,
author = {Mark Jerrum and Tam\'as Makai},
title = {The size of the giant joint component in a binomial random double graph},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {1},
doi = {10.37236/8846},
zbl = {1459.05303},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8846/}
}
TY - JOUR
AU - Mark Jerrum
AU - Tamás Makai
TI - The size of the giant joint component in a binomial random double graph
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/8846/
DO - 10.37236/8846
ID - 10_37236_8846
ER -
%0 Journal Article
%A Mark Jerrum
%A Tamás Makai
%T The size of the giant joint component in a binomial random double graph
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/8846/
%R 10.37236/8846
%F 10_37236_8846
Mark Jerrum; Tamás Makai. The size of the giant joint component in a binomial random double graph. The electronic journal of combinatorics, Tome 28 (2021) no. 1. doi: 10.37236/8846
