Spanning-Tree Counts versus Triangulation Counts

Definitions and mathematical statement

For a finite set $P\subset{\mathbb{R}}^2$, a crossing-free straight-line graph on $P$ has vertex set $P$, edges that are segments joining pairs of points of $P$, no vertex in the relative interior of an edge, and no intersection between edges except at a common endpoint. Let $\operatorname{st}(P)$ count such graphs that are spanning trees. For a two-dimensional configuration, let $\operatorname{tr}(P)$ count triangulations of $\operatorname{conv}(P)$ using exactly $P$ as vertices: the triangles have pairwise disjoint interiors, cover the convex hull, and meet along shared faces. Configurations, trees and triangulations are counted geometrically on the given point set, rather than up to abstract graph isomorphism.

The supplied comparison asks whether there are constants $c>1$ and $N\in{\mathbb{N}}$, independent of the configuration, such that \[ \forall P\subset{\mathbb{R}}^2\text{ finite with }|P|\geq N, \qquad \operatorname{st}(P)\geq c^{|P|}\operatorname{tr}(P). \] Thus "sufficiently large" refers uniformly to cardinality, not to spatial scale or a threshold depending on the shape of $P$. The source does not specify general position, exclude collinear point sets, or define triangulations in lower dimension. Consequently the displayed quantifier records the supplied target, but its admissible class of configurations requires clarification. In the common general-position version one would restrict that quantifier to sets with no three collinear; that additional hypothesis is not asserted by this source. If one instead extends triangulations to collinear configurations by the subdivision into consecutive segments, arbitrarily large collinear sets have only one admissible spanning tree and one such triangulation, so that convention changes the proposed assertion materially.

Short English statement

Is the number of crossing-free spanning trees uniformly larger than the number of triangulations by an exponential factor $c^{|P|}$ with $c>1$? The admissibility of degenerate point configurations must be specified before this becomes an unambiguous assertion.

Sources

• Local UnsolvedMath registry, permanent ID $30001074$, source code catalogue entry; supplied original and corrected statements. Record created 25 August 2026, updated 16 September 2026; proposed year 2008. No individual proposer is supplied.
• Discrete Geometry (2009), Oberwolfach Reports, DOI 10.4171/owr/2008/44, pp. 2477--2556: https://doi.org/10.4171/owr/2008/44. The supplied publication-year label and DOI year are retained.
• Supplied literature source, Counting crossing-free geometric graphs: https://arxiv.org/abs/1604.05350.
• Literature checked at 2026-08-21: the assessment is supplied dated curation, not independently verified. The record labels the problem open and says known enumeration and exponential bounds for the two families do not establish this uniform comparison. It explicitly calls for independent verification of time-sensitive status and cited claims.