14 problems

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…

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…

Let $P_n$ consist of $n$ independent random points uniformly distributed in $[0,1]^2$. Probabilistic upper-bound conjecture. The maximum EMST-ratio of $P_n$ is less than $2$ with p…

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…

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…

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…

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 $\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 $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…