Invariant bipartite random graphs on ${\mathbb{R}}^d$

Abstract

Suppose that red and blue points occur in ${\mathbb{R}}^d$ according to two simple point process with finite intensities ${\lambda }_{\mathcal{R}}$ and ${\lambda }_{\mathcal{B}}$, respectively. Furthermore, let $\nu$ and $\mu$ be two probability distributions on the strictly positive integers. Assign independently a random number of stubs (half-edges) to each red and blue point with laws $\nu$ and $\mu$, respectively. We are interested in translation-invariant schemes to match stubs between points of different colors in order to obtain random bipartite graphs in which each point has a prescribed degree distribution with law $\nu$ or $\mu$ depending on its color. Let $X$ and $Y$ be random variables with law $\nu$ and $\mu$, respectively. For a large class of point processes we show that we can obtain such translation-invariant schemes matching a.s. all stubs if and only if \[ λ_{\mathcal{R}} \mathbb{E}(X)= λ_{\mathcal{B}} \mathbb{E}(Y), \] allowing $\infty$ in both sides, when both laws have infinite mean. Furthermore, we study a particular scheme based on the Gale-Shapley stable marriage. For this scheme we give sufficient conditions on $X$ and $Y$ for the presence and absence of infinite components. These results are two-color versions of those obtained by Deijfen, Häggström and Holroyd.

arXiv admin note: text overlap with arXiv:1002.1943 by other authors