On Minimal Spanning Trees for Random Euclidean Bipartite Graphs

The minimum spanning tree (MST) problem is a combinatorial optimization problem with many applications, well beyond its historical introduction for network design. The study of its random instances on Euclidean models, e.g., on complete graphs obtained by sampling i.i.d. uniform points on a d-dimensional cube, is classical, with many limit results as the number of the points grows. In this talk, I will present two new results for its bipartite counterpart, i.e., with an additional colouring (red/blue) of the points and allowing connections only between different colours. First, we prove that the maximum vertex degree of the MST grows logarithmically, in contrast with the non-bipartite case, where a uniform bound holds, depending on d only -- a fact crucially used in many classical results. Despite this difference, we then argue that the cost of the MST, suitably normalized, converge a.s. to a limiting constant that can be represented as a series of integrals, thus extending a result of Avram and Bertsimas to the bipartite case and confirming a conjecture by Riva, Malatesta and Caracciolo. Joint work with M. Correddu, Università di Pisa.