1
vote
1answer
88 views

manhattan to euclidean metric

One may define a graph on a square lattice by taking the nodes of the lattice as graph vertices and the bonds of the lattice as edges. Suppose for simplicity that the nodes have integer $(x,y)$ ...
2
votes
1answer
55 views

Quasi-isometry of Schreier coset graphs

Let $G$ be a finitely generated group and $H$ a subgroup. For any choice of a generating set $X$ we can form the Schreier coset graph. Is this graph independent of the generating set up to ...
0
votes
1answer
62 views

Distance Metric in 4 dimensions $\Bbb R^3\times SO(2)$

The euclidean distance metric, $\sqrt{dx^2+dy^2+dz^2}$, shows the shortest distance between two points in $\Bbb R^3$. What would be the distance metric to show the shortest distance between two ...
1
vote
2answers
153 views

How well can we embed graphs with shortest path metric into $\mathbb{R}^2$ with Euclidean metric?

If we take the integer lattice in $\mathbb{R}^2$ and make edges from $(m,n)$ to $(m+1,n)$ and $(m,n+1)$, you get your typical city block street layout, and if we put the shortest path metric on the ...
1
vote
1answer
73 views

Star graph embeddings

This is an homework question which I'm struggling with: Let $S = (V, E, w)$ a star graph, meaning, $S$ is a tree that all it's vertices are leafs except one. I need to : show that every weighted ...
5
votes
1answer
157 views

Count number of special onto functions

We define an onto function from $[n] \times [n]$ to $[n-2] \cup \{0\}$ as follows, where $[n] = \{1,2,3,\ldots ,n\}$, $$f : [n] \times [n] \rightarrow [n-2] \cup \{0\}.$$ 1) $f(x,x) = 0$. 2) ...
0
votes
1answer
29 views

How can i bound the largest edge length of an $n$-point metric in $O(n)$?

For a given metric $d$ on a finite (vertex) set $V$, how can I bound the largest edge length in $O(|V|)$? While (wlog) assuming that the smallest edge length is at least $1$.
1
vote
2answers
135 views

How should I measure the total “closeness” of a finite number of elements?

Suppose I have n points and a way to measure the pairwise (probably non-Euclidean) distance between them. I would like to have some way to measure the total "closeness" of my points, but I'm not ...
6
votes
3answers
595 views

Largest sphere in a “grid graph”

Let $G=(V,E)$ be an undirected graph, such that $V$ is a subset of $\{1,\dotsc,N\} \times \{1,\dotsc,N\}$ and there is an edge between $2$ vertices if and only if they have one identical coordinate ...
2
votes
0answers
106 views

Probability metric spaces for which $r \leq R$ implies $\frac{Pr(B(x,r))}{Pr(B(x,R))} \geq \frac{r}{R}$

I'm looking for examples of spaces $X$ such that: $X$ is a probability space. $X$ is a metric space. If $x \in X$ and $0 < r \leq R$ then $\frac{Pr(B(x,r))}{Pr(B(x,R))} \geq \frac{r}{R}$. I ...
1
vote
0answers
155 views

l1-metric and cut metric equivalence

I would like to show that the following two statements are equivalent. Let (A, d) be an n-point metric space. And B set of $\binom{n}{2}$ pairs of points of A. $\exists t \geq 1$, integer m, and ...