Minimum-cost matching in a random graph with random costs

Original · EN

Let Gₙ,ₚ be the standard Erdős-Rényi-Gilbert random graph and let Gₙ,ₙ,ₚ be the random bipartite graph on n+n vertices, where each e∈ [n]² appears as an edge independently with probability p. For a graph G=(V,E), suppose that each edge e∈ E is given an independent uniform exponential rate one cost. Let C(G) denote the random variable equal to the length of the minimum cost perfect matching, assuming that G contains at least one. We show that w.h.p. if d=np≫(n)² then w.h.p. E[C(Gₙ,ₙ,ₚ)] =(1+o(1))²/6p. This generalises the well-known result for the case G=Kₙ,ₙ. We also show that w.h.p. E[C(Gₙ,ₚ)] =(1+o(1))²/12p along with concentration results for both types of random graph.