Our Paper on Realizing a Graph on Random Points

A minimum spanning tree. (image source)


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 d, a graph G=(V,E), and a uniformly random
embedding f : V \rightarrow \{0,1\}^d of the vertices. We are interested in
the probability that G can be “realized” by a scaled Euclidean norm on
\mathbb{R}^d, in the sense that there exists a non-negative scaling w \in \mathbb{R}^d and a real threshold \theta > 0 so that

\displaystyle (u,v) \in E \qquad \Leftrightarrow \qquad \Vert f(u) - f(v) \Vert_w^2 < \theta\,,

where \| x \|_w^2 = \sum_i w_i x_i^2.

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 f.

In this paper, we consider embeddings f : V \rightarrow \{ x, y\}^d for
arbitrary x, y \in \mathbb{R}. We prove that arbitrary trees can be realized
with high probability when d = \Omega(n \log n). We prove an analogous result
for graphs parametrized by the arboricity: specifically, we show that an
arbitrary graph G with arboricity a can be realized with high probability
when d = \Omega(n a^2 \log n). Additionally, if r is the minimum effective
resistance of the edges, G can be realized with high probability when
d=\Omega\left((n/r^2)\log n\right). Next, we show that it is necessary to
have d \geq \binom{n}{2}/6 to realize random graphs, or d \geq n/2 to
realize random spanning trees of the complete graph. This is true even if we
permit an arbitrary embedding f : V \rightarrow \{ x, y\}^d for any x, y \in \mathbb{R} or negative weights. Along the way, we prove a probabilistic analog
of Radon’s theorem for convex sets in \{0,1\}^d.

Our tree-realization result can complement existing results on statistical
inference for gene expression data which involves realizing a tree, such as

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s