Decompositions of set-valued mappings
Gespeichert in:
| Veröffentlicht in: | Algebra and Discrete Mathematics |
|---|---|
| Datum: | 2020 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2020
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/188566 |
| 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: | Decompositions of set-valued mappings / I. Protasov // Algebra and Discrete Mathematics. — 2020. — Vol. 30, № 2. — С. 235–238. — Бібліогр.: 6 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-188566 |
|---|---|
| record_format |
dspace |
| spelling |
Protasov, I. 2023-03-06T14:41:55Z 2023-03-06T14:41:55Z 2020 Decompositions of set-valued mappings / I. Protasov // Algebra and Discrete Mathematics. — 2020. — Vol. 30, № 2. — С. 235–238. — Бібліогр.: 6 назв. — англ. 1726-3255 DOI:10.12958/adm1485 2010 MSC: 03E05, 54E05 https://nasplib.isofts.kiev.ua/handle/123456789/188566 On 100th anniversary of Professor V. S. Čarin en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics Decompositions of set-valued mappings Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Decompositions of set-valued mappings |
| spellingShingle |
Decompositions of set-valued mappings Protasov, I. |
| title_short |
Decompositions of set-valued mappings |
| title_full |
Decompositions of set-valued mappings |
| title_fullStr |
Decompositions of set-valued mappings |
| title_full_unstemmed |
Decompositions of set-valued mappings |
| title_sort |
decompositions of set-valued mappings |
| author |
Protasov, I. |
| author_facet |
Protasov, I. |
| publishDate |
2020 |
| language |
English |
| container_title |
Algebra and Discrete Mathematics |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| issn |
1726-3255 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/188566 |
| citation_txt |
Decompositions of set-valued mappings / I. Protasov // Algebra and Discrete Mathematics. — 2020. — Vol. 30, № 2. — С. 235–238. — Бібліогр.: 6 назв. — англ. |
| work_keys_str_mv |
AT protasovi decompositionsofsetvaluedmappings |
| first_indexed |
2025-11-26T00:12:44Z |
| last_indexed |
2025-11-26T00:12:44Z |
| _version_ |
1850596662289891328 |
| fulltext |
© Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 30 (2020). Number 2, pp. 235–238
DOI:10.12958/adm1485
Decompositions of set-valued mappings
I. Protasov
On 100th anniversary of Professor V. S. Čarin∗
Abstract. Let X be a set, BX denotes the family of all
subsets of X and F : X → BX be a set-valued mapping such that
x ∈ F (x), sup
x∈X
|F (x)| < κ, sup
x∈X
|F−1(x)| < κ for all x ∈ X
and some infinite cardinal κ. Then there exists a family F of bijective
selectors of F such that |F| < κ and F (x) = {f(x) : f ∈ F} for
each x ∈ X. We apply this result to G-space representations of
balleans.
1. Decompositions
For a set X, BX denotes the family of all subsets of X. Given a
set-valued mapping F : X → BX , any function f : X → X such that,
for each x ∈ X, f(x) ∈ F (x) is called a selector of F . We say that a
selector f is bijective if f : X → X is a bijection. For x ∈ X, we denote
F−1(x) = {y ∈ X : x ∈ F (y)}.
In section 1 we prove the mail result and apply it to G-space represen-
tations of balleans in section 2.
Theorem 1. Let F : X → BX be a set-valued mapping such that x ∈ F (x),
supx∈X |F (x)| < κ, supx∈X |F−1(x)| < κ for each x ∈ X and some infinite
cardinal κ. Then there exists a family F of bijective selectors of X such
that |F| < κ and F (x) = {f(x) : f ∈ F} for each x ∈ X.
∗Victor Sil’vestrovich Čarin is known as the founder of topological algebra in Kyiv
University, but his mathematical interests were not bounded by topological groups. He
encouraged and supported the activity of students and collaborators in many areas, in
particular, in combinatorics.
2010 MSC: 03E05, 54E05.
Key words and phrases: set-valued mapping, selector, ballean.
https://doi.org/10.12958/adm1485
236 Decompositions of set-valued mappings
Proof. We consider two cases.
Case κ = ω. We put P = {F (x) : x ∈ X} and define a graph Γ with the
set of vertices P and the set of edges {{F (x), F (y)} : F (x)∩F (y) 6= ∅}. We
take a natural number m such that m > supx∈X |F (x)|, m > sup |F−1(x)|
and show that the local degree of each vertices of Γ does not exceed m2−1.
Assume the contrary and choose y ∈ X and distinct y1, . . . , ym2 ∈ X such
that F (y) ∩ F (yi) 6= ∅} for every i ∈ {1, . . . ,m2}. Then yi ∈ F−1F (y)
but, by the choice of m, we have |F−1F (y)| < m2.
We use the following simple fact [2]: if the local degree of each vertices
of a graph Γ′ does not exceed k then the chromatic number of Γ′ does not
exceed k + 1.
Hence the set P of vertices of Γ can be partition P1, . . . ,Pm2 so that
any two vertices from each Pi are not incident.
To construct the family F , we enumerate Pi = {F (yα) : α < γ}. Let
M = supx∈X |F (x)|. Then we enumerate each F (yα) (with repetitions,
if necessary) F (yα) = {yαj) : j < M}, yα0
= yα. For each j < M , we
define a bijective function fj such that fj acts as a transposition of yα
and yαj at each F (yα) and identically at all other elements of X. We put
Fi = {fj : j < M} and note that F = F1 ∪ . . .∪Fm2 is the desired family
of selectors of F .
Case κ > ω. We take an infinite cardinal σ such that σ < κ and
|F (x)| 6 σ, |F−1(x)| 6 σ for each x ∈ X. Then we define a partition P of
X such that each P ∈ P is the minimal by inclusion subset of X satisfying
F (y) ∈ P , F−1(y) ∈ P for each y ∈ P . Constructively, every P can be
obtained applying to x ∈ P the sequence of operations F , F−1 : F (x),
F−1F (x), FF−1F (x), . . .. Then P is the union of all numbers of this
sequence.
By the choice of σ, we have |P | 6 σ. We enumerate P = {Pα : α < γ},
Pα = {xαj : j < γ}. For each j < σ, we choose a family Fj of bijective
selectors of F such that |Fj | 6 σ and F (xαj) = {f(xαj) : f ∈ Fj} for
each α < γ, see the case κ = ω. Then
⋃
j<σ Fj is the desired family F of
bijective selectors of F .
2. Applications
Let X be a set. A family E of subsets of X × X is called a coarse
structure if
• each E ∈ E contains the diagonal △X , △X = {(x, x) : x ∈ X};
• if E, E′ ∈ E then E ◦E′ ∈ E and E−1 ∈ E , where E ◦E′ = {(x, y) :
∃z((x, z) ∈ E, (z, y) ∈ E′)}, E−1 = {(y, x) : (x, y) ∈ E};
I . Protasov 237
• if E ∈ E and △X ⊆ E′ ⊆ E then E′ ∈ E ;
• for any x, y ∈ X, there exists E ∈ E such that (x, y) ∈ E.
A subset E ′ ⊆ E is called a base for E if, for every E ∈ E , there exists
E′ ∈ E ′ such that E ⊆ E′. For x ∈ X, A ⊆ X we denote E[x] = {y ∈ X :
(x, y) ∈ E}, E[A] = ∪a∈AE[a] and say E[x] and E[A] are balls of radius
E around x and A.
The pair (X, E) is called a coarse space [6] or a ballean [5].
Let (X, E), (X ′, E ′) be coarse spaces. A mapping f : X → X ′ is
called macro-uniform if, for every E ∈ E there exists E′ ∈ E ′ such that
E[x] ⊆ E′[f(x)]. If f is a bijection such that f, f−1 are macro-uniform
then f is called an asymorphism.
Now we describe some general way of constructing balleans. Let G be
a group. A family I of subsets of G is called an ideal if, for every A,B ∈ I
and A′ ⊆ A, we have A ∪B ∈ I and A′ ∈ I. An ideal I is called a group
ideal if F ∈ I for every finite subset of G and A,B ∈ I imply AB−1 ∈ I.
Let a group G acts transitively on a set X by the rule (g, x) 7−→ gx,
g ∈ X, x ∈ X. Every group ideal I on G defines the ballean (X,G, I) on
X with the base of entourages {{(x, y) : y ∈ Ax} : A ∈ I}. By Theorem 1
from [3], for every ballean (X, E), there exist a group G of permutations of
X and a group ideal I on G such that (X, E) is asymorphic to (X,G, I).
Theorem 2. Let (X, E) be a ballean and let κ be an infinite cardinal
such that, for each E ∈ E, supx∈E |E[x]| < κ. Then there exist a group
G of permutations of X and a group ideal I on G such that (X, E) is
asymorphic to (X, E , I) and |A| < κ for each A ∈ I.
Proof. For each E ∈ E , we define a mapping FE : X → BX by FE(x) =
E[x]. By Theorem 1, there exists a family FE of permutations of X such
that |FE | < κ and FE(x) = {f(x) : f ∈ FE} for each x ∈ X. We denote
by I the minimal by inclusion group ideal of G such that FE ∈ I for each
E ∈ E . Then (X, E) is asymorphic to (X,G, I).
In the case κ = ω, Theorem 2 was proved in [4]. For its applications
see Remark 3.5 in [1].
A ballean (X, E) is called cellular if E has a base consisting of equiva-
lence relations. By Theorem 3 from [3], every cellular ballean is asymorphic
to some ballean (X,G, I) such that I has a base consisting of subgroups
of G.
A ballean (X, E) is called finitary if, for every E ∈ E there exists a
natural number m such |E[x]| < m for each x ∈ X. The finitary ballean
238 Decompositions of set-valued mappings
of a G space X is the ballean (X,G, I), where I is the ideal of all finite
subsets of G.
Theorem 3. For every finitary cellular ballean (X, E) there exists a locally
finite group of permutations of X such that (X, E) is asymorphic to the
finitary ballean of G-space X.
Proof. We take a base E ′ of consisting of partitions of X. For every
P ∈ E we pick a natural number nP such that |P | 6 nP for each P ∈ P.
We denote by GP the direct product of the family of symmetric groups
{Sm : m 6 nP} and note that GP acts on each P ∈ P so that GPx = P
for each x ∈ P . Then the group G generated by the family {GP : P ∈ E ′}
satisfies the conclusion of Theorem 3.
References
[1] Cornulier Y. On the space of ends of infinitely generated groups, arXiv: 1901.11073.
[2] A. Harary, Graph Theory, Addison-Wesley, 1994.
[3] O. V. Petrenko, I.V. Protasov, Balleans and G-spaces, Ukr. Mat. Zh. 64 (2012),
344-350.
[4] I.V. Protasov, Balleans of bounded geometry and G-space, Algebra Discrete Math.
2008, no 2, 101-108.
[5] I. Protasov, M. Zarichnyi, General Asymptology, Mat. Stud. Monogr. Ser, vol. 12,
VNTL, Lviv, 2007.
[6] J. Roe, Lectures on Coarse Geometry, Univ. Lecture Ser., vol. 31, American Mathe-
matical Society, Providence RI, 2003.
Contact information
Igor Protasov Faculty of Computer Science and
Cybernetics, Kyiv University,
Academic Glushkov pr. 4d,
03680 Kyiv, Ukraine
E-Mail(s): i.v.protasov@gmail.com
Received by the editors: 29.10.2019.
mailto:i.v.protasov@gmail.com
I. Protasov
|