# Our Paper on Realizing a Graph on Random Points

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.

Abstract:

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
[GJP15].