2021/07/18 by Mario Correddu, Correddu, Mario, Dario Trevisan +1
Mathematics · #FOS: Mathematics #Probability (math.PR) #math.PR
paper · pdf · doi:10.48550/arxiv.2107.08452
arxiv created 2021/07/18 · arxiv updated 2021/07/20
We consider the minimum spanning tree problem on a weighted complete bipartite graph KnR, nB whose n=nR+nB vertices are random, i.i.d. uniformly distributed points in the unit cube in d dimensions and edge weights are the p-th power of their Euclidean distance, with p>0. In the large n limit with nR/n → αR and 0<αR<1, we show that the maximum vertex degree of the tree grows logarithmically, in contrast with the classical, non-bipartite, case, where a uniform bound holds depending on d only. Despite this difference, for p<d, we are able to prove that the total edge costs normalized by the rate n1-p/d converge to a limiting constant that can be represented as a series of integrals, thus extending a classical result of Avram and Bertsimas to the bipartite case and confirming a conjecture of Riva, Caracciolo and Malatesta.