26 problems

A minimum spanning tree is a shortest connection of a finite set $A$ of points in the plane by segments with endpoints in $A$. The Steiner ratio is the infimum, over finite point s…

Let $\rho_2$ denote the infimum, over finite point sets in the Euclidean plane, of the length of a Steiner tree divided by the length of a Euclidean minimum spanning tree. Gilbert–…

Let $G_n$ be an expander sequence converging locally to the $d$-regular tree. Consider the local limits associated with item c., a sequence of $d$-regular expanders with $n$ vertic…

Let $(W_{\vec e})_{\vec e\in\vec E}$ be i.i.d. weights with continuous distributions supported in $(0,\infty)$, rather than i.i.d. Exponential$(1)$ weights. Let the main theorem as…

Let $P$ be a finite point set in the plane, and let $\operatorname{cr-MST}(P)$ denote its bicolored minimum spanning tree crossing number. The NP-hardness conjecture. Finding…

Let $P$ be a generic set of $n$ points in the plane. The linear lower-bound conjecture. … The authors identify this as the most important problem for improving the lower bound for…

Omission conjecture. This assumption can be omitted, and the main result remains true. This concerns whether the giant component in the finite graph remains locally visible and rea…

Let $P_n$ consist of $n$ independent random points uniformly distributed in $[0,1]^2$, and let a bipartite coloring of $P_n$ be any coloring induced by a Euclidean minimum spanning…

For a finite point set in the plane and a red-blue partition, the chromatic crossing number is the number of crossings between an edge of $\operatorname{EMST}(R)$ and an edge of…

Let $P\subseteq\mathbb{R}^2$ be a finite point set. A bipartite coloring is obtained by choosing a Euclidean minimum spanning tree of $P$ and partitioning $P=R\cup B$ so that every…

For a point set in Euclidean space, the $k$-MAX-EMST-ratio problem restricts the input to $k$ dimensions. Fixed-dimensional hardness conjecture. The $k$-MAX-EMST-ratio problem for…

For a finite point set $P$ in the plane, let $\rho$ denote the infimum, over all such point sets, of the ratio between the length of a shortest Steiner tree and the length of a min…

Let $P$ be a set of $n$ points in the plane. Write $w(P)$ for the length of a Euclidean minimum spanning tree of $P$, and let … where the maximum is over all non-trivial bipartitio…

Extremal lower-bound conjecture. One should have

Let $n_R$ and $n$ denote the number of red points and the total number of points, respectively, and suppose that $n_R/n\to 1/2$. Let $f_R$ and $f_B$ be the densities of the red and…

Let $G=(V,E)$ be a graph that admits a star spanning tree $T_s$. Let $\mathscr{T}_G$ denote the set of spanning trees of $G$, and let $\cap(T)$ be the intersection number of a span…

Shi et al.'s conjecture. The version of BMST in which both the leader and the follower have a sum objective is NP-hard.

Let the node weights of an inhomogeneous random graph or a configuration-model graph follow a distribution with a power-law tail of parameter $4 > \alpha > 3$, and assign i.i.d. ca…

Let $\gamma_i$ be the limiting weight constant for the $i$th successive minimum spanning tree, and define the cumulative constant … Let $\overline{\Gamma}_k$ denote the numerical u…

For each $k\geqslant1$, let $\sigma_k$ be the threshold at which the limiting giant-component function $\rho_k(t)$ becomes positive. Threshold asymptotics conjecture. There exists…

For each $k\geqslant1$, let $\rho_k(t)$ be the limiting fraction of vertices in the largest component of the $k$th Kruskal forest, and let $\sigma_k>0$ be its giant-component thres…

For each $k\geqslant1$, let $\gamma_k$ be the limiting constant for the weight of the $k$th successive minimum spanning tree. Sharp weight bounds conjecture. For every…

For each $k\geqslant1$, let $\gamma_k$ be the constant to which the weight of the $k$th successive minimum spanning tree converges in probability. Asymptotic linearity conjecture.…

For each $k\geqslant1$, let $F_k(t)$ be the forest produced by Kruskal's algorithm at time $t$, and let $\rho_k(t)$ be the limiting fraction of vertices in its largest component. T…

Successive minimum spanning tree weight conjecture. As $k\to\infty$,