How many times can two minimum spanning trees cross?

arXiv:2601.20060v1 Announce Type: new
Abstract: Let $P$ be a generic set of $n$ points in the plane, and let $P=Rcup B$ be a coloring of $P$ in two colors. We are interested in the number of crossings between the minimum spanning trees (MSTs) of $R$ and $B$, denoted by $crossAB(R,B)$. We define the emph{bicolored MST crossing number} of $P$, denoted by $cross(P)$, as $cross(P) = max_{P= Rcup B}(crossAB(R,B))$. We prove a linear upper bound for $cross(P)$ when $P$ is generic. If $P$ is dense or in convex position, we provide linear lower bounds. Lastly, if $P$ is chosen uniformly at random from the unit square and is colored uniformly at random, we prove that the expected value of $crossAB(R,B)$ is linear.