All Questions
12 questions
0
votes
0
answers
45
views
Functional inequalities on neighbourhood graphs
Consider an open domain $\Omega \in \mathbb{R}^d$, say the unit disk in $\mathbb{R}^2$ with $N$ points sampled i.i.d. on it. One of the simplest possible (unnormalised) discrete Laplacian of a ...
- 111
11
votes
1
answer
370
views
Graph with path of length $\geq n$ along grid diagonals - a known result in graph theory?
Is the following lemma a well known result in graph theory?
I am studying a basic existence result that appears to be simple yet powerful. I have not seen it stated as an important result in graph ...
- 6,937
4
votes
0
answers
94
views
Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius
I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ non ...
- 161
9
votes
4
answers
371
views
Diameter of random segment intersection graph?
I have an even number of points $n$ randomly distributed (uniformly) in a disk.
Then the points are randomly connected to form $n/2$ segments, a perfect
matching.
Finally, I form the intersection ...
- 151k
2
votes
1
answer
115
views
mean length of the non-crossing graphs on n points
My original question is rather vague so I'll start with a precise example and then indicate possible generalisations.
Given a n-tuple $x=(x_1,\dots,x_n)$ in, say, a square with side-length $1$ in the ...
- 1,352
7
votes
2
answers
335
views
Wait time to grid network disconnection with failing edges
Let $G_n$ be an $n \times n$ planar toroidal grid graph, with each node
connected to its four neighbors, with the top row connected to the bottom,
and the right column connected to the left.
Suppose ...
- 151k
1
vote
1
answer
313
views
Expected length of the shortest polygonal chain connecting N random points in the unit square
N points are selected uniformly at random in the unit square. Let L(N) be the expected length of the shortest (possibly self-intersecting) polygonal chain connecting all the points. It can be proved ...
24
votes
6
answers
3k
views
Shortest grid-graph paths with random diagonal shortcuts
Suppose you have a network of edges connecting
each integer lattice point
in the 2D square grid $[0,n]^2$
to each of its (at most) four neighbors, {N,S,E,W}.
Within each of the $n^2$ unit cells of ...
- 151k
10
votes
1
answer
527
views
Random geometric graphs and spanners
I would grateful to learn of work mixing
random geometric graphs with random graphs under
the
Erdős-Renyi model, and in particular concerning spanners.
Select $n$ points uniformly at random from the ...
- 151k
7
votes
3
answers
801
views
Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance Part II
For some context see Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance
As per Noah's answer and JBL's comment this was false as stated. However, I think the following ...
9
votes
1
answer
526
views
Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance
Problem: Consider a random walk on the lattice $\mathbb{Z}^2$ where on each iteration a particle either stays at its current location or moves to a neighboring vertex with probability 1/5. We start ...