How to Realize a Graph on Random Points Article Swipe

MAKE IMPACT

Saad Quader , Alexander Russell · YOU? · · 2018 · Open Access · · DOI: https://doi.org/10.48550/arxiv.1804.08680

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 $θ> 0$ so that \[ (u,v) \in E \qquad \text{if and only if} \qquad \Vert f(u) - f(v) \Vert_w^2 < θ\,, \] 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 = Ω(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 = Ω(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=Ω\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].

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/1804.08680

PDF

https://arxiv.org/pdf/1804.08680

OA Status

green

References

3

Related Works

20

OpenAlex ID

https://openalex.org/W2798355620

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W2798355620

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.1804.08680

Digital Object Identifier

Title

How to Realize a Graph on Random Points

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2018

Year of publication

Publication date

2018-04-23

Full publication date if available

Authors

Saad Quader, Alexander Russell

List of authors in order

Landing page

https://arxiv.org/abs/1804.08680

Publisher landing page

PDF URL

https://arxiv.org/pdf/1804.08680

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/1804.08680

Direct OA link when available

Concepts

Arboricity, Combinatorics, Omega, Embedding, Graph, Realization (probability), Mathematics, Random graph, Discrete mathematics, Euclidean geometry, Tree (set theory), Physics, Planar graph, Geometry, Computer science, Statistics, Artificial intelligence, Quantum mechanics

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

References (count)

3

Number of works referenced by this work

Related works (count)

20

Other works algorithmically related by OpenAlex

Full payload