Wreath product of metric spaces

This paper describes a new construction of wreath product of metric spaces. The group of isometries of the wreath product of metric spaces is calculated.

Gespeichert in:

Bibliographische Detailangaben
Datum:	2007
1. Verfasser:	Oliynyk, B.
Format:	Artikel
Sprache:	English
Veröffentlicht:	Інститут прикладної математики і механіки НАН України 2007
Schriftenreihe:	Algebra and Discrete Mathematics
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/152373
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Wreath product of metric spaces / B. Oliynyk // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 4. — С. 123–130. — Бібліогр.: 5 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-152373
record_format	dspace
spelling	irk-123456789-1523732019-06-11T01:25:38Z Wreath product of metric spaces Oliynyk, B. This paper describes a new construction of wreath product of metric spaces. The group of isometries of the wreath product of metric spaces is calculated. 2007 Article Wreath product of metric spaces / B. Oliynyk // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 4. — С. 123–130. — Бібліогр.: 5 назв. — англ. 1726-3255 2000 Mathematics Subject Classification:28D15. http://dspace.nbuv.gov.ua/handle/123456789/152373 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
description	This paper describes a new construction of wreath product of metric spaces. The group of isometries of the wreath product of metric spaces is calculated.
format	Article
author	Oliynyk, B.
spellingShingle	Oliynyk, B. Wreath product of metric spaces Algebra and Discrete Mathematics
author_facet	Oliynyk, B.
author_sort	Oliynyk, B.
title	Wreath product of metric spaces
title_short	Wreath product of metric spaces
title_full	Wreath product of metric spaces
title_fullStr	Wreath product of metric spaces
title_full_unstemmed	Wreath product of metric spaces
title_sort	wreath product of metric spaces
publisher	Інститут прикладної математики і механіки НАН України
publishDate	2007
url	http://dspace.nbuv.gov.ua/handle/123456789/152373
citation_txt	Wreath product of metric spaces / B. Oliynyk // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 4. — С. 123–130. — Бібліогр.: 5 назв. — англ.
series	Algebra and Discrete Mathematics
work_keys_str_mv	AT oliynykb wreathproductofmetricspaces
first_indexed	2025-07-13T02:56:33Z
last_indexed	2025-07-13T02:56:33Z
_version_	1837498785052229632
fulltext	Jo u rn al A lg eb ra D is cr et e M at h . Algebra and Discrete Mathematics RESEARCH ARTICLE Number 4. (2007). pp. 123 – 130 c© Journal “Algebra and Discrete Mathematics” Wreath product of metric spaces Bogdana Oliynyk Communicated by M. Ya. Komarnytskyj Dedicated to Professor V. V. Kirichenko on the occasion of his 65th birthday Abstract. This paper describes a new construction of wreath product of metric spaces. The group of isometries of the wreath product of metric spaces is calculated. 1. Introduction In 1959 F.Harrary [1] and G.Sabidussi [2] introduced a new construction of composition of graphs. Later this construction was called the wreath product of graphs. Definition 1. The wreath product of two simple graphs G1 and G2 is defined to be a graph whose vertices are the ordered pairs (v, w) for which v is a vertex of G1, and w is a vertex of G2. There is an arc between (v, w) and (v1, w1) if either of following holds: • v = v1 and there is an arc between w and w1 in G2 • there is an arc between v and v1 in G1 Denote the wreath product of graphs G1 and G2 by G1 ≀ G2. Recall, that a graph G is called locally finite if every its vertex has finite degree. The main result of Sabidussi about wreath product of graphs is The research was partially supported by Fundamental Research State Fund, project F25.1/096 2000 Mathematics Subject Classification: 28D15. Key words and phrases: wreath product, metric space, isometry group. Jo u rn al A lg eb ra D is cr et e M at h .124 Wreath product of metric spaces Theorem 1. (Sabidussi, 1959) If G1 is a locally finite graph and G2 is a finite graph, then the wreath product G1 ≀G2 of these graphs have the automorphism group isomorphic to (AutG1) ≀ (AutG2). In 2003 this result was strengthen by E.Dobson and J.Morris. Theorem 2. (Dobson–Morris, 2003) Let G1 be some graph and G2 be a graph not isomorphic to a proper induced subgraph of itself. Then the wreath product G1 ≀G2 of these graphs have the automorphism group isomorphic to (AutG1) ≀ (AutG2). Dobson and Morris proved that one can not omit the condition on the graph G2. G.Sabidussi in [2] considered slightly different wreath products for directed graphs end colored directed graphs. These constructions was also considered by E.Dobson and J.Morris. Some quite different construction of wreath product of graphs was considered by A.Erschler in [3]. The main purpose of this paper is to introduce a notion of the wreath product of metric spaces that is analogous to the Sabidussi’s and Har- rary’s one. We consider also isometry groups of the wreath products of metric spaces. 2. Construction Following [4] metric spaces (X, dX) and (Y, dY ) are called isomorphic if there exists a scale, that is a strictly increasing continuous function s : R+ → R+, s(0) = 0, such that dX = s(dY ). It is easy to observe that if metric spaces (X, dX) and (Y, dY ) are isomorphic then their isometry groups IsomX and IsomY are isomorphic. Let (X, dX) and (Y, dY ) be metric spaces. Assume that there exists a positive number r, such that for arbitrary points x1, x2 ∈ X, x1 6= x2, the inequality dx(x1, x2) > r holds. Additionally assume that the diameter diamY of the space (Y, dY ) is finite. Then fix a scale s(x) such that diam(s(Y )) < r. (1) Define a function ρs on the cartesian product X × Y by the rule: ρs((x1, y1), (x2, y2)) = { dX(x1, x2), if x1 6= x2 s(dY (y1, y2)), if x1 = x2 , (2) where x1, x2 ∈ X, y1, y2 ∈ Y . Jo u rn al A lg eb ra D is cr et e M at h .B. V. Oliynyk 125 The function ρs is a metric on the set X × Y . We call (X ×Y, ρs) the wreath product of spaces X and Y with scale s and denote by Xwr sY . Proposition 1. Let s1 and s2 be scales such that the inequality (1) holds. Then spaces (X × Y, ρs1 ) and (X × Y, ρs2 ) are isomorphic. Proof. Let r0 = diam(s2(Y )). Since for s2 the inequality (1) holds, it follows that r0 < r. Define a new function Ŝ(x) on the R+ by the rule: • if x < r0, then Ŝ(x) = s1(s −1 2 (x)); • if r0 6 x 6 r, then Ŝ(x) is a line segment joining the points (r0, s1(s −1 2 (r0)) and (r, r); • if x > r, then Ŝ(x) = x. It is clear that Ŝ(x) is a scale and Ŝ(ρs2 ) = ρs1 . Then spaces (X × Y, ρs1 ) and (X × Y, ρs2 ) are isomorphic. Another way to describe the wreath product of X and Y with scale s is as follows. Each point of X is replaced by an isometric copy of s(Y ), that is by an isomorphic copy of Y . And the distance between two points u and v is defined by the rule: • if u and v belong to the same copy of s(Y ) then the distance between these points is s(dY (u, v)); • if u and v belong to different copies of s(Y ), u ∈ s(Y )x1 and v ∈ s(Y )x2 , x1 6= x2 then the distance between them is dX(x1, x2). Since the wreath product of metric spaces is unique up to isomorphism we assume in the sequel that corresponding scale is fixed. Denote the wreath product of metric spaces X and Y by XwrY It is easy to see that the operation of wreath product of metric spaces is not commutative. Let (X, dX), (Y, dY ) and (Z, dZ) be metric spaces. Assume that for spaces X and Y a non-zero distances dX and dY are bounded low by a positive number. Additionally assume that the diameters diamY and diamZ of the space (Y, dY ) and (Z, dZ) are finite. Then this proposition can be proved by direct calculations. Proposition 2. Let (X, dX), (Y, dY ) and (Z, dZ) be metric spaces as above. Then spaces (XwrY )wrZ and Xwr(Y wrZ) are isomorphic. 3. Main properties Let (X, dX) and (Y, dY ) be metric spaces as considered before. The fol- lowing properties of the wreath product of metric spaces hold. Jo u rn al A lg eb ra D is cr et e M at h .126 Wreath product of metric spaces Theorem 3. 1) XwrY is ultrametric space iff X and Y are ultrametric spaces. 2) XwrY is a separable space iff X and Y are separable metric spaces. 3) XwrY is a complete space iff Y is a complete metric space. 4) XwrY is a compact space iff X is finite and Y is compact. Proof. 1) Let X and Y be ultrametric spaces. Let us show that for arbitrary points (x1, y1), (x2, y2), (x3, y3) from X × Y the inequalities ρs(xi, yi) 6 max{ρs(xj , yj), ρs(xk, yk)}, 1 6 i, j, k 6 3 (3) hold. The proof consists of 3 cases. Case 1: x1 6= x2, x2 6= x3, x1 6= x3, then by definition of ρs we obtain that the distance between (xi, yi) and (xj , yj), 1 6 i, j 6 3, is equal to the distance between xi and xj in (X, dX). Since this space is ultrametric the inequalities (3) hold. Case 2. x1 = x2 = x3, then by (2) we obtain that the distance between (xi, yi) and (xj , yj) is equal to the distance between yi and yj in (Y, s(dY )), 1 6 i, j 6 3. Since Y is ultrametric then s(Y ) is ultrametric too and the inequalities (3) hold. Case 3. Without loss of generality it can be assumed that x1 = x2 6= x3. Using (2) we obtain ρs((x1, y1), (x3, y3)) = dX(x1, x3) = dX(x2, x3) = ρs((x2, y2), (x3, y3)). By (1) and ρs((x1, y1), (x2, y2)) = s(dY (y1, y2)) so that ρs((x1, y1), (x2, y2)) < ρs((x1, y1), (x3, y3)) = ρs((x2, y2), (x3, y3)). Therefore the inequalities (3) hold. In opposite side. Let y be some point from Y . Assume that X is not ultrametric. Then there exist points x1, x2, x3 ∈ X such that the inequality dX(x1, x2) 6 max{dX(x1, x3), dX(x2, x3)}, holds. By (2), it follows that for point (x1, y), (x2, y), (x3, y) from X ×Y the inequalities (3) do not hold. Hence X × Y is not ultrametric space. If the space Y is not ultrametric the proof is similar. 2) Let X and Y be separable metric spaces. Let X̂ be a countable everywhere dense subset of X. Since there exists a positive number r such that for arbitrary points x1, x2 ∈ X, x1 6= x2, the inequality dx(x1, x2) > r holds, it follows that X is countable and X̂ = X. Let Ŷ be a countable everywhere dense subset of Y . Then X × Ŷ is a countable everywhere dense subset of X × Y and therefore XwrY is a separable space. Jo u rn al A lg eb ra D is cr et e M at h .B. V. Oliynyk 127 Note that projections of the countable dense subset of XwrY on each coordinate give countable dense subsets in both spaces X and Y . 3) Let {(xn, yn), n > 1} be a fundamental sequence in XwrY . Then {xn, n > 1} is fundamental in X, and {yn, n > 1} is fundamental in Y . Due to completeness of Y the latter sequences converge. Since there exists a positive number r such that for arbitrary points x1, x2 ∈ X, x1 6= x2, the inequality dx(x1, x2) > r holds, it follows that {(xn, yn), n > 1} is convergent sequence in XwrY iff xi = xj = x for all i, j > 1 and {yn, n > 1} is convergent sequence in s(Y ). As Y is a complete metric space, then s(Y ) is also complete. Hence, there exists limn→∞ yn = y in the space (Y, s(dY )). It follows that limn→∞(xn, yn) = (x, y) in (X × Y, ρs). Let the space Y is not complete. Then s(Y ) is not complete too. Hence there exists a fundamental sequence {yn, n > 1} that has no limit in (Y, dY ). It follows that for arbitrary point x ∈ X a fundamental sequence {(x, yn), n > 1} has no limit in (X × Y, ρs). Therefore XwrY is not complete. 4) Let X = {x1, x2, . . . , xn}, and the space Y is compact. Consider a covering {Qα, α ∈ I} of XwrY . Since X is finite, we see that XwrY =⋃n i=1 s(Y )i, where s(Y )i is an isometric copy of s(Y ) corresponding xi, 1 6 i 6 n. Then we can consider the covering {Qα, α ∈ I} as a finite union of {Qαi , αi ∈ Ii}, I = ∪n i=iIi, where {Qαi , αi ∈ Ii} is a covering of s(Y )i. Since Y is a compact space, it follows that s(Y )i is also compact for 1 6 i 6 n. Therefore, for any s(Y )i, 1 6 i 6 n there exists a finite subcovering of the covering {Qαi , αi ∈ Ii}. It follows that there exists a finite subcovering of covering {Qα, α ∈ I}. Let X be an infinite set. Fix a number r such that for arbitrary points x1, x2 ∈ X, x1 6= x2, the inequality dx(x1, x2) > r holds. Denote by Q(x,y) a ball B((x, y), r1) in XwrY centered in (x, y) ∈ X × Y of positive radius r1 < r. Then the set {Q(x,y) : (x, y) ∈ X × Y } is an infinite covering of XwrY that does not posses any finite subcovering. Then the space XwrY is not compact. Let X = {x1, x2, . . . , xn} and Y is not. Then there exists an infinite covering {Qα, α ∈ I} of Y that does not contain a finite subcovering. Hence for every isomorphic copy s(Y )i, 1 6 i 6 n there exists a cov- ering {Qαi , αi ∈ Ii}, that does not contain a finite subcovering. Then {Qαi , αi ∈ ∪n i=1Ii} is a covering of XwrY , that does not contain a finite subcovering. This completes the proof. This theorem immediately implies Corollary 1. If X and Y are Polish spaces then XwrY is a Polish space. The main result of this report is the following Jo u rn al A lg eb ra D is cr et e M at h .128 Wreath product of metric spaces Theorem 4. The isometry group of the wreath product of metric spaces X and Y is isomorphic as a permutation group to the wreath product of isometry groups of spaces X and Y Isom(XwrY ) ≃ IsomX ≀ IsomY. Proof. At first let us prove that ϕ = [g, h(x)] ∈ IsomX ≀ IsomY is an isometry of XwrY . By definition of the wreath product of permu- tation groups ( [5]) ϕ acts on X × Y . We shall see that ϕ preserves the metric ρs. Indeed, ρs(ϕ(x1, y1), ϕ(x2, y2)) = ρs((x g 1, y h(x1) 1 ), (xg 2, y h(x2) 2 )) = { dX(xg 1, x g 2), if x g 1 6= x g 2 s(dY (y h(x1) 1 , y h(x2) 2 )), if x g 1 = x g 2. Since g ∈ IsomX, it follows that x g 1 = x g 2 iff x1 = x2. Then h(x1) = h(x2), that is h(x1) and h(x2) define the same isometry t of Y . Note that t is an isometry of Y iff t is isometry of s(Y ). Hence, s(dY (y h(x1) 1 , y h(x2) 2 )) = s(dY (y h(x1) 1 , y h(x1) 2 ) = s(dY (y1, y2)). Since g ∈ IsomX, it means that dX(xg 1, x g 2) = dX(x1, x2). Therefore ρs(ϕ(x1, y1), ϕ(x2, y2)) = { dX(x1, x2), if x1 6= x2 s(dY (y1, y2)), if , x1 = x2. This means that ϕ is an isometry of XwrY . Now let us prove that for any isometry ϕ of XwrY there exists g ∈ IsomX and h(x) ∈ IsomY X , where [g, h(x)] acts on X × Y as ϕ does. Let the function ϕ maps some point (x1, y1) to (x2, y2). Using (2), we obtain that the function ϕ maps any point of the form (x1, ⋆) to point of the form (x2, ⋆). It follows that ϕ acts as an isometry on each isometric copy s(Y )x, x ∈ X. In each copy s(Y )x choose a point yx. Then ϕ is an isometry on {yx, x ∈ X}. This implies that there exists g ∈ IsomX and h(x) ∈ Isoms(Y )X , where [g, h(x)] acts on X ×Y as ϕ does. Since Isom(s(Y )) ≃ IsomY , it follows that we can consider [g, h(x)] as [g, h(x)] ∈ IsomX ≀ IsomY Jo u rn al A lg eb ra D is cr et e M at h .B. V. Oliynyk 129 4. Examples Observe, that constructions of wreath product of graphs and wreath prod- uct of metric spaces are different. We can consider arbitrary simple graph as a metric space. The distance between two point of such a graph is the length of the shortest path between them in this graph. For arbitrary simple graphs G1 and G2 the metric spaces G1 ≀ G2 and G1wrG2 are different (indeed not isomorphic). Example 1. Let G1 and G2 be two isomorphic simple graphs. The sets of vertices of these graphs consist of two points v1 and v2. The points v1 and v2 are connected by an edge. Then G1 ≀ G2 is a complete graph on 4 points. If we consider G1 and G2 as a metric spaces, then G1wrG2 is a metric spaces with the following matrix of distances   0 1 2 1 1 1 2 0 1 1 1 1 0 1 2 1 1 1 2 0   . Observe, that metric spaces G1 ≀ G2 and G1wrG2 are not isomorphic. Example 2. The stairs into the sky. Conceder two metric spaces: Z and [a, b] both with the euclidean met- ric. Let X = Z, Y = [a, b] and denote Stairs = Zwr [a, b]. This space consist of countable enumerated family of pairwise disjoint segments⋃ ∞ i=−∞ [ci, di]. The length of each segment is less than 1 \|ci − di\| < 1, i ∈ Z. The distance between points of this space is defined by the follow- ing rule: • if points belong to the same segment then the distance between them is simply the euclidean distance, • if points belong to the segments with number k and l, k 6= l then the distance between them is equal to \|k − l\|. This space is complete. The isometry group of Stairs is isomorphic to the permutational wreath product of the infinite dihedral group and the cyclic group of order 2: Isom(Stairs) ≃ D∞ ≀ C2. References [1] Harrary F. On the group of composition of two graphs // Duke Math J. 26(1959),p. 29–34 [2] Subidussi G. The composition of graphs // Duke Math J. 26(1959),p. 693–696 Jo u rn al A lg eb ra D is cr et e M at h .130 Wreath product of metric spaces [3] Eshler A. Generalized wreath products // IMRN, volume 2006, article ID57835, p.1–14 [4] Shoenberg I.J. Metric spaces and completely monotone functions// Ann. Math.- 1938.- v.39 N4.- p.811-841 [5] Kaloujnine L.A., Beleckij P.M., Feinberg V.T. Kranzprodukte. Leipzig: BSB B.G. Teubner Verlagsgesellschaft, 1987.- 168p. Contact information B. V. Oliynyk Department of Informatics, National University “Kyiv-Mohyla Academy”, Skovorody 2, 04070 Kyiv Ukraine E-Mail: bogd@ukma.kiev.ua Received by the editors: 28.02.2008 and in final form 09.04.2008.

Wreath product of metric spaces

Institution

Ähnliche Einträge