o****i
发帖数: 23 | 1 借本版问个问题。以下命题是否正确？有无reference可以参考？谢谢！
"Any edge-weighted undirected graph can be isometrically embedded into some
Riemannian manifold."
这里的isometric embedding指的是任意两点在图中的最短路径距离等于在manifold上
的geodesic距离。
我是computer science的，在最近的工作中需要用到这一步，不知道在数学领域是不是
已经有人做过了。我Google了一下没有找到。 |
Q***5
发帖数: 994 | 2 图论一窍不通。你说的 weight满足三角不等式吗？ |
o****i
发帖数: 23 | 3
谢谢你的回复。这里是想把一个基于最短路径距离的graph metric嵌入到riemannian
manifold, graph metric 肯定是满足三角不等式的。
这个问题可以换个问法，与图论无关：is it true that any finite discrete metric
space can be isometrically embedded into a Riemannian manifold?
【在 Q***5 的大作中提到】
: 图论一窍不通。你说的 weight满足三角不等式吗？
|
f*c
发帖数: 687 | 4 Assume all triangle inequalities hold strictly, i.e. the length
of the edge linking vertices p_i and p_j is at least 100\epsilon shorter
than any other path (through other vertices) from p_i to p_j, and assume the
edge linking p_i, p_j has length at least 100\epsilon.
How about this: For each vertex p_i, take a 2-sphere S_i of radius
\epsilon and choose a point x_i on S_i; if there is a edge linking
p_i, p_j, we punch a hole on S_i and a hole on S_j (avoiding x_i
x_j), then link S_i, S_j by a thin tube of length 10\epsilon less than the
edge lenth p_ip_j. Thus (smoothing the corners...) we get a surface S. The
distance x_ix_j, roughly speaking is about 10\epsilon shorter than what we
want, but we can stretch (i.e. make it longer by changing metric) the tube
linking S_i, S_j; by continuity we can get the desired value of d(x_i, x_j)
.
So you can embedd the graph into the 2-d surface S. |
o****i
发帖数: 23 | 5 谢谢你的解答。我有一些想法和疑问，等今天晚上有时间再来这里回复。
the
【在 f*c 的大作中提到】
: Assume all triangle inequalities hold strictly, i.e. the length
: of the edge linking vertices p_i and p_j is at least 100\epsilon shorter
: than any other path (through other vertices) from p_i to p_j, and assume the
: edge linking p_i, p_j has length at least 100\epsilon.
: How about this: For each vertex p_i, take a 2-sphere S_i of radius
: \epsilon and choose a point x_i on S_i; if there is a edge linking
: p_i, p_j, we punch a hole on S_i and a hole on S_j (avoiding x_i
: x_j), then link S_i, S_j by a thin tube of length 10\epsilon less than the
: edge lenth p_ip_j. Thus (smoothing the corners...) we get a surface S. The
: distance x_ix_j, roughly speaking is about 10\epsilon shorter than what we
|
o****i
发帖数: 23 | 6 我觉得你提的用manifold来模拟一个graph的想法很有意思， 我也有过类似的想法，还
有下面几个问题，有的可能比较业余：
1。 怎么保证球面和tube的连接处是光滑的，也就是indefinitely differentiable?
我记得几何书上讲partition of unity的时候会用smooth function来模拟平台函数，
这里也可以用类似的方法么？
2。 你是构造了一个三维欧氏空间里的二维曲面么？需不需要specify每个点上的
riemannian metric? 是不是就用dot product作为inner product就可以了？
3。如果这个命题是正确的，那看起来是一个很general的结论，为什么网上和书上都没
有呢？
谢谢
the
【在 f*c 的大作中提到】
: Assume all triangle inequalities hold strictly, i.e. the length
: of the edge linking vertices p_i and p_j is at least 100\epsilon shorter
: than any other path (through other vertices) from p_i to p_j, and assume the
: edge linking p_i, p_j has length at least 100\epsilon.
: How about this: For each vertex p_i, take a 2-sphere S_i of radius
: \epsilon and choose a point x_i on S_i; if there is a edge linking
: p_i, p_j, we punch a hole on S_i and a hole on S_j (avoiding x_i
: x_j), then link S_i, S_j by a thin tube of length 10\epsilon less than the
: edge lenth p_ip_j. Thus (smoothing the corners...) we get a surface S. The
: distance x_ix_j, roughly speaking is about 10\epsilon shorter than what we
|
w***w
发帖数: 84 | 7 Riemannian metric 太general 了，对discrete set, 多的研究是embed到更加有结构
的空间，比如欧式空间。 |
f*c
发帖数: 687 | 8
连接的地方用（换）一个warped product metric 就可以了。
没有在3维空间里。小球和tube(即s^1times [0, L])都用标准 intrinsic 度量。
即使有Nash的定理，把曲面嵌入欧氏空间好像也没有什么益处。距离空间如果包含
至少四个点，一般就不可能等距嵌入欧氏空间。
【在 o****i 的大作中提到】
: 我觉得你提的用manifold来模拟一个graph的想法很有意思， 我也有过类似的想法，还
: 有下面几个问题，有的可能比较业余：
: 1。 怎么保证球面和tube的连接处是光滑的，也就是indefinitely differentiable?
: 我记得几何书上讲partition of unity的时候会用smooth function来模拟平台函数，
: 这里也可以用类似的方法么？
: 2。 你是构造了一个三维欧氏空间里的二维曲面么？需不需要specify每个点上的
: riemannian metric? 是不是就用dot product作为inner product就可以了？
: 3。如果这个命题是正确的，那看起来是一个很general的结论，为什么网上和书上都没
: 有呢？
: 谢谢
|
w***w
发帖数: 84 | 9 任何有限集上的metric 可以等距嵌入l_\infty. Bourgain证明任何n个点可以嵌入欧式
空间
with O(log n) multiplicative distortion. 这些有不少算法上的应用。 |
o****i
发帖数: 23 | 10 对，(A) O(log n)－distortion的嵌入到欧氏空间 和 (B) isometrically嵌入到
infinity-norm空间我最近两三年研究过，也得到一些partial results发了领域内top
journal的文章。但是这两种嵌入对我的问题来说都有缺陷。(A)的问题是有distortion
, 而我最终要证明的是一个绝对的等式，所以用(A)只能得到一些bound. (B)的问题是
，嵌入之后很难做进一步的处理。l_infinity空间的文献和结论好像不多，感觉
structure过于复杂，不好办。
我本来感觉Riemannian manifold有可能综合(A)和(B)的优点，就是既可以等距嵌入（
待检验），又和熟悉的欧式空间有关系（每个点局部同构于欧式空间）。但是看前面的
回复，有可能不加限制的Riemannian metric还是象l_infitity一样过于复杂。
【在 w***w 的大作中提到】
: 任何有限集上的metric 可以等距嵌入l_\infty. Bourgain证明任何n个点可以嵌入欧式
: 空间
: with O(log n) multiplicative distortion. 这些有不少算法上的应用。
|
|
|
o****i
发帖数: 23 | 11 谢谢解释。warped product metric我没听说过，这两天找资料研究一下。
考虑三维欧式空间做ambient space一个可能的好处，就是如果需要的话，可以保证被
嵌入的完全图任意两条边不相交。(平面图可以嵌入二维平面保证任两条边不相交，任
意图都可以嵌入三维空间保证任两条边不相交。)
Nash embedding theorem说任意riemannian manifold可以等距嵌入到欧式空间，而一
个graph又不可以等距嵌入到欧式空间，所以一年前我以为这两个结论就决定了graph
metric不可能等距嵌入到riemannian manifold. 最近我意识到这个想法是错的，因为
Nash定理说的是嵌入之前和之后的geodesic距离相等，而不是嵌入之前的geodesic距离
和嵌入之后的欧式空间直线距离相等。
【在 f*c 的大作中提到】
:
: 连接的地方用（换）一个warped product metric 就可以了。
: 没有在3维空间里。小球和tube(即s^1times [0, L])都用标准 intrinsic 度量。
: 即使有Nash的定理，把曲面嵌入欧氏空间好像也没有什么益处。距离空间如果包含
: 至少四个点，一般就不可能等距嵌入欧氏空间。
|
o****i
发帖数: 23 | 12 谢谢comment. 我看到有文章研究往constant sectional curvature的Riemannian
manifold嵌入，那又太特殊了。
欧式空间没法保证graph metric的等距嵌入。
【在 w***w 的大作中提到】
: Riemannian metric 太general 了，对discrete set, 多的研究是embed到更加有结构
: 的空间，比如欧式空间。
|
o****i
发帖数: 23 | 13 借本版问个问题。以下命题是否正确？有无reference可以参考？谢谢！
"Any edge-weighted undirected graph can be isometrically embedded into some
Riemannian manifold."
这里的isometric embedding指的是任意两点在图中的最短路径距离等于在manifold上
的geodesic距离。
我是computer science的，在最近的工作中需要用到这一步，不知道在数学领域是不是
已经有人做过了。我Google了一下没有找到。 |
Q***5
发帖数: 994 | 14 图论一窍不通。你说的 weight满足三角不等式吗？ |
o****i
发帖数: 23 | 15
谢谢你的回复。这里是想把一个基于最短路径距离的graph metric嵌入到riemannian
manifold, graph metric 肯定是满足三角不等式的。
这个问题可以换个问法，与图论无关：is it true that any finite discrete metric
space can be isometrically embedded into a Riemannian manifold?
【在 Q***5 的大作中提到】
: 图论一窍不通。你说的 weight满足三角不等式吗？
|
f*c
发帖数: 687 | 16 Assume all triangle inequalities hold strictly, i.e. the length
of the edge linking vertices p_i and p_j is at least 100\epsilon shorter
than any other path (through other vertices) from p_i to p_j, and assume the
edge linking p_i, p_j has length at least 100\epsilon.
How about this: For each vertex p_i, take a 2-sphere S_i of radius
\epsilon and choose a point x_i on S_i; if there is a edge linking
p_i, p_j, we punch a hole on S_i and a hole on S_j (avoiding x_i
x_j), then link S_i, S_j by a thin tube of length 10\epsilon less than the
edge lenth p_ip_j. Thus (smoothing the corners...) we get a surface S. The
distance x_ix_j, roughly speaking is about 10\epsilon shorter than what we
want, but we can stretch (i.e. make it longer by changing metric) the tube
linking S_i, S_j; by continuity we can get the desired value of d(x_i, x_j)
.
So you can embedd the graph into the 2-d surface S. |
o****i
发帖数: 23 | 17 谢谢你的解答。我有一些想法和疑问，等今天晚上有时间再来这里回复。
the
【在 f*c 的大作中提到】
: Assume all triangle inequalities hold strictly, i.e. the length
: of the edge linking vertices p_i and p_j is at least 100\epsilon shorter
: than any other path (through other vertices) from p_i to p_j, and assume the
: edge linking p_i, p_j has length at least 100\epsilon.
: How about this: For each vertex p_i, take a 2-sphere S_i of radius
: \epsilon and choose a point x_i on S_i; if there is a edge linking
: p_i, p_j, we punch a hole on S_i and a hole on S_j (avoiding x_i
: x_j), then link S_i, S_j by a thin tube of length 10\epsilon less than the
: edge lenth p_ip_j. Thus (smoothing the corners...) we get a surface S. The
: distance x_ix_j, roughly speaking is about 10\epsilon shorter than what we
|
o****i
发帖数: 23 | 18 我觉得你提的用manifold来模拟一个graph的想法很有意思， 我也有过类似的想法，还
有下面几个问题，有的可能比较业余：
1。 怎么保证球面和tube的连接处是光滑的，也就是indefinitely differentiable?
我记得几何书上讲partition of unity的时候会用smooth function来模拟平台函数，
这里也可以用类似的方法么？
2。 你是构造了一个三维欧氏空间里的二维曲面么？需不需要specify每个点上的
riemannian metric? 是不是就用dot product作为inner product就可以了？
3。如果这个命题是正确的，那看起来是一个很general的结论，为什么网上和书上都没
有呢？
谢谢
the
【在 f*c 的大作中提到】
: Assume all triangle inequalities hold strictly, i.e. the length
: of the edge linking vertices p_i and p_j is at least 100\epsilon shorter
: than any other path (through other vertices) from p_i to p_j, and assume the
: edge linking p_i, p_j has length at least 100\epsilon.
: How about this: For each vertex p_i, take a 2-sphere S_i of radius
: \epsilon and choose a point x_i on S_i; if there is a edge linking
: p_i, p_j, we punch a hole on S_i and a hole on S_j (avoiding x_i
: x_j), then link S_i, S_j by a thin tube of length 10\epsilon less than the
: edge lenth p_ip_j. Thus (smoothing the corners...) we get a surface S. The
: distance x_ix_j, roughly speaking is about 10\epsilon shorter than what we
|
w***w
发帖数: 84 | 19 Riemannian metric 太general 了，对discrete set, 多的研究是embed到更加有结构
的空间，比如欧式空间。 |
f*c
发帖数: 687 | 20
连接的地方用（换）一个warped product metric 就可以了。
没有在3维空间里。小球和tube(即s^1times [0, L])都用标准 intrinsic 度量。
即使有Nash的定理，把曲面嵌入欧氏空间好像也没有什么益处。距离空间如果包含
至少四个点，一般就不可能等距嵌入欧氏空间。
【在 o****i 的大作中提到】
: 我觉得你提的用manifold来模拟一个graph的想法很有意思， 我也有过类似的想法，还
: 有下面几个问题，有的可能比较业余：
: 1。 怎么保证球面和tube的连接处是光滑的，也就是indefinitely differentiable?
: 我记得几何书上讲partition of unity的时候会用smooth function来模拟平台函数，
: 这里也可以用类似的方法么？
: 2。 你是构造了一个三维欧氏空间里的二维曲面么？需不需要specify每个点上的
: riemannian metric? 是不是就用dot product作为inner product就可以了？
: 3。如果这个命题是正确的，那看起来是一个很general的结论，为什么网上和书上都没
: 有呢？
: 谢谢
|
|
|
w***w
发帖数: 84 | 21 任何有限集上的metric 可以等距嵌入l_\infty. Bourgain证明任何n个点可以嵌入欧式
空间
with O(log n) multiplicative distortion. 这些有不少算法上的应用。 |
o****i
发帖数: 23 | 22 对，(A) O(log n)－distortion的嵌入到欧氏空间 和 (B) isometrically嵌入到
infinity-norm空间我最近两三年研究过，也得到一些partial results发了领域内top
journal的文章。但是这两种嵌入对我的问题来说都有缺陷。(A)的问题是有distortion
, 而我最终要证明的是一个绝对的等式，所以用(A)只能得到一些bound. (B)的问题是
，嵌入之后很难做进一步的处理。l_infinity空间的文献和结论好像不多，感觉
structure过于复杂，不好办。
我本来感觉Riemannian manifold有可能综合(A)和(B)的优点，就是既可以等距嵌入（
待检验），又和熟悉的欧式空间有关系（每个点局部同构于欧式空间）。但是看前面的
回复，有可能不加限制的Riemannian metric还是象l_infitity一样过于复杂。
【在 w***w 的大作中提到】
: 任何有限集上的metric 可以等距嵌入l_\infty. Bourgain证明任何n个点可以嵌入欧式
: 空间
: with O(log n) multiplicative distortion. 这些有不少算法上的应用。
|
o****i
发帖数: 23 | 23 谢谢解释。warped product metric我没听说过，这两天找资料研究一下。
考虑三维欧式空间做ambient space一个可能的好处，就是如果需要的话，可以保证被
嵌入的完全图任意两条边不相交。(平面图可以嵌入二维平面保证任两条边不相交，任
意图都可以嵌入三维空间保证任两条边不相交。)
Nash embedding theorem说任意riemannian manifold可以等距嵌入到欧式空间，而一
个graph又不可以等距嵌入到欧式空间，所以一年前我以为这两个结论就决定了graph
metric不可能等距嵌入到riemannian manifold. 最近我意识到这个想法是错的，因为
Nash定理说的是嵌入之前和之后的geodesic距离相等，而不是嵌入之前的geodesic距离
和嵌入之后的欧式空间直线距离相等。
【在 f*c 的大作中提到】
:
: 连接的地方用（换）一个warped product metric 就可以了。
: 没有在3维空间里。小球和tube(即s^1times [0, L])都用标准 intrinsic 度量。
: 即使有Nash的定理，把曲面嵌入欧氏空间好像也没有什么益处。距离空间如果包含
: 至少四个点，一般就不可能等距嵌入欧氏空间。
|
o****i
发帖数: 23 | 24 谢谢comment. 我看到有文章研究往constant sectional curvature的Riemannian
manifold嵌入，那又太特殊了。
欧式空间没法保证graph metric的等距嵌入。
【在 w***w 的大作中提到】
: Riemannian metric 太general 了，对discrete set, 多的研究是embed到更加有结构
: 的空间，比如欧式空间。
|
o****i
发帖数: 23 | 25 更新一个，最近网上有人给了我一个反例，证明1楼的命题是错的。大概意思是：
考虑一个4节点星状图G: 4个点A, B, C, O, 3条边OA, OB, OC. 每条边长度都是1. 如
果图G可以等距嵌入riemannian manifold， 则A到B和A到C的两个geodesic都经过O。这
两个geodesic在AO段是共同的，到O之后分开分别去B和C. 这是不可能的，因为
riemannian manifold上的两个geodesic不可能先统一再分开(根据ODE的smooth
solution的唯一性可推出) |
l********e
发帖数: 3632 | 26 等距嵌入太强了。
事实上如果你能把图嵌入一个smooth Riemannian manifold，那么原先这个graph的曲
率必须有下界（图的曲率下界可以通过和对应space form的三角形比较得出）。
但是任何图只要有一个vertex有3个edge出去，那么对应的曲率下界就应该是负无穷。
因此不可能isometrically embedded into riemannian manifold。
不过你可以考虑bilipschitz embedding这样的问题，然后试图控制最佳lipschitz常数。
当然任何距离空间都可以等距嵌入到L_infinity里面。
【在 o****i 的大作中提到】
: 更新一个，最近网上有人给了我一个反例，证明1楼的命题是错的。大概意思是：
: 考虑一个4节点星状图G: 4个点A, B, C, O, 3条边OA, OB, OC. 每条边长度都是1. 如
: 果图G可以等距嵌入riemannian manifold， 则A到B和A到C的两个geodesic都经过O。这
: 两个geodesic在AO段是共同的，到O之后分开分别去B和C. 这是不可能的，因为
: riemannian manifold上的两个geodesic不可能先统一再分开(根据ODE的smooth
: solution的唯一性可推出)
|
