All Questions
Tagged with random-graphs mg.metric-geometry
12 questions
6
votes
1
answer
257
views
Expected doubling constant of a random Erdős–Rényi graph
Consider the $G(n,p)$ random graph model where $n$ is a ``large'' positive integer and $p\in (0,1)$. We may equip every realized random graph $G$ with its shortest path distance, making it into a (...
- 5,407
1
vote
0
answers
64
views
Angles between edges of a geometric graph and graph invariants
Are there any clever ways in which the angles between edges in a geometric graph are encoded in the graph spectrum, or another object associated with the graph?
I'm interested to see what else is ...
- 640
4
votes
1
answer
566
views
Random graphs and Benjamini-Schramm convergence
I am looking for literature on the question whether a randomly chosen sequence of $k$-regular graphs converges in the Benjamini-Schramm sense to the universal covering with probability one.
There are ...
user130903
4
votes
3
answers
430
views
How to show that random graphs cannot be embedded with short edges
For each (not necessarily planar) embedding of a graph in $\mathbb{R}^k$ one can calculate the ratio
$$\gamma = \frac{\textsf{mean Euclidean length of edges}}{\textsf{mean Euclidean distance between ...
- 9,720
1
vote
0
answers
79
views
Generation of randomly looking graph coordinates
Let $G$ be some connected graph. We pick randomly $k$ distinct vertices $l_1, l_2, \cdots l_k \in V(G)$. We call them the landmarks.
We define $d(u,v)$ to be the length of the shortest path between ...
- 323
6
votes
5
answers
1k
views
Generate random graphs that satisfy the triangle inequality
I would like to generate random graphs that might be geometric graphs in some
(unknown) dimension. So I would like every triangle in the graph to satisfy the
triangle inequality on its (random) edge ...
- 151k
0
votes
0
answers
320
views
Gromov-Hausdorff distance measure between minimum spanning trees
I am trying to compare minimum spanning trees through time. I have two questions:
1-Is it possible to measure the similarity between two minimum spanning trees with Gromov-Hausdorff distance measure ...
- 1
8
votes
1
answer
314
views
Longest induced cycles in random geometric graphs near criticality
We make a random geometric graph $X(n;r)$ as follows. Choose $n$ points uniformly, independently, in the unit square $[0,1]^2$, for vertices, and then connect a pair of vertices $\{ p,q \}$ by an edge ...
- 7,857
8
votes
0
answers
181
views
Can two random graphs be metrically embedded into one another?
Let $X, Y$ be two random graphs on $n$ vertices (say, in $G(n, p)$ model for some $p$). Can anything (expectation, value with high probabiity, ...) be said about $D(X, Y)$, where $D$ is the minimal ...
- 3,323
2
votes
0
answers
163
views
Reachability in dynamic random graphs
There has been some advice on how to ask questions. So I reask my question.I have a problem related to graph theory, random graphs or random geometric graphs in special that really confuses me. ...
- 35
13
votes
3
answers
835
views
What fraction of n-point sets in the unit ball have diameter smaller than 1?
This question is inspired by a recent talk by Matt Kahle on random geometric complexes.
Some simple notation: let $\mathcal{B} \subset \mathbb{R}^d$ be the unit ball in $d$-dimensional Euclidean ...
- 15.5k
4
votes
2
answers
882
views
The probability distribution for vertex degree in a unit disc graph generated from random points on a plane
Imagine I cover an arbitrarily large plane with randomly placed points at some density $\rho$ s.t. the number of points in any randomly sampled area $A$ (of arbitrary shape and size) is $\approx A*\...
