Invariant Bipartite Random Graphs on Rd. (September 2014)

• Record Type: Journal Article
• Authors: Lopes, Fabio
• Is Part Of: Journal of applied probability. Volume 51:Number 3(2014)
• Page Start: 769
• Page End: 779
• Publication Date: 2014-09
• Subjects: Poisson process, -- random graph, -- bipartite, -- stable matching, -- percolation; 60D05, -- 60G55, -- 05C80; 519.2
• DOI: 10.1017/S0021900200011669
• Languages: English
• ISSNs: 0021-9002

Abstract

Abstract : Suppose that red and blue points occur inR d according to two simple point processes with finite intensities λ R and λ B, respectively. Furthermore, let ν and μ be two probability distributions on the strictly positive integers with means ν̅ and μ̅, respectively. Assign independently a random number of stubs (half-edges) to each red (blue) point with law ν (μ). We are interested in translation-invariant schemes for matching stubs between points of different colors in order to obtain random bipartite graphs in which each point has a prescribed degree distribution with law ν or μ depending on its color. For a large class of point processes, we show that such translation-invariant schemes matching almost surely all stubs are possible if and only if λ R ν̅ = λ B μ̅, including the case when ν̅ = μ̅ = ∞ so that both sides are infinite. Furthermore, we study a particular scheme based on the Gale-Shapley stable marriage problem. For this scheme, we give sufficient conditions on ν and μ for the presence and absence of infinite components. These results are two-color versions of those obtained by Deijfen, Holroyd and Häggström.