Bipartite Stable Poisson Graphs on R

M. Deijfen, F.M. Lopes

2012, v.18, Issue 4, 583-594

ABSTRACT

Let red and blue points be distributed on $R$ according to two independent Poisson processes $\mathcal{R}$ and $\mathcal{B}$ and let each red (blue) point independently be equipped with a random number of half-edges according to a probability distribution $\nu$ ($\mu$). We consider translation-invariant bipartite random graphs with vertex classes defined by the point sets of $\mathcal{R}$ and $\mathcal{B}$, respectively, generated by a scheme based on the Gale\tire Shapley stable marriage for perfectly matching the half-edges. Our main result is that, when all vertices have degree 2, then the resulting graph almost surely does not contain an infinite component. The two-color model is hence qualitatively different from the one-color model, where Deijfen, Holroyd and Peres have given strong evidence that there is an infinite component. We also present simulation results for other degree distributions.

Keywords: Poisson process,random graph,degree distribution,percolation,matching

COMMENTS

Please log in or register to leave a comment