Kaleidoscopical configurations
Let G be a group and X be a G-space with the action G × X → X, (g, x) → gx. A subset A of X is called a kaleidoscopical configuration if there is a coloring χ : X → k (i.e. a mapping of X onto a cardinal k) such that the restriction χ|gA is a bijection for each g ∊ G. We survey some recent results o...
Gespeichert in:
| Datum: | 2014 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2014
|
| Schriftenreihe: | Український математичний вісник |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/124449 |
| 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: | Kaleidoscopical configurations / ИОФІ. Protasov, K. Protasova амилия // Український математичний вісник. — 2014. — Т. 11, № 1. — С. 79-86. — Бібліогр.: 18 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-124449 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1244492017-09-27T03:03:19Z Kaleidoscopical configurations Protasov, І. Protasova, K. Let G be a group and X be a G-space with the action G × X → X, (g, x) → gx. A subset A of X is called a kaleidoscopical configuration if there is a coloring χ : X → k (i.e. a mapping of X onto a cardinal k) such that the restriction χ|gA is a bijection for each g ∊ G. We survey some recent results on kaleidoscopical configurations in metric spaces considered as G-spaces with respect to the groups of its isometries and in groups considered as left regular G-spaces. 2014 Article Kaleidoscopical configurations / ИОФІ. Protasov, K. Protasova амилия // Український математичний вісник. — 2014. — Т. 11, № 1. — С. 79-86. — Бібліогр.: 18 назв. — англ. 1810-3200 2010 MSC. 05A18, 05B30. http://dspace.nbuv.gov.ua/handle/123456789/124449 en Український математичний вісник Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
Let G be a group and X be a G-space with the action G × X → X, (g, x) → gx. A subset A of X is called a kaleidoscopical configuration if there is a coloring χ : X → k (i.e. a mapping of X onto a cardinal k) such that the restriction χ|gA is a bijection for each g ∊ G. We survey some recent results on kaleidoscopical configurations in metric spaces considered as G-spaces with respect to the groups of its isometries and in groups considered as left regular G-spaces. |
| format |
Article |
| author |
Protasov, І. Protasova, K. |
| spellingShingle |
Protasov, І. Protasova, K. Kaleidoscopical configurations Український математичний вісник |
| author_facet |
Protasov, І. Protasova, K. |
| author_sort |
Protasov, І. |
| title |
Kaleidoscopical configurations |
| title_short |
Kaleidoscopical configurations |
| title_full |
Kaleidoscopical configurations |
| title_fullStr |
Kaleidoscopical configurations |
| title_full_unstemmed |
Kaleidoscopical configurations |
| title_sort |
kaleidoscopical configurations |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2014 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/124449 |
| citation_txt |
Kaleidoscopical configurations / ИОФІ. Protasov, K. Protasova амилия // Український математичний вісник. — 2014. — Т. 11, № 1. — С. 79-86. — Бібліогр.: 18 назв. — англ. |
| series |
Український математичний вісник |
| work_keys_str_mv |
AT protasoví kaleidoscopicalconfigurations AT protasovak kaleidoscopicalconfigurations |
| first_indexed |
2025-07-09T01:26:55Z |
| last_indexed |
2025-07-09T01:26:55Z |
| _version_ |
1837130757367136256 |
| fulltext |
Український математичний вiсник
Том 11 (2014), № 1, 79 – 86
Kaleidoscopical configurations
Igor Protasov, Ksenia Protasova
Abstract. Let G be a group and X be a G-space with the action
G × X → X, (g, x) 7→ gx. A subset A of X is called a kaleidoscopical
configuration if there is a coloring χ : X → κ (i.e. a mapping of X
onto a cardinal κ) such that the restriction χ|gA is a bijection for each
g ∈ G. We survey some recent results on kaleidoscopical configurations
in metric spaces considered as G-spaces with respect to the groups of its
isometries and in groups considered as left regular G-spaces.
2010 MSC. 05A18, 05B30.
Key words and phrases. Kaleidoscopical configuration, transversal,
factorization, splitting.
1. Introduction
Let X be a set F be a family of subsets of X. The pair (X,F) is called
a hypergraph. Following [9], we say that a coloring χ : X → κ (i.e. a
mapping of X onto a cardinal κ) is kaleidoscopical if χ|F is bijective for
all F ∈ F. A hypergraph (X,F) is called kaleidoscopical if there exists
a kaleidoscopical coloring χ : X → κ. The adjective “kaleidoscopical”
appeared in definition [13] of an s-regular graph Γ(V,E) (each vertex
v ∈ V has degree s) admitting a vertex (s + 1)-colloring such that each
unit ball B(v, 1) = {u ∈ V : d(u, v) = 1} has the vertices of all colors
(d is the path metric on V ). These graphs define the kaleidoscopical
hypergraphs (V, {B(v, 1) : v ∈ V }) and can be considered as the graph
counterparts of the Hamming codes [10].
In this paper we survey some recent results and open problems on
kaleidoscopical configurations in G-spaces.
Let G be a group. A G-space is a set X endowed with an action
G×X → X, (g, x) 7→ gx. All G-spaces are suppose to be transitive: for
any x, y ∈ X, there exists g ∈ G such that gx = y. For a subset A ⊆ X,
we denote G[A] = {gA : g ∈ G} where gA = {ga : a ∈ A}.
Received 11.07.2013
ISSN 1810 – 3200. c© Iнститут математики НАН України
80 Kaleidoscopical Configurations
A subset A ⊆ X is called a kaleidoscopical configuration if the hy-
pergraph (X,G[A]) is kaleidoscopical, in words, if there exists a coloring
χ : X → |A| such that χ|gA is bijective for every g ∈ G.
We note that finite kaleidoscopical configurations in a sense are an-
tipodal to monochromatizable configurations defined and studied in [9,
Chapter 8]: a subset A of a G-space X is called monochromatizable if, for
any finite coloring of X, there is g ∈ G such that gA is monochrome.
In Section 2 we discus a relationship between the kaleidoscopical con-
figurations in a G-space X and transversals of the family {gA : g ∈ G},
A ⊆ G. We present also an effective method (namely, the splitting), of
construction of kaleidoscopical configurations in a G-space X from the
finite chains of G-invariant equivalence relations on X.
The main results of Section 3 are about kaleidoscopical configurations
in Rn considered as a G-space with respect to the group G = Iso(Rn) of
all Euclidean isometries. For n = 1, it is easy to find a kaleidoscopi-
cal configuration in R of any size ≤ the cardinality of the continuum.
The problem is much more difficult for n ≥ 2. Surprisingly, the subsets
Z × {0}, Q × {0}, Q × Q and Z × Z are kaleidoscopical in R2. The most
intriguing open problem: for n ≥ 2, does there exist a finite kaleidoscop-
ical configuration K, |K| ≥ 2 in Rn. We show that if such a K exists in
R2 then |K| ≥ 5.
Each group G can be considered as a (left) regular G-space X = G,
where (g, x) 7−→ gx is the group product. In Section 4 we show that
kaleidoscopical configurations in G are tightly connected with factoriza-
tions of G = AB by subsets A,B. The factorizations were introduced
by Hajoś [5] to solve the famous Minkowsky’s problem on tiling of Rn
by the copies of a cube. For modern state of factorizations see [17, 18].
Also we establish a connection between kaleidoscopical configurations and
T -sequences from [12].
2. Transversality and factorization
Let (X,F) be a hypergraph. A subset T ⊆ X is called an F-transversal
if |F ⋂T | = 1 for each F ∈ F. All results of this section are from [1].
Theorem 2.1. A hypergraph (X,F) is kaleidoscopical if and only if X
can be partitioned into F-transversals.
For a cardinal κ, cfκ denotes the cofinality of κ.
Theorem 2.2. Let κ be an infinite cardinal, (X,F) be a hypergraph
such that |F| = κ and |F | = κ for each F ∈ F. If |F ∩ F ′| < cfκ for all
distinct F, F ′ ∈ F then there is a disjoint family T of F-transversals such
that |T| = κ and |T | = κ for each T ∈ T.
I. Protasov, K. Protasova 81
For a hypergraph (X,F), x ∈ X and A ⊆ X, we put
St(x,F) =
⋃
{F ∈ F : x ∈ F},
St(A,F) =
⋃
{St(a, F ) : a ∈ A}.
Theorem 2.3. A hypergraph (X,F) is kaleidoscopical provided that, for
some infinite cardinal κ, the following two conditions are satisfied:
(i) |F| ≤ κ and |F | = κ for each F ∈ F;
(ii) for any subfamily A ⊂ F of cardinality |A| < κ and any subset B ⊂
X \ (
⋃
A) of cardinality |B| < κ the intersection St(B,F) ∩ (
⋃
A)
has cardinality less than κ.
Now we present some construction of kaleidoscopical configurations in
arbitrary G-space, called the splitting. The kaleidoscopical configurations
obtained in this way will be called splittable.
Given an equivalence relation E ⊆ X × X on a set X, let X/E =
{[x]E : x ∈ X} be the quotient space consisting of the equivalence classes
[x]E = {y ∈ X : (x, y) ∈ E}, x ∈ X. Denote by qE : X → X/E,
qE(x) = [x]E , the quotient mapping. For a subset K of X, let K/E =
{[x]E : x ∈ K} ⊆ X/E and [K]E =
⋃
x∈K [x]E ⊆ X.
Let E be an equivalence relation on a set X. A subset K ⊆ X is
defined to be
• E-parallel if K ∩ [x]E = [x]E for all x ∈ K;
• E-orthogonal if K ∩ [x]E = {x} for all x ∈ K.
Given two equivalence relations E, F on X such that F ⊆ E, we gener-
alize these two notions defining K ⊆ X to be
• E/F -parallel if [K]F ∩ [x]E = [x]E for all x ∈ K;
• E/F -orthogonal if [K]F ∩ [x]E = [x]F for all x ∈ K.
We observe that K ⊆ X is E-parallel (E-orthogonal) if it is E/∆X -
parallel (E/∆X -orthogonal), where ∆X = {(x, x) : x ∈ X}.
An equivalence relation E on a G-space X is called G-invariant if, for
each (x, y) ∈ E and every g ∈ G we have (gx, gy) ∈ E. For a G-invariant
equivalence relation E on X, the quotient space X/E is a G-space under
the induced action
G×X/E → X/E, (g, [x]E) 7→ [gx]E
of the group G.
82 Kaleidoscopical Configurations
Theorem 2.4. Let ∆X = E0 ⊂ E1 ⊂ · · · ⊂ Em = {X ×X} be a chain
of G-invariant equivalence relations on a G-space X. A subset K of X
is kaleidoscopical provided that, for every i ∈ {0, . . . ,m− 1}, K is either
Ei+1/Ei-parallel or Ei+1/Ei-orthogonal.
A subset K of a G-space X is called splittable if there is a chain
∆X = E0 ⊂ E1 ⊂ · · · ⊂ Em = {X × X} of G-invariant equivalence
relations on X such that, for each i ∈ {0, . . . ,m−1}, K is either Ei+1/Ei-
parallel or Ei+1/Ei-orthogonal. By Theorem 2.4, each splittable subset
of X is a kaleidoscopical configuration.
Some partial answers to the following general question are in the next
sections.
Question 2.1. Given a G-space X, how one can detect whether each
kaleidoscopical configuration in X is splittable?
For motivation of the following definition see [1, Section 4].
A G-space has the semi-Hajós property if, for every kaleidoscopical
subset K ⊂ X, there is an equivalence relation E on X, E 6= ∆X such
that K is E-parallel or E-orthogonal and K/E is kaleidoscopical in the
G-space K/E.
Theorem 2.5. If each kaleidoscopical subset of a G-space X is splittable,
then X has the semi-Hajós property.
On some partial conversions of Theorem 2.5 see [1, Section 4].
A G-space X is called primitive if each G-invariant equivalence rela-
tion on X is either ∆X or {X×X}. Clearly, each splittable configuration
K in a primitive G-space X is trivial, i.e. either K = X or K is a single-
ton. It is natural to ask whether every kaleidoscopical configuration in a
primitive G-space is trivial? The answer to this question is affirmative if
X is 2-transitive: for any (x, y), (x′, y′) ∈ X2 \ ∆X , there is g ∈ G such
that (x′, y′) = (gx, gy). But for n ≥ 2, the primitive space Rn endowed
with the action of its group of all Euclidean isometries has a plenty of
infinite kaleidoscopical configurations, see Section 3.
Question 2.2. Is every finite kaleidoscopical configuration in a (finite)
primitive G-space trivial?
3. Kaleidoscopical configurations in metric spaces
Here we consider each metric space (X, d) as a G-space endowed with
the natural action of its isometry group G = Iso(X). If this action is
transitive, X is called isometrically homogeneous.
I. Protasov, K. Protasova 83
Let us recall that a metric space (X, d) is ultrametric if the metric d
satisfies the strong triangle inequality
d(x, z) ≤ max{d(x, y), d(y, z)}
for all x, y, z. In this case, for every ε ≥ 0, the relation
Eε = {(x, y) ∈ X2 : d(x, y) ≤ ε}
is an invariant equivalence relation on X.
Theorem 3.1 ([1]). Let (X, d) be an isometrically homogeneous ultra-
metric space with the finite distance scale d(X × X) = {ε0, ε1, . . . , εn}
where 0 = ε0 < ε1 < · · · < εn. Then every kaleidoscopical configuration
in X is (Eε0 , Eε1 , . . . , Eεn)-splittable.
Let (X, d) be a metric space. By S(x, r) = {y ∈ X : d(x, y) = r}, we
denote the sphere of radius r centered at x.
A subset K of X is called rigid if, for any distinct points x, y, z ∈ K
and numbers rx, ry, rz ∈ d(K×K) the spheres S(x, rx), S(y, ry), S(z, rz)
have no common points in X \K. A proof of the following theorem uses
Theorem 2.3.
Theorem 3.2 ([1]). Let X be a metric space and let G ⊆ Iso(X) be
a group of isometries of X. Then each infinite rigit subset K of X of
cardinality |K| ≥ |G| is kaleidoscopical.
Now we consider the Euclidean space Rn as a G-space with respect to
the group G = Iso(Rn) of all isometries of Rn. Given a cardinal κ ≤ c, it
is easy to find a kaleidoscopical configurations of cardinality κ in R, but
the problem is much more delicate for Rn, n ≥ 2.
Theorem 3.3 ([1]). Any algebraically independent over Q subset A of
an affine line (identified with R) in the Euclidean space Rn is rigid. For
any n ≥ 2, Rn contains 2c kaleidoscopical configurations of cardinality c.
Following [8], we say that a subset A of Rn has the Steinhaus property
if the family {gA : g ∈ Iso(Rn)} has a transversal B. In this case,
B is a transversal of the family {x + A : x ∈ Rn}. By Theorem 4.1
{B − a : a ∈ A} is a partition of Rn. Since each subset B − a is a
transversal of the family {gA : g ∈ Iso(Rn)}, by Theorem 2.1, A is a
kaleidoscopical configuration.
Theorem 3.4 ([6, 7]). The subsets Z × {0}, Q × {0}, Q of R have the
Steinhaus property and hence are kaleidoscopical configurations.
84 Kaleidoscopical Configurations
Theorem 3.5 ([2–4]). The subset Z×Z of R2 has a Steinhaus property
and hence is a kaleidoscopical configuration.
Theorem 3.6 ([15]). The subset Zm ×{0}n−m does not have the Stein-
haus property for 4 ≤ m < n.
Question 3.1. Does there exist a non-trivial finite kaleidoscopical con-
figuration in Rn for n ≥ 2?
We put k(Rn) = min{|F | : |F | > 1 and F is a kaleidoscopical config-
uration in Rn}. It is easy to see that κ(Rn) ≥ χ(Rn), where χ(Rn) is a
chromatic number of Rn. We recall that χ(Rn) is the smallest number
of colors for which there is a coloring of Rn without monochrome points
at the distance 1. It is well known that 4 ≤ χ(R2) ≤ 7 and there is a
conjecture that χ(Rn) = 2n+1 − 1, see [16, §47]. Thus, κ(R2) ≥ 4. We
show that κ(R2) ≥ 5.
For n ≥ 1 and d > 0, a rather red coloring of Rn with respect to d is
a 2-coloring of Rn, with red and blue, such that no two blue points are a
distance d apart. Let mc = min{|F | : F ⊂ R2 and each isometric copy of
F is forbidden for red by some rather red coloring of R2}. By [14, p. 102],
5 ≤ mc ≤ 8.
Now assume that there is a kaleidoscopical configuration K in R2 of
cardinality |K| = 4. Let χ : R2 −→ {1, 2, 3, 4} be the corresponding
kaleidoscopical coloring. We recolor χ′ : R2 −→ {red, blue} by the fol-
lowing rule χ′(x) is blue if and only if χ′(x) = 4. Let d be a distance
between some two points of K. Since χ is kaleidoscopical, we conclude
that χ′ is rather red and each isometric copy of F is forbidden for red,
contradicting mc ≥ 5.
4. Kaleidoscopical configurations in groups
A subset A of a group G is defined to be complemented if there exists
a subset B of G such that the multiplication mapping µ : A × B → G,
(a, b) 7→ ab, is bijective. Following [18], we say that B is a complementer
factor to A and G = AB is a factorization of G. In this case, we have
the partitions
G =
⊔
a∈A
aB =
⊔
b∈B
Ab.
A subset A ⊆ G is called doubly complemented if there are factorizations
G = AB = BC for some subsets B,C of G.
The following interrelations between kaleidoscopical configurations
and factorizations are observed in [1].
I. Protasov, K. Protasova 85
Theorem 4.1. Let A,B be subsets of a group G. Then B is G[A]-
transversal if and only if G = AB−1 is a factorization of G. In particular,
each kaleidoscopical configuration in G is complemented.
Theorem 4.2. A subset A of an Abelian group G is a kaleidoscopical
configuration if and only if A is complemented.
Question 4.1. Is each complemented subset of a (finite) group kaleido-
scopical?
The remaining results of this section are from [11]. We say that a
subset A of a group G is rigid if, for each g ∈ G\A, the set g−1A∩A−1A
is finite. Applying Theorem 2.3 we get:
Theorem 4.3. If A is a countable rigid subset of a group G then A is a
kaleidoscopical configuration.
An injective sequence (an)n∈ω in a group G is called a T -sequence [12]
if there exists a Hausdorff group topology in which (an)n∈ω converges to
the identity e of G.
Theorem 4.4. For every T -sequence (an)n∈ω in a group G, the set A =
{e, an, a
−1
n : n ∈ ω} is a kaleidoscopical configuration. In particular, A
is complemented and G can be partitioned into right translations of A.
Theorem 4.5. Every infinite subset S of an Abelian group G contains
an infinite kaleidoscopical configuration.
Corollary 4.1. If S is an infinite subset of an Abelian group, then S
contains an infinite complemented subset.
Let G be a group defined by the following generators and relations
〈xm, ym : x2
m = y2
m = e, xnxmxn = ym, m < n < ω〉.
Then the subset {xn : n ∈ ω} has no infinite rigid subsets.
Question 4.2. Does every infinite subset of an arbitrary infinite group
contains an infinite kaleidoscopical (complemented) subset?
References
[1] T. Banakh, I. Protasov, O. Petrenko, S. Slobodianiuk, Kaleidoscopical configura-
tions in G-spaces // The Electron J. Comb., 19 (2012), p. 12.
[2] S. Jackson, R. Mauldin, Sets meeting isometric copies of the lattice Z2 in exactly
one point // Proc. Nat. Acad. Sci. USA, 99 (2002), 15883–15887.
86 Kaleidoscopical Configurations
[3] S. Jackson, R. Mauldin, On a lattice problem of H. Steinhaus // J. Amer. Math.
Soc., 15 (2002), 817–856.
[4] S. Jackson, R. Mauldin, Survey on the Steinhaus tiling problem // Bull. Symbolic
Logic., 9 (2003), 335–361.
[5] G. Hajos, Sur la factorisation des groupes abeliens // C̆asopis Pest. Mat. Fys.,
74 (1949), 157–162.
[6] P. Komjath, A lattice-point problem of Steinhaus // Quart. J. Math., 43 (1992),
235–241.
[7] P. Komjath, A coloring result for the plane // J. Appl. Anal., 5 (1999), 113–117.
[8] A. Miller, Set theory of the plane, M873 Topics in Foundations, Spring (2005).
[9] I. Protasov, T. Banakh, Ball Structures and Colorings of Graphs and Groups,
Math. Stud. Monogr. Ser., Vol. 11, VNTL Publisher, Lviv, 2003.
[10] I. Protasov, K. Protasova, Kaleidoscopical Graphs and Hamming codes, Voronoi’s
Impact on Modern Science, Book 4, Vol. 1, Proc. 4th Intern. Conf. on Ana-
lytic Number Theory and Spatial Tesselations, Institute of Mathematics, NAS of
Ukraine, Kyiv, 2008, 240–245.
[11] I. Protasov, S. Slobodianiuk, Kaleidoscopical configurations in groups // Math.
Stud., 36 (2011), 115–118.
[12] I. Protasov, E. Zelenyuk, Topologies on Groups Determined by Sequences, Math.
Stud. Monogr. Ser., Vol. 4, VNTL Publisher, Lviv, 1999.
[13] K. D. Protasova, Kaleidoscopical graphs, Math. Stud., 18 (2002), 3–9.
[14] Ramsey Theory, Yesterday, Today and Tomorrow, Ed. A. Soifer, Birkhauser,
2010.
[15] J. Schmerl, Coloring Rn // Trans. Amer. Math. Soc., 354 (2002), 967–974.
[16] A. Soifer, The Mathematical Coloring Book. Mathematics of Coloring and the
Colorful Life of its Creators, Springer, 2009.
[17] S. Szabo, Topics in Factorization of Abelian Groups, Birkhauser Basel, 2005.
[18] S. Szabo, A. Sands Factoring groups into subsets, CRC Press, 2009.
Contact information
Igor Protasov,
Ksenia Protasova
Department of Cybernetics
National Taras Shevchenko
University of Kiev
Academic Glushkov St. 4d
03680 Kiev,
Ukraine
E-Mail: i.v.protasov@gmail.com,
ksuha@freenet.com.ua
|