github-backend

分类： Metric geometry

若干有趣问题：线排列染色、单纯形结构与度量畸变
旧博客原文

原题：Some interesting problems

There are some interesting problem, I post them at there in case I forget them. Excuse me if they are trivial, I have not took enough time to consider them about I think they are valuable to be consider.
Problem 1:

This problem is stated by graph coloring. there are two prat of it, in fact the first part I heard from someone else and I try to generate it to high dimension.
1. there are finite lines $\{l_i\}_{i\in I}, l_i\subset \mathbb R^2$ , crossing each other and the is a set $J$ of crossing point. for technique reason, assume the position of lines are generic, i.e. no three of them intersect at one point. Then we could use 3 different colors to color $J$ make Neighbor points have different color. And to proof 3 is smallest.
2. generate it to high dimension, to prove $\mathbb R^n$ case, $n+1$ is the number.
This seems to be a graph problem, but the underlying structure is linear structure and some topological obstacle. I am not very sure. But it seems we can use an energy decrement argument with the obesevation:

The existence of a reasonable definition of “energy of correlation”.

the simplex arrive with the maximum of “correlation energy” in a very symmetric way, and this situation is easy to handle (coloring).

If make sense, this argument could also generate to high dimension.

Problem 2:

Let us consider some example of map between two metric space, a toy model is a line and two parallel lines, I called two parallel lines by $X_1\cup X_2$ , the single line by $X_3$ . The problem is try to find a tuple $(d,f)$ , where $d$ is a metric define on $X_1\cup X_2$ and $f: X_1\cup X_2\to X_3$ . such that the distortion of $f^* d$ and the standard metric on $X_3$ arrive at a infimum, this of course could not be the case, such like the situation of Yamabe problem on manifold with conners. So, let us ask a more general problem, could we describe the behavior of $f$ in some sense? what could we say with this kind of $f$ ?

补充说明

以下是新整理的中文说明；上方旧博客原文保持不变。

这里记录两个表面上很初等、但背后可能带有线性结构和拓扑障碍的问题。第一个问题从直线排列的交点染色开始，第二个问题从度量空间之间的最佳畸变开始。它们的共同点是：单纯的图论语言可能太粗，真正控制问题的是隐藏的几何结构。

直线排列染色看似是图论问题，但一般位置和线性排列结构给了它额外的几何约束。

1. 直线排列上的三染色

考虑平面中有限条直线，并假设一般位置：没有三条直线共点。交点构成一个图，若两个交点在同一条直线上相邻，就连一条边。问题是：能否总用三种颜色给交点染色，使相邻交点颜色不同？

三色的必要性很容易从三角形构型看出来；困难在于证明三色总是足够。这个图不是任意平面图，它来自直线的全局排列，因此有额外的线性约束。

2. 高维推广

若把直线换成高维中的超平面，交点换成更高余维的相交胞腔，问题自然变成：需要多少种颜色？猜想的数目应当与单纯形的顶点数有关。

一种可能思路是定义某种“相关能量”。当能量接近最大时，构型应当逼近对称单纯形，而这种对称情形反而容易染色。若能建立能量递降，就可能把一般情形归约到对称模型。

3. 度量畸变问题

第二个问题是：给定一条直线 $L$ 和两条平行线 $L_1\sqcup L_2$，是否可以在两边选择合适度量，使某个自然映射的畸变达到最小？

这有点像带角点流形上的 Yamabe 型问题：最优对象可能不存在，但极小化序列会呈现某种退化形态。于是更合理的问题不是“是否达到最小”，而是“接近最优时几何如何坍缩或分裂”。

4. 可能的共同结构

染色问题和畸变问题都可以看作约束优化：前者优化颜色冲突，后者优化距离拉伸。若存在合适的能量或紧性定理，就能把直觉转化成证明。真正值得追问的是：这些模型中的对称构型是不是唯一的极值障碍。
2017年12月21日
自由群 $F_2$ 上的线性度量：Cayley graph、范数空间与 pullback

旧博客原文

原题：Linear metric on F2, free group with two generator.

I may have made a stupid mistake, but if not, we could construct a metric by pullback a metric on a suitable linear normalized space $H$ which we carefully constructed. Let we define the generators of free group $F_2$ by $a,b$ .

Step 1.

Constructed the linear normalized space $H$ . the space $H$ was spanned by basis $\Lambda=\Lambda_a \coprod \Lambda_b$ , $\Lambda_a, \Lambda_b$ are defined by look at the Cayley graph of $F_2$ , there is a lot of vertical vector and horizontal vector in the Cayley graph, for every level set of vertical vector we put a basis in $\Lambda_a$ , because there is only countable many vertical vectors (for example, $a,a^2,a^{-5}$ are in the same vertical level, $bab^{-1}, ba^{10}b^{-1}$ are in the same vertical level, $bab^{-1},a$ are not in the same vertical level), we put a basis in $\Lambda_a$ for every vertical level and claim we accomplished the construct of $\Lambda_a$ , we do the same operation for $\Lambda_b$ but only change the vertical level with horizontal level. Now we accomplished the construction of $\Lambda$ , We spanned this with coefficient $\mathbb Z$ and we get a linear space $V$ . by Zorn’s lemma there exists a norm on the space, take one norm $\|\cdot\|$ we accomplished the construction of $H=(V,\|\cdot\|)$ .

Step 2:

Pullback the norm $\|\cdot\|$ on $H$ to the free group $F_2$ . In fact there is a natural bijection $T: F_2\to H$ , which is given by following: On the Cayley graph (imaged it is embedding in $\mathbb R^2$ ), identity $1$ in the group $F_2$ corresponding to the original, and more general every element in $F_2$ exactly identify with a point in the Cayley graph, thanks to there is no relation between $a,b$ . And then there is of course infinity many of path from original to the point, but there is only one shortest path , thanks to there is no loop in the Cayley graph. We identify the elements in $F_2$ with the point in Cayley graph with the shortest path. Now we could explain why the path lies $H$ . This path only across to finite vertical level and horizontal level and on every level it only pass finite step, this already given a representation $\sum_{e_i\in \Lambda}c_i\cdot e_i, c_i\in \mathbb Z$ , the key point is there is only finite $c_i\neq 0$ . So we have defined the bijection $T:F_2\to H$ , and we could use the bijection to pullback the norm on $H$ to a norm on $F_2$ .

Step 3:

Now we begin to proof the norm we get by pullback satisfied the condition we need. We need only to proof the condition of linear growth and triangle inequality. The conjugation invariance is automatically by linear growth by the comments of Tobias Fritz. The triangle inequality is automatically, due to the bijection $T$ stay the structure in fact, the multiplier of elements $x_1,x_2 \in_2$ could be view as put the two path together but this is not true… merely because of the addition operation is not commutative.

The space we should consider is the path space equipped with the composition operation. I image there exists a “big space” such that the natural metric on the “big space” restrict on the embedding image of $\mathbb F_2$ is a linear growth metric.

补充说明

以下是新整理的中文说明；上方旧博客原文保持不变。

自由群 $F_2=\langle a,b\rangle$ 的 Cayley graph 是一棵正则树。一个自然想法是：能否把这棵树嵌入某个线性赋范空间，然后把范数距离 pull back 回群上，得到一种由线性构造出来的 metric？

自由群的 Cayley graph 是树，把它映到赋范空间后可以 pull back 得到由线性构造出来的 metric。

1. Cayley graph 图像

$F_2$ 的每个元素都是一个约化字。Cayley graph 的顶点是群元素，边对应左乘或右乘生成元。因为自由群没有非平凡关系，这个图没有环，是一棵树。

2. 从边方向构造线性空间

可以尝试给 Cayley tree 中不同“水平”的水平边、垂直边分配基向量。设这些基张成一个向量空间 $V$，再在 $V$ 上选择一个范数 $\|\cdot\|$。

每个群元素对应从单位元到该点的唯一 geodesic path，于是可把路径上的边向量相加，得到映射

$$\Phi:F_2\to V.$$

3. Pullback metric

定义

$$d(g,h)=\|\Phi(g)-\Phi(h)\|.$$

如果 $\Phi$ 是单射，这确实给出 metric。若范数选得合适，它可能与 word metric 有可比较关系；若选得太退化，则会丢失树的几何。

4. 需要注意的问题

真正困难在于，这种构造是否自然、是否左不变、是否 quasi-isometric 于 word metric。普通 word metric 满足

$$d_S(g,h)=|g^{-1}h|_S,$$

具有明显的左不变性；pullback metric 未必自动保留这个性质。

5. 几何意义

这个问题可以看作自由群嵌入 Banach space 的 toy model。它连接 Cayley graph、tree metric、coarse embedding 和 geometric group theory 中的线性化思想。

2017年12月19日
Gromov-Hausdorff 距离笔记：不同维球面之间能多近？

旧博客原文

原题：How to compute the Gromov-Hausdorff distance between spheres $latex S_n$ and $latex S_m$?

There is the question, because when we consider the Gromov-Hausdorff distance, we must fix the metric, so we use the natural metric induced from the embedding $\mathbb{S}_n \to \mathbb{R}^{n+1}$ . Is it possible for us to compute the Gromov-Hausdorff distance $d_{G-H}(\mathbb{S}_n,\mathbb{S}_m)$ for two different spheres $\mathbb{S}_n$ and $\mathbb{S}_m$ , $m\neq n$ ?

For example if we want to calculate $d_{G-H}(\mathbb{S}_2,\mathbb{S}_3)=\inf_{M,f,g}d_{M}(\mathbb{S}_2,\mathbb{S}_3)$ , where $M$ ranges over all possible metric space and $f:\mathbb{S}_2\to M$ and $g:\mathbb{S}_3\to M$ range over all possible isometric (distance-preserving) embeddings.

At least we can embed $\mathbb{S}_2$ , $\mathbb{S}_3$ into $\mathbb{R}^3$ in a canonical way. This will lead to a upper bound: $d_{G-H}(\mathbb{S}_2,\mathbb{S}_3)\leq \sqrt{2}$ . And in general case we have $d_{G-H}(\mathbb{S}_m,\mathbb{S}_n)\leq d_{G-H}(point,S_m)+d_{G-H}(point,S_n)\leq 2,\forall 0\leq n\leq m$ . But it is difficult to get a lower bound control for me. Because we need to take the inf in all possible metric spaces $M$ . Especially I conjecture $d_{G-H}(\mathbb{S}_m,\mathbb{S}_n)\geq \lambda_{m,n}\frac{m-n}{m},\forall 0\leq n\leq m$ , where $\liminf_{m,n\to \infty}\lambda_{m,n}>0$ .

I only know the knowledge of Gromov-Hausdorff from Peterson’s Riemann Geometry. Unfortunately there is not enough information to compute the Gromov-Hausdorff distance, so this problem may be very stupid, I will appreciate any pointer.

And we know for the case $S_n,S_m$ , if $n,m$ is very near to each other,then the two space should be more near, and there is a canonical embed $S_0\subset S_1 \subset S_2 ....\subset S_n \subset ...$ . So it is natural to conjecture if $m,n$ is very near then the distance $d_{G-H}(S_n,S_m)$ is very small. I have a very rough strategy to prove the conjecture, that is inspired by the Nash embedding theorem. I just mean if we consider the problem in this frame $d_{G-H}(S_n,S_m)=\inf_{M,g,f}(d_M(f(S_n),g(S_m)))$ then the difficult is the deformation space of $M,g,f$ is too large. so the first step is to establish a regular lemma, to prove the function $d_M(f(S_n),g(S_m))$ is continues under the small perbutation of $M$ and reduced to the situation of space $M,g,f$ with very nice regularity. the second part is to embed $M$ to a big euclid space $R^N$ as subspace, and the embedding stay the length of geodesic.locally this is determine by a group of pde: $u_i(x)u_j(x)=g_{ij}(x)$ ,at least in the cut locus.but there should be some critical point,and I do not know how to deal with them.the third,i.e. the last step is to calculate $d_{G-H}(S_n,S_m)$ in the very some deformation space $M,f,g$ .

@Mark Sapir,Appreciate for help!I am reading the article you point out,it seems this article mainly focus on investigating the Gromov-Hausdorff limit space of a sequence of hyperbolic group equipped with modified G-H metric defined in 2.A with some special condition to ensure the limit space exists.and take a sequences corvarage to the limit space,the hyperbolic property and some other thing is stayed by the process of take limit.
@Mark Sapir,So it is natural for us to investigate the original space by some information from the limit space.there is a series of bi-product state in 3.B.but I do not see where the author exactly calculate some groom-hausdorff distance of two different space,may you point out it?appreciate again!
@MarianoSuárez-Álvarez,Corrected, thanks.

Y:
I fixed numerous typos. In particular, you should use spacing after each punctuation mark; capitals to begin sentences and names.

H:
Thank you very much for helping me to correct the mistakes! I will know how to write in a correct style.

Y:
23.1k
Your conjecture would imply that the GH distance is unbounded. But it’s clearly bounded, since the GH distance of any sphere to a point is equal to 2 (when the sphere is endowed with the restriction of Euclidean distance, as you seem to assume, or $\pi$ when endowed with geodesic distance) and hence the GH distance between any two spheres is $\le 4$ .

H:
73
You are right,In fact if we use the canonical embed, then we can get $d_{G-H}(S_n,S_m)\leq 2$ by another equivalent definition of GH distance.I confuse the geometry picture of the pairs $T_n,S_n$ with the pairs $S_n,S_m$ ,for $S_n,S_m$ case,I thick the seems correct conjecture will be $d_{G-H}(S_n,S_m)\sim \frac{m-n}{m},0\leq n\leq m,m,n\to \infty$ .

Y:
16:37
Clearly from standard embeddings we get $d_{GH}(S_n,S_m)\le\sqrt{2}$ for all $n,m\ge 0$ . Would it be reasonable to simply conjecture that it’s an equality whenever $n\neq m$ ?

H:
73
Yeah, you are right, $d_{G-H}(S_n,S_m)\leq \sqrt{2}$ for all $n,m\geq 0$ .I find the interesting problem when I want to find a toy model of a kind of problem,roughly speaking is to investigate a map $f:X\to Y$ from low-dimensions space $X$ to high-dimension space $Y$ stay some affine structure of the low-dimension space $X$ . This structure could have some control by the distance function on the low-dimension space, so if we can get some control on the variation of the Energy of distance function, this will share some line on the original problem I consider.
And we know for the case $S_n,S_m$ , if $n,m$ is very near to each other,then the two space should be more near, and there is a canonical embed $S_0\subset S_1 \subset S_2 ....\subset S_n \subset ...$ . So it is natural to conjecture if $m,n$ is very near then the distance $d_{G-H}(S_n,S_m)$ is very small. .
I have a very rough strategy to prove the conjecture, that is inspired by the Nash embedding theorem. I just mean if we consider the problem in this frame $d_{G-H}(S_n,S_m)=\inf_{M,g,f}(d_M(f(S_n),g(S_m)))$ then the difficult is the deformation space of $M,g,f$ is too large. so the first step is to establish a regular lemma, to prove the function $d_M(f(S_n),g(S_m))$ is continues under the small perbutation of $M$ and reduced to the situation of space $M,g,f$ with very nice regularity.
The second part is to embed $M$ to a big euclid space $R^N$ as subspace, and the embedding stay the length of geodesic.locally this is determine by a group of pde: $u_i(x)u_j(x)=g_{ij}(x)$ ,at least in the cut locus.but there should be some critical point,and I do not know how to deal with them.the third,i.e. the last step is to calculate $d_{G-H}(S_n,S_m)$ in the very some deformation space $M,f,g$ .
I need come back to explain why we expect the groom-hausdorff distance $d_{G-H}(S_d,S_m),0\leq n\leq m$ should be much small than $\sqrt 2$ when $frac{n}{m}$ is small.
Let consider a toy model of the problem,in a graph model,i.e. now we do not consider to take the Infimum in all space but in discrete space endow with metric. this can be view as a complete graph equipped metric, i.e. $M=\{(G,d_G)\}$ . So there is also some space very like $S_n$ ,$S_m$ in the Euclid space, Let remark them as $G_{S_n},G_{S_m}$ .
, oberseve that $(G,d_G)\in M$ then $(G,\hat d_{G})\in M$ , $\hat d_{G}$ is a scaling of $d_G$ so it is natural to consider a cut off of $M$ ,called $M_{\lambda}$ which is just a subset of $M$ and satisfied if $(G,d_G)\in M_{\lambda}$ ,then $\inf_{x\neq y}d_{G}(x,y)\geq d$ .
Now,in the space $M_{\lambda}$ let us consider a Distance distribution: $\mu_G((a,b))=\frac{\#\{x,y\in G|a<d_G(x,y)<b\}}{\#G\times G}$ . Then this distribution will give us some information of the distance of the two different set $G_1,G_2$ in $M_{\lambda}$ .
(removed)
Now,in the space $M_{\lambda}$ let us consider a Distance distribution: $\mu_G((a,b))=\frac{\#\{x,y\in G|a<d_G(x,y)<b\}}{\#G\times G}$ . Then this distribution will give us some information of the distance of the two different set $G_1,G_2$ in $M_{\lambda}$ .
and obviously we will see that if $n,m$ is close,then the distribution of fuzzy approximation $G_{S_n},G_{S_m}$ is near, and the reverse is also true. I think this can explain why the conjecture $d_{G-H}(S_n,S_m) =O(\frac{m-n}{m})$ may be right.

by the way,it is a very good exercise to proof $d_{G-H}(S_n,S_0)=1,\forall n\in N^*$ .

补充说明

以下是新整理的中文说明；上方旧博客原文保持不变。

问 $S^n$ 和 $S^m$ 的 Gromov-Hausdorff 距离，第一步必须先固定 metric。球面可以带内蕴测地距离，也可以带作为欧氏空间子集的 chordal distance；不同选择会给出不同数值。真正稳定的对象不是某个嵌入，而是所有可能 correspondences 的 distortion。

比较不同维球面时，标准嵌入只给出上界；真正的 GH 距离要在所有 correspondences 上取最优。

1. 定义提醒

紧 metric spaces $X,Y$ 的 Gromov-Hausdorff 距离可以用 correspondences 表示：

$$d_{GH}(X,Y)=\frac12\inf_R \operatorname{dis}(R),$$

其中 $R\subset X\times Y$ 是 correspondence，distortion 定义为

$$\operatorname{dis}(R)=\sup_{(x,y),(x’,y’)\in R}
\bigl|d_X(x,x’)-d_Y(y,y’)\bigr|.$$

这一定义强调：我们不是只比较两个空间在某个欧氏空间中的位置，而是允许把它们同时嵌入任意 metric space，再取最优比较。

2. 先用标准嵌入给上界

若 $n
$$d_{GH}(S^n,S^m)\le \sqrt2.$$

若用 geodesic metric，对应上界是 $\pi/2$。这只是上界，不自动说明最优。

3. 为什么不能猜它随维数增长

一个容易犯的错误是认为维数差越大，距离越大。但 GH 距离由直径控制。对任意紧空间 $X$，

$$d_{GH}(X,\{\ast\})=\frac12\operatorname{diam}(X).$$

因此两单位球面之间的 GH 距离总是被一个统一常数控制，不可能随着 $m-n$ 无界增长。维数差体现为拓扑和覆盖数的差异，但 GH 距离本身仍然是 metric 层面的量。

4. 下界为什么难

要证明 equator 嵌入给出的上界是最优，需要排除所有更聪明的 correspondences。这通常要找一个 metric invariant，例如 covering number、packing number、waist phenomenon 或同调信息，说明低维球面无法在小 distortion 下模拟高维球面。

例如，如果 $S^m$ 中有许多两两相距较远的点，而 $S^n$ 在同样尺度下容纳不了这么多点，就可以得到下界。这类 argument 本质上是把维数信息转化成 packing 数据。

5. 一个合理的 toy problem

这个问题真正有意思的地方在于，它是“低维空间如何嵌入高维空间并保留距离结构”的 toy model。若把球面换成带变形 metric 的流形，还会涉及 Nash embedding、cut locus、距离函数能量的变化以及正则性问题。

所以比较 $S^n$ 和 $S^m$ 不只是为了得到一个数值；它逼迫我们区分三件事：具体嵌入给出的 Hausdorff 上界、抽象 GH 距离的最优 correspondence、以及维数信息如何通过 metric invariant 被读出来。

2017年10月28日