Dear colleagues,

we are happy to announce the following online talk:

Speaker: *Dario Trevisan* (Università di Pisa)

Title: *On Minimal Spanning Trees for Random Euclidean Bipartite Graphs*

Abstract: 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.

Date and time: *Monday July 12, 17:30-18:30 (Rome time zone)*

*Zoom link:* https://us02web.zoom.us/j/5772228296

This is a talk of the *(PMS)^2: Pavia-Milano Seminar series on Probability and Mathematical Statistics* organized jointly by the universities Milano-Bicocca, Pavia, Milano-Politecnico and Milano-Statale. For more information see the dedicated webpage: https://paviamilanoseminars.wordpress.com/

Participation is free and welcome!

Best regards The organizers (Mario Maurelli, Carlo Orrieri, Maurizia Rossi, Margherita Zanella)