On representations of permutations groups as isometry groups of n-semimetric spaces
We prove that every finite permutation group can be represented as the isometry group of some n-semimetric space. We show that if a finite permutation group can be realized as the isometry group of some n-semimetric space then this permutation group can be represented as the isometry group of so...
Gespeichert in:
| Datum: | 2015 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2015
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/152787 |
| 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: | On representations of permutations groups as isometry groups of n-semimetric spaces / O. Gerdiy, B. Oliynyk // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 1. — С. 58-66. — Бібліогр.: 13 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-152787 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1527872019-06-13T01:25:38Z On representations of permutations groups as isometry groups of n-semimetric spaces Gerdiy, O. Oliynyk, B. We prove that every finite permutation group can be represented as the isometry group of some n-semimetric space. We show that if a finite permutation group can be realized as the isometry group of some n-semimetric space then this permutation group can be represented as the isometry group of some (n+1)-semimetric space. The notion of the semimetric rank of a permutation group is introduced. 2015 Article On representations of permutations groups as isometry groups of n-semimetric spaces / O. Gerdiy, B. Oliynyk // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 1. — С. 58-66. — Бібліогр.: 13 назв. — англ. 1726-3255 2010 MSC:54B25, 20B25, 54E40. http://dspace.nbuv.gov.ua/handle/123456789/152787 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We prove that every finite permutation group can be represented as the isometry group of some n-semimetric space. We show that if a finite permutation group can be realized as the isometry group of some n-semimetric space then this permutation group can be represented as the isometry group of some (n+1)-semimetric space. The notion of the semimetric rank of a permutation group is introduced. |
| format |
Article |
| author |
Gerdiy, O. Oliynyk, B. |
| spellingShingle |
Gerdiy, O. Oliynyk, B. On representations of permutations groups as isometry groups of n-semimetric spaces Algebra and Discrete Mathematics |
| author_facet |
Gerdiy, O. Oliynyk, B. |
| author_sort |
Gerdiy, O. |
| title |
On representations of permutations groups as isometry groups of n-semimetric spaces |
| title_short |
On representations of permutations groups as isometry groups of n-semimetric spaces |
| title_full |
On representations of permutations groups as isometry groups of n-semimetric spaces |
| title_fullStr |
On representations of permutations groups as isometry groups of n-semimetric spaces |
| title_full_unstemmed |
On representations of permutations groups as isometry groups of n-semimetric spaces |
| title_sort |
on representations of permutations groups as isometry groups of n-semimetric spaces |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2015 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/152787 |
| citation_txt |
On representations of permutations groups as isometry groups of n-semimetric spaces / O. Gerdiy, B. Oliynyk // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 1. — С. 58-66. — Бібліогр.: 13 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT gerdiyo onrepresentationsofpermutationsgroupsasisometrygroupsofnsemimetricspaces AT oliynykb onrepresentationsofpermutationsgroupsasisometrygroupsofnsemimetricspaces |
| first_indexed |
2025-07-14T04:16:54Z |
| last_indexed |
2025-07-14T04:16:54Z |
| _version_ |
1837594434086109184 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 19 (2015). Number 1, pp. 58–66
© Journal “Algebra and Discrete Mathematics”
On representations of permutations groups as
isometry groups of n-semimetric spaces
Oleg Gerdiy and Bogdana Oliynyk
Communicated by V. I. Sushchansky
Abstract. We prove that every finite permutation group
can be represented as the isometry group of some n-semimetric
space. We show that if a finite permutation group can be realized
as the isometry group of some n-semimetric space then this per-
mutation group can be represented as the isometry group of some
(n + 1)-semimetric space. The notion of the semimetric rank of a
permutation group is introduced.
Introduction
Permutation groups occur as groups of symmetries of various math-
ematical objects that preserve basic structure of those objects. The au-
tomorphism groups of graphs, boolean functions, ordered sets, isometry
groups of metric or semimetric spaces can be considered as permuta-
tion groups. The following well-known problem is called sometimes the
generalized Koenig’s problem. Let X be a discrete structure. Does exist
a permutation group (G, X) that the automorphism group Aut(X) is
isomorphic to (G, X) as a permutation group (see g.e. [1])? For example,
not every permutation group can be represented as the automorphism
group of a graphs (see [1], [2]) or as the isometry group of a metric space
[3]. There is no complete answers on the questions about characteri-
zation of permutation groups that can be realized as a automorphism
2010 MSC: 54B25, 20B25, 54E40.
Key words and phrases: n-semimetric, permutation group, isometry group.
O. Gerdiy, B. Oliynyk 59
groups of graphs or isometry groups of metric spaces. The case of regular
permutation groups is the most studied in this direction. Regular permu-
tation groups that arise as automorphism groups of simple graphs are
well-known [4]-[9]. In [10] for some classes of metric spaces it is obtained
similar results. But every permutation group (G, X) can be represented
as the automorphism group of a system of k-ary relations on X [11] for
some k or the automorphism group of a supergraph defined on X [12].
In this paper we continue research in this direction. We prove that
every finite permutation group can be represented as the isometry group
of some n-semimetric space. Over proof is self-contained. We show that if
a finite permutation group can be realized as the isometry group of some
n-semimetric space then this permutation group can be represented as
the isometry group of some (n + 1)-semimetric space. It follows from the
last statement that we can introduce the notion of the semimetric rank
of a permutation group. Additionaly we give some examles.
1. Preliminaries
We will need the following definitions.
Let X be a nonempty set, n be a positive integer, Sn be the symmetric
group of degree n. Denote by R
+ the set of all nonnegative integers.
An n-semimetric ( see [13]) defined on the set X is a function dn :
Xn+1 → R
+ satisfying the folowing conditions:
1) the function dn is fully symmetric, i.e. for arbitrary x1, x2, . . .,
xn+1 ∈ Xn+1 and for arbitrary permutations π ∈ Sn+1 the equality
dn(x1π , x2π , . . . , x(n+1)π ) = dn(x1, x2, . . . , xn+1).
holds.
2) dn satisfies the following simplex-type inequality, i.e. for arbitrary
x1, x2, . . . , xn+2 ∈ X the inequality
dn(x1, x2, . . . , xn+1) 6 dn(x2, . . . , xn+2)+
+
n+1∑
i=2
dn(x1, . . . , xi−1, xi+1, . . . , xn+2) (1)
holds.
The set X with an n-semimetric dn is called n-semimetric space and
denoted by (X, dn).
60 On representations of permutations groups
A function f : X → X is said to be an isometry, if for arbitrary
a1, a2, . . . , an+1 ∈ X the equality
dn
X(f(a1), f(a2), . . . , f(an+1)) = dX(a1, a2, . . . , an+1)
holds.
As for metric spaces, all isometries of the space (X, dn) form a group
with respect to superposition. We call this group the isometry group of the
n-semimetric space (X, dn). We can consider this group as a permutation
group on the set X and denote it by (Isom X, X).
2. Representations of permutations groups
The main result of this paper is as follows.
Theorem 1. Let (G, X) be a finite permutation group. Then there exist
a positive integer n and an n-semimetric dn on X such that the isometry
group (Isom X, X) of the n-semimetric space (X, dn) is isomorphic as a
permutation group to (G, X).
Proof. Let X = {x1, x2, . . . , xm}, where m is some positive integer. De-
note by n the number
2 + 3 + . . . + m =
m(m + 1)
2
− 1.
Fix an element x̄ from the set Xn+1:
x̄ = (x1, x2, x2
︸ ︷︷ ︸
2
, x3, x3, x3
︸ ︷︷ ︸
3
, . . . , xm, . . . , xm
︸ ︷︷ ︸
m
). (2)
Define a function dn : Xn+1 → R
+ by the rule:
dn(ȳ) =
{
1, if yi = (xiσ )g for some g ∈ G and σ ∈ Sn+1, 1 6 i 6 n,
2, in other cases,
(3)
where ȳ is arbitrary element of Xn+1.
It is not difficult to verify that the function dn is fully symmetric
and satisfies simplex-type inequality (1). Then dn is an n-semimetric. We
shall show that the groups (Isom X, X) and (G, X) are isomorphic as
permutation groups.
O. Gerdiy, B. Oliynyk 61
Let g be an element G. The element g acts as one-to-one corre-
spondence on X. Therefore, it is sufficient to show that g preserves the
n-semimetric dn. Indeed, for any ȳ ∈ Xn+1
dn(yg
1 , y
g
2 , . . . , y
g
n+1) =
=
1, if there exist g1 ∈ G, σ ∈ Sn+1, such that xiσ = (yg
i )g1 ,
1 6 i 6 n + 1,
2, in other cases.
Assume that dn(yg
1 , y
g
2 , . . . , y
g
n+1) = 1. Since g ∈ G, the elements g1 and σ
exist if and only if there exist g2 ∈ G, such that g2 = gg1 and the equality
xiσ = y
g2
i
holds for all i, 1 6 i 6 n+1. This means that dn(y1, . . . , yn+1) = 1. Hence
dn(yg
1 , y
g
2 , . . . , y
g
n+1) = dn(y1, . . . , yn+1),
and g is an isometry of (X, dn).
Let now f be some isometry of (X, dn). Assume that ȳ is an element
of Xn+1 such that dn(ȳ) = 1. By the definition the semimetric dn (see
(3)) we obtain that there exist g ∈ G, π ∈ Sn+1 such that
xi = y
g
iπ (4)
for all i, 1 6 i 6 n + 1. Hence, from (2) we obtaine
y2π = y3π , y4π = y5π = y6π , . . . (5)
and yiπ 6= y1π for all i, 2 6 i 6 n + 1. Moreover,
dn(y1π , y2π , . . . , yn+1π ) = 1.
Since the function f is an isometry of (X, dn), the equality
dn(f(y1π ), f(y2π ), . . . , f(yn+1π )) = 1
holds. By (3) there exist g1 ∈ G, σ ∈ Sn+1 such that
xiσ = f(yiπ )g1 (6)
for all i, 1 6 i 6 n + 1. But f(yiπ ) 6= f(y1π ) for all i, 2 6 i 6 n + 1.
Therefore, using definition (2) of the element x̄ and (6), we obtain that
f(y1π ) = x1.
62 On representations of permutations groups
Analogously, from (5) and (6) we obtain
f(yiπ ) = xi for all i, 2 6 i 6 n + 1.
Therefore, from (4) it follows that the following equalities
f(yiπ ) = y
g
iπ , 1 6 i 6 n + 1,
hold. This means that the isometry f acts on X as the element g from
the permutation group (G, X).
Definition 1. A permutation group (G, X) is called n-semimetric real-
izable if there exist a positive integer n and an n-semimetric space (Y, dn
Y )
such that the group (G, X) and the isometry group (Isom Y, Y ) are iso-
morphic as permutation groups. In this case we say that the group (G, X)
is realized on the n-semimetric space (Y, dn
Y ).
Note, that if a permutation group (G, X) is n-semimetric realizable,
then there exists an n-semimetric dn on X such that the permutation
group (G, X) is realized on the space (X, dn).
The proof of the next statement is not difficult to verify.
Lemma 1. Let (G, X) be a permutation group, n be a positive integer and
(X, dn) be an n-semimetric space. Assume that (G, X) is realized on the
n-semimetric space (X, dn). Then (G, X) is realized on an n-semimetric
space (X, d̂n), where d̂n takes only positive integer values.
Theorem 2. Let (G, X) be a permutaion group, n be a positive integer.
If the permutaion group (G, X) is n-semimetric realizable, then it is
(n + 1)-semimetric realizable.
Proof. Let dn be some n-semimetric on X, such that the permutation
group (G, X) is realized on the space (X, dn). From Lemma 1 is follows,
that we can consider the case when dn takes only positive integer values.
The maximum
M = max
xi∈X
dn(x1, x2, . . . , xn+1)
exists for X is finite. Denote by b the positive integer
b = n + 1 + M.
Define a function dn+1 : Xn+2 → R
+ by the rule:
dn+1(x1, x2, . . . , xn+2) = bdn(x2,...,xn+2)+
+ bdn(x1,x3...,xn+2) . . . + bdn(x1,x2...,xn+1), xi ∈ X, 1 6 i 6 n + 2. (7)
O. Gerdiy, B. Oliynyk 63
Obviously, dn+1 is fully symmetric. We need to veryfy simplex-type
inequality (1):
bdn(x2,...,xn+2) + bdn(x1,x3...,xn+2) . . . + bdn(x1,x2...,xn+1)
6
6
n+3∑
i=1
dn+1(x1, . . . , xi−1, xi+1, . . . , xn+3). (8)
But the sum
dn+1(x2, . . . , xn+3) =
n+3∑
i=2
bdn(x2,...,xi−1,xi+1,...,xn+3)
contains the term bdn(x2,...,xn+2), the sum
dn+1(x1, x3, . . . , xn+3) =
n+3∑
i=1,i6=2
bdn(x1,...,xi−1,xi+1,...,xn+3)
contains the term bdn(x1,x3,...,xn+2) and so on. Hence, inequality (8) holds.
Therefore the function dn+1 is an (n + 1)-semimetric.
From the definition of the function dn+1 it follows, that all isometries
of the n-semimetric space (X, dn) are isometries of the (n + 1)-semimetric
space (X, dn+1).
Let f : X → X be an isometry of (X, dn+1). Assume on the contrary
that f is not an isometry of (X, dn). Then there exist a1, . . . , an+1 ∈ X
such that
dn(a1, . . . , an, an+1) 6= dn(f(a1), f(a2), . . . , f(an), f(an+1)). (9)
As f is an isometry of (X, dn+1), the equality
dn+1(a1, . . . , an, an+1, an+1) =
= dn(f(a1), f(a2), . . . , f(an), f(an+1), f(an+1)) (10)
holds. From (10) and defininition (7) (n + 1)-semimetric dn+1 we have
bdn(a2,...,an+1,an+1) + bdn(a1,a3...,an+1,an+1) . . . + bdn(a1,a2...,an+1) =
= bdn(f(a2),...,f(an+1),f(an+1)) + bdn(f(a1),f(a3)...,f(an+1),f(an+1)) + . . . +
+ bdn(f(a1),f(a2)...,f(an+1)) (11)
64 On representations of permutations groups
From (9) we obtaine, that the last term on the left is not equal to the
last term on the right in (11). Then either
bdn(a2,...,an+1,an+1) 6= bdn(f(a2),...,f(an+1),f(an+1)), (12)
or there exists a positive integer i, 2 6 i 6 n + 1, such that the inequality
bdn(a1,...,ai−1,ai+1,...,an+1,an+1) 6= bdn(f(a1),...,f(ai−1),f(ai+1),...,f(an+1),f(an+1))
holds. As dn is fully symmetric, without loss of generality we can assume
that inequality (12) holds. As f is an isometry of (X, dn+1), we have
dn+1(a2, . . . , an, an+1, an+1, an+1) =
= dn(f(a2), . . . , f(an), f(an+1), f(an+1), f(an+1)). (13)
Using (13) and (12), by the similar arguments as above we get
bdn(a3,...,an+1,an+1,an+1) 6= bdn(f(a3),...,f(an+1),f(an+1),f(an+1)).
Then we consider dn+1(a3, . . . , an+1, an+1, an+1, an+1), and so on. Finally
we obtain
bdn(an+1,...,an+1,an+1,an+1) 6= bdn(f(an+1),...,f(an+1),f(an+1),f(an+1)).
From this inequality and the definition of the (n + 1)-semimetric dn+1 (7)
we get
dn+1(an+1, . . . , an+1, an+1, an+1) 6=
6= dn(f(an+1), . . . , f(an+1), f(an+1), f(an+1)).
But f is an isometry of the space (X, dn+1). Hence, our assumption is
incorrect and f is isometry of (X, dn).
3. n-semimetric ranks of groups
Theorem 1 and Theorem 2 imply that the following definition is
correct.
Definition 2. The semimetric rank of a permutation group (G, X) is
the minimal number k ∈ N such that there exists a k-semimetric space
(X, dk) such that (G, X) is realized on the space (X, dk).
We denote the semimetric rank of (G, X) as sr(G, X).
O. Gerdiy, B. Oliynyk 65
Proposition 1. Let (G, X) be a finite permutation group, |X| = n. Then
the following inequality
sr(G, X) 6
n(n + 1)
2
− 1
holds.
The proof of this proposition follows directly from the proof of Theorem 1.
A permutation group (G, X) is called metric realizable if there exists
a metric space (Y, dY ) such that the group (G, X) and the isometry group
(Isom Y, Y ) are isomorphic as permutation groups. In this case we say
that the group (G, X) is realized on the metric space (Y, dY ).
As any metric space is an 1-semimetric space, any metric realized per-
mutation group is an 1-semimetric realizable. For example, the symmetric
group of degree n, direct sums, direct products and wreath products of
symmetric groups of some degree are 1-semimetric realizable and hence
sr(Sn) = sr(Sn ≀ Sm) = sr(Sn × Sm) = sr(Sn ⊕ Sm) = 1,
where n, m ∈ N (see [3]).
Open questions. Is semimetric rank unbounded, i.e. is it true that for
arbitrary positive integer n there exists a permutation group (G, X) such
that sr(G, X) > n? If the answer is affirmative then find natural series
(Gn, Xn), n > 1, of permutation groups such that their semimetric ranks
have a common bound, i.e. there exists C > 0 such that sr(Gn, Xn) <
C, n > 1.
References
[1] Babai L. Automorphism groups, isomorphism, reconstruction, In: Graham R.
L., Grotschel M., Lovasz L. (eds.) Handbook of Combinatorics, North-Holland,
Amsterdam, V.2, 1995, pp 1447-1540.
[2] Beineke, Lowell W. (ed.), Wilson, Robin J. (ed.), Cameron, Peter J. (ed.), Topics
in algebraic graph theory, Encyclopedia of Mathematics and Its Applications 102,
Cambridge: Cambridge University Press, 2004.
[3] B. V. Oliynyk, Metric realizable permutation groups, Bulletin of Taras Shevchenko
National University of Kyiv, Series: Physics & Mathematics, V. 2, 2013, pp. 15-18.
[4] L. Babai, On a conjecture of M. E. Watkins on graphical regular representations
of finite groups, Compos. Math. , V.37., 1978, pp. 291-296.
[5] C.D. Godsil, GRR’s for non-solvable groups, Algebraic methods in graph theory,
Conf. Szeged 1978, Colloq. Math. Soc. Janos Bolyai 25, V. I, 1981, pp. 221-239.
[6] W. Imrich, M. E. Watkins, On graphical representations of cyclic extensions of
groups, Pac. J. Math., V.55, 1974, pp. 461-477.
66 On representations of permutations groups
[7] L.A. Nowitz, On the non-existence of graphs with transitive generalized dicyclic
groups, J. Comb. Theory, V.4, 1967, pp. 49–51.
[8] L. A. Nowitz, M. E. Watkins, Graphical regular representations of non-abelian
groups. I., Can. J. Math., V.24, 1972, pp. 993–1008.
[9] L. A. Nowitz, M. E. Watkins, Graphical regular representations of non-abelian
groups. II., Can. J. Math., V.24, 1972, pp. 1009–1018.
[10] B. V. Oliynyk, Metric realization of regular permutation groups, Mat. Visn. Nauk.
Tov. Im. Shevchenka, V. 8, 2011, pp. 151-166.
[11] J. D. Dixon, B. Mortimer, Permutation groups, Graduated Texts in Mathematis
163, Springer-Verlag New York In., 1996.
[12] A. Kisielewicz, Supergraphs And Graphical Complexity Of Permutation Groups,
Ars Combinatoria, V. 101, 2011 , pp. 193-207.
[13] Deza M. n-semimetrics. Eur. J. Comb., V. 21, N. 6, 2000, 797–806.
Contact information
O. Gerdiy,
B. Oliynyk
Department of Computer Sciences, National University
of “Kyiv-Mohyla Academy”, Skovorody St. 2, Kyiv,
04655, Ukraine
E-Mail(s): lotuseater24@gmail.com,
bogdana.oliynyk@gmail.com
Received by the editors: 18.03.2015
and in final form 18.03.2015.
|