Our paper, titled How to Realize a Graph on Random Points, has been accepted at CCCG (Canadian Conference on Computational Geometry) 2019. I’ll write more about it in future posts.
We are given an integer , a graph , and a uniformly random
embedding of the vertices. We are interested in
the probability that can be “realized” by a scaled Euclidean norm on
, in the sense that there exists a non-negative scaling and a real threshold so that
These constraints are similar to those found in the Euclidean minimum
spanning tree (EMST) realization problem. A crucial difference is that the
realization map is (partially) determined by the random variable .
In this paper, we consider embeddings for
arbitrary . We prove that arbitrary trees can be realized
with high probability when . We prove an analogous result
for graphs parametrized by the arboricity: specifically, we show that an
arbitrary graph with arboricity can be realized with high probability
when . Additionally, if is the minimum effective
resistance of the edges, can be realized with high probability when
. Next, we show that it is necessary to
have to realize random graphs, or to
realize random spanning trees of the complete graph. This is true even if we
permit an arbitrary embedding for any or negative weights. Along the way, we prove a probabilistic analog
of Radon’s theorem for convex sets in .
Our tree-realization result can complement existing results on statistical
inference for gene expression data which involves realizing a tree, such as