Tagged Questions

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)$ ...
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 ...
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 ...
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 ...
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 ...
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) ...
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$.
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 ...
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 ...
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 ...
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 ...