How to Realize a Graph on Random Points

Authors Saad Altaful Quader, Alexander Russell

Publication date 23 April 2018

Abstract: We are given an integer

d

, a graph

G = (V, E)

, and a uniformly random embedding

f : V i g h t a r r o w {0, 1}^{d}

of the vertices. We are interested in the probability that

G

can be "realized" by a scaled Euclidean norm on

m a t h b b R^{d}

, in the sense that there exists a non-negative scaling

w i n m a t h b b R^{d}

and a real threshold

h e t a > 0

so that [ (u,v) in E qquad ext{if and only if} qquad Vert f(u) - f(v) Vert_w^2 < heta,, ] where

| x |_{w}^{2} = s u m_{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 i g h t a r r o w {x, y}^{d}

for arbitrary

x, y i n m a t h b b R

. We prove that arbitrary trees can be realized with high probability when

d = O m e g a (n l o g 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 = O m e g a (n a^{2} l o g n)

. Additionally, if

r

is the minimum effective resistance of the edges,

G

can be realized with high probability when

d = O m e g a l e f t ((n / r^{2}) l o g n i g h t)

. Next, we show that it is necessary to have

to realize random graphs, or

d g e q n / 2

to realize random spanning trees of the complete graph. This is true even if we permit an arbitrary embedding

f : V i g h t a r r o w {x, y}^{d}

for any

x, y i n m a t h b b 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].

This page was built for publication: How to Realize a Graph on Random Points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6300706)