Полугруппы сильных эндоморфизмов бесконечных графов и гиперграфов
Визначено один клас нескінченних неорiєнтованих графiв, один клас нескінченних n-однорідних гiперграфiв i доведено, що будь-яка напівгрупа всіх сильних єндоморФізмів графiв i гiперграфiв таких класів ізоморфна вінцевому добутку моноїда перетворень i деякої малої категорії. Знайдено критеріальні умов...
Gespeichert in:
| Veröffentlicht in: | Український математичний журнал |
|---|---|
| Datum: | 2013 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут математики НАН України
2013
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/165488 |
| 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: | Полугруппы сильных эндоморфизмов бесконечных графов и гиперграфов / Е.А. Бондарь, Ю.В. Жучок // Український математичний журнал. — 2013. — Т. 65, № 6. — С. 743–754. — Бібліогр.: 16 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-165488 |
|---|---|
| record_format |
dspace |
| spelling |
Бондарь, Е.А. Жучок, Ю.В. 2020-02-13T17:12:55Z 2020-02-13T17:12:55Z 2013 Полугруппы сильных эндоморфизмов бесконечных графов и гиперграфов / Е.А. Бондарь, Ю.В. Жучок // Український математичний журнал. — 2013. — Т. 65, № 6. — С. 743–754. — Бібліогр.: 16 назв. — рос. 1027-3190 https://nasplib.isofts.kiev.ua/handle/123456789/165488 512.53 Визначено один клас нескінченних неорiєнтованих графiв, один клас нескінченних n-однорідних гiперграфiв i доведено, що будь-яка напівгрупа всіх сильних єндоморФізмів графiв i гiперграфiв таких класів ізоморфна вінцевому добутку моноїда перетворень i деякої малої категорії. Знайдено критеріальні умови регулярності напівгрупи сильних ендоморфізмів нескінченних n-однорідних гіперграфів. We define a class of infinite undirected graphs and a class of infinite n-regular hypergraphs and prove that any semigroup of all strong endomorphisms of the graphs and hypergraphs from these classes is isomorphic to the wreath product of a transformation monoid and a small category. We establish the criterional conditions for the regularity of the semigroup of strong endomorphisms of infinite n-regular hypergraphs. ru Інститут математики НАН України Український математичний журнал Статті Полугруппы сильных эндоморфизмов бесконечных графов и гиперграфов Semigroups of Strong Endomorphisms of Infinite Graphs and Hypergraphs Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Полугруппы сильных эндоморфизмов бесконечных графов и гиперграфов |
| spellingShingle |
Полугруппы сильных эндоморфизмов бесконечных графов и гиперграфов Бондарь, Е.А. Жучок, Ю.В. Статті |
| title_short |
Полугруппы сильных эндоморфизмов бесконечных графов и гиперграфов |
| title_full |
Полугруппы сильных эндоморфизмов бесконечных графов и гиперграфов |
| title_fullStr |
Полугруппы сильных эндоморфизмов бесконечных графов и гиперграфов |
| title_full_unstemmed |
Полугруппы сильных эндоморфизмов бесконечных графов и гиперграфов |
| title_sort |
полугруппы сильных эндоморфизмов бесконечных графов и гиперграфов |
| author |
Бондарь, Е.А. Жучок, Ю.В. |
| author_facet |
Бондарь, Е.А. Жучок, Ю.В. |
| topic |
Статті |
| topic_facet |
Статті |
| publishDate |
2013 |
| language |
Russian |
| container_title |
Український математичний журнал |
| publisher |
Інститут математики НАН України |
| format |
Article |
| title_alt |
Semigroups of Strong Endomorphisms of Infinite Graphs and Hypergraphs |
| description |
Визначено один клас нескінченних неорiєнтованих графiв, один клас нескінченних n-однорідних гiперграфiв i доведено, що будь-яка напівгрупа всіх сильних єндоморФізмів графiв i гiперграфiв таких класів ізоморфна вінцевому добутку моноїда перетворень i деякої малої категорії. Знайдено критеріальні умови регулярності напівгрупи сильних ендоморфізмів нескінченних n-однорідних гіперграфів.
We define a class of infinite undirected graphs and a class of infinite n-regular hypergraphs and prove that any semigroup of all strong endomorphisms of the graphs and hypergraphs from these classes is isomorphic to the wreath product of a transformation monoid and a small category. We establish the criterional conditions for the regularity of the semigroup of strong endomorphisms of infinite n-regular hypergraphs.
|
| issn |
1027-3190 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/165488 |
| citation_txt |
Полугруппы сильных эндоморфизмов бесконечных графов и гиперграфов / Е.А. Бондарь, Ю.В. Жучок // Український математичний журнал. — 2013. — Т. 65, № 6. — С. 743–754. — Бібліогр.: 16 назв. — рос. |
| work_keys_str_mv |
AT bondarʹea polugruppysilʹnyhéndomorfizmovbeskonečnyhgrafovigipergrafov AT žučokûv polugruppysilʹnyhéndomorfizmovbeskonečnyhgrafovigipergrafov AT bondarʹea semigroupsofstrongendomorphismsofinfinitegraphsandhypergraphs AT žučokûv semigroupsofstrongendomorphismsofinfinitegraphsandhypergraphs |
| first_indexed |
2025-11-26T18:03:49Z |
| last_indexed |
2025-11-26T18:03:49Z |
| _version_ |
1850766913678868480 |
| fulltext |
УДК 512.53
Е. А. Бондарь, Ю. В. Жучок (Луган. нац. ун-т им. Т. Шевченко)
ПОЛУГРУППЫ СИЛЬНЫХ ЭНДОМОРФИЗМОВ
БЕСКОНЕЧНЫХ ГРАФОВ И ГИПЕРГРАФОВ
We define a class of infinite undirected graphs and a class of infinite n-uniform hypergraphs and prove that the semigroup
of all strong endomorphisms of graphs and hypergraphs from these classes is isomorphic to the wreath product of a
transformation monoid and a small category. We establish criterial conditions for the regularity of the semigroup of strong
endomorphisms of infinite n-uniform hypergraphs.
Визначено один клас нескiнченних неорiєнтованих графiв, один клас нескiнченних n-однорiдних гiперграфiв i
доведено, що будь-яка напiвгрупа всiх сильних ендоморфiзмiв графiв i гiперграфiв таких класiв iзоморфна вiнцевому
добутку моноїда перетворень i деякої малої категорiї. Знайдено критерiальнi умови регулярностi напiвгрупи сильних
ендоморфiзмiв нескiнченних n-однорiдних гiперграфiв.
1. Введение. Одним из методов исследования алгебраических систем является изучение мно-
жеств отображений, связанных с исходной системой определенным образом. Так, при изучении
графов и их обобщений — гиперграфов — полезными оказываются их полугруппы эндомор-
физмов. Исследованию различных свойств полугрупп эндоморфизмов графов и гиперграфов
посвящено достаточно большое количество работ (см. обзоры [1 – 3]). Вместе с тем лишь
немногие работы посвящены изучению полугрупп эндоморфизмов графов и их подполугрупп
с точностью до изоморфизма (см., например, [4 – 6]).
Понятие сильного эндоморфизма графа было введено в [7] и использовалось для различных
целей. Одним из первых структурных результатов о моноидах сильных эндоморфизмов явля-
ется теорема Кнауэра – Нипорте [4] о точном представлении моноида сильных эндоморфизмов
конечного неориентированного графа без кратных ребер в виде сплетения группы подстано-
вок и малой категории. При этом, как было показано в [4], для бесконечного случая данная
теорема не верна. В работах [8, 9] сильные эндоморфизмы графов вместе с другими типами
эндоморфизмов используются для определения таких понятий, как спектр эндоморфизма и
эндотип графа, с помощью которых можно классифицировать графы. Описание графов, у кото-
рых полугруппы сильных эндоморфизмов являются регулярными моноидами, рассматривалось
в [10, 11]. Отношения Грина на моноиде сильных эндоморфизмов графа и некоторые их ком-
бинаторные свойства изучались в роботах [12, 13]. В настоящей статье мы изучаем строение
моноидов сильных эндоморфизмов бесконечных графов и гиперграфов.
Опишем кратко построение статьи. Второй пункт содержит все основные понятия. В тре-
тьем пункте доказывается, что моноид всех сильных эндоморфизмов любого бесконечного
неориентированного графа заданного класса может быть точно представлен как сплетение
подходящего моноида преобразований и некоторой малой категории. Этот результат дополня-
ет основной результат работы [4]. В четвертом пункте показано, что любой бесконечный n-
однородный гиперграф является обобщенным лексикографическим произведением некоторых
гиперграфов. Доказано, что полугруппа всех сильных эндоморфизмов любого бесконечного n-
c© Е. А. БОНДАРЬ, Ю. В. ЖУЧОК, 2013
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 6 743
744 Е. А. БОНДАРЬ, Ю. В. ЖУЧОК
однородного гиперграфа заданного класса изоморфна сплетению моноида сильных мономор-
физмов канонического фактор-гиперграфа и малой категории. В последнем пункте изучается
регулярность моноида сильных эндоморфизмов бесконечных n-однородных гиперграфов.
2. Основные понятия. Пусть V — непустое множество, E — некоторое множество неупо-
рядоченных пар элементов из V. Пара X = (V,E) называется неориентированным графом с
множеством вершин V и множеством ребер E. Множество вершин и ребер графа X будем
обозначать также через V (X) и E(X) соответственно. Далее под графом X будем понимать
неориентированный граф (V,E) без кратных ребер. Говорят, что две вершины x и y графа
X смежны, если множество {x, y} является ребром этого графа. Множеством связности N(x)
вершины x ∈ X называется множество всех вершин графа X, смежных с вершиной x.
Определим на множестве вершин графа X отношение эквивалентности ν, положив
xνy ⇔ N(x) = N(y).
Через xν обозначим класс эквивалентности по ν, содержащий x. Каноническим сильным
фактор-графом X/ν называется граф, множество вершин которого — фактор-множество V/ν, а
множество {aν , bν} является ребром тогда и только тогда, когда {a, b} ∈ E(X).
Если X и Y — графы, то гомоморфизмом графа X в Y называется отображение f : X → Y,
для которого из того, что {x, y} ∈ E(X), следует, что {xf, yf} ∈ E(Y ) для любых x, y ∈ X.
Если f биективно и f−1 тоже гомоморфизм, то f называется изоморфизмом. Гомоморфизм
f : X → Y называется сильным гомоморфизмом, если из того, что {xf, yf} ∈ E(Y ), следует,
что {x, y} ∈ E(X) для любых x, y ∈ X. Группу всех автоморфизмов графаX обозначим AutX,
а моноид его сильных эндоморфизмов — SEndX. Отметим, что композиция отображений везде
в работе осуществляется слева направо.
Пусть G — класс всех бесконечных неориентированных графов X без кратных ребер, для
которых при любом ϕ ∈ SEndX выполняется условие
∀ xν ∈ X/ν ∃ yν ∈ X/ν : xνϕ ⊆ yν . (1)
Определенный таким образом класс G непуст. Рассмотрим, например, бесконечный граф
...
1 3 4 52
1X
Пусть k ∈ V (X1) — фиксированное число. Тогда преобразование
xϕk = x+ k − 1
задает сильный эндоморфизм графа X1. Более того, все сильные эндоморфизмы графа X1
исчерпываются сильными эндоморфизмами вида ϕk, k ∈ V (X1).
Понятно, что тождественное преобразование является сильным эндоморфизмом, который
можно представить как ϕ1.
Пусть ϕ ∈ SEndX1 и a, b ∈ V (X1) такие, что aϕ = b. Если a = b = 1, то ϕ = ϕ1.
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 6
ПОЛУГРУППЫ СИЛЬНЫХ ЭНДОМОРФИЗМОВ БЕСКОНЕЧНЫХ ГРАФОВ И ГИПЕРГРАФОВ 745
Если b = 1, а элемент a 6= 1, то (a− 1)ϕ = 2 = (a+1)ϕ. Поскольку {a+1, a+2} ∈ E(X1),
то {a + 1, a + 2}ϕ = {(a − 1)ϕ, (a + 2)ϕ} ∈ E(X1), откуда {a − 1, a + 2} ∈ E(X1), и мы
приходим к противоречию.
Пусть b 6= 1 (a — произвольный), тогда (a + 1)ϕ может быть равным либо b + 1, либо
b − 1. Предположим сначала, что (a + 1)ϕ = b − 1. В случае, когда (a + 2)ϕ = b, получаем,
что (a + 3)ϕ равно b − 1 или b + 1. В каждом из этих случаев {a, a + 3} ∈ E(X1), так как
ϕ — сильный эндоморфизм. Следовательно, (a + 2)ϕ = b − 2. Рассуждая аналогично, можно
показать, что последовательность образов aϕ, (a+1)ϕ, (a+2)ϕ, . . . , (a+b−1)ϕ убывает. Тогда
(a + b − 1)ϕ = 1, где a + b − 1 6= 1, и, как было показано выше, в этом случае получаем
противоречие. Следовательно, (a+ 1)ϕ = b+ 1.
Рассуждая так же, получаем (a+ 2)ϕ = b+ 2, (a+ 3)ϕ = b+ 3 и т. д. Тогда если a = 1, то
единственным образом получаем
1ϕ = b, 2ϕ = b+ 1, 3ϕ = b+ 2, . . . , nϕ = b+ n− 1, . . .
и, следовательно, ϕ = ϕb.
Кроме того, поскольку все классы эквивалентности по отношению ν одноэлементны, для
любого класса xν ∈ X1/ν имеем
xνϕk = {xϕk} = {x+ k − 1} = (x+ k − 1)ν ,
т. е. выполняется условие (1). Таким образом, X1 ∈ G.
Заметим, что класс G не совпадает с классом всех бесконечных неориентированных графов
без кратных ребер. Например, граф X2 (см. рисунок) не принадлежит классу G.
1
2
3
4
5
6
7
8
9
10
11
X
2
...
Действительно, пусть преобразование γ графа X2 такое, как показано на рисунке. Нетрудно
убедиться, что γ — сильный эндоморфизм, при этом в точности две вершины этого графа ν-экви-
валентны и образовывают единственный двухэлементный класс 1ν = {1, 3} в каноническом
сильном фактор-графе X2/ν. Однако 1γ = 5 ∈ 5ν , а 3γ = 7 ∈ 7ν , следовательно, для класса 1ν
условие (1) не выполняется.
3. Сильные эндоморфизмы бесконечных неориентированных графов. Обозначим че-
рез SMonX полугруппу всех сильных инъективных эндоморфизмов графа X. Элементы из
SMonX будем называть сильными мономорфизмами. Понятно, что если граф X конечный, то
SMonX = AutX.
Лемма 3.1. Пусть X — произвольный граф класса G. Преобразование ϕ графа X будет
его сильным эндоморфизмом тогда и только тогда, когда преобразование
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 6
746 Е. А. БОНДАРЬ, Ю. В. ЖУЧОК
ϕ∗ : X/ν → X/ν : xν 7→ (xϕ)ν
является сильным мономорфизмом фактор-графа X/ν.
Доказательство. Пусть ϕ ∈ SEndX, тогда ϕ отображает элементы из разных классов
эквивалентности ν в элементы разных классов. Действительно, если x, y ∈ X такие, что
xν 6= yν , то, не нарушая общности рассуждений, можно предположить, что существует вершина
a ∈ N(x), которая не принадлежит N(y). Тогда {x, a}ϕ = {xϕ, aϕ} ∈ E(X) и {y, a}ϕ =
= {yϕ, aϕ} /∈ E(X), следовательно, (xϕ)ν 6= (yϕ)ν . Таким образом, ϕ∗ инъективно.
Пусть x, y ∈ X. Тогда
{xν , yν} ∈ E(X/ν)⇔ {x, y} ∈ E(X)⇔ {xϕ, yϕ} ∈ E(X)⇔
⇔ {(xϕ)ν , (yϕ)ν} = {xν , yν}ϕ∗ ∈ E(X/ν).
Таким образом, ϕ∗ — сильный мономорфизм графа X/ν.
Пусть теперь преобразование ϕ графа X такое, что ϕ∗ ∈ SMonX/ν. Тогда для лю-
бых x, y ∈ X
{x, y} ∈ E(X)⇔ {xν , yν} ∈ E(X/ν)⇔ {xν , yν}ϕ∗ =
= {(xϕ)ν , (yϕ)ν} ∈ E(X/ν)⇔ {xϕ, yϕ} ∈ E(X).
Лемма 3.1 доказана.
Предложение 3.1. Для каждого графа X класса G справедливо SEndX/ν = SMonX/ν.
Доказательство. Пусть π ∈ SEndX/ν. Зафиксируем в каждом классе A ∈ X/ν по пред-
ставителю Â и определим на множестве X преобразование f, положив af = âνπ для всех
a ∈ X. Для любых не ν-эквивалентных x, y ∈ X
{x, y} ∈ E(X)⇔ {xν , yν} ∈ E(X/ν)⇔ {xνπ, yνπ} ∈ E(X/ν)⇔
⇔ {x̂νπ, ŷνπ} = {x, y}f ∈ E(X).
Если же xνy, то
{x, y} ∈ E(X)⇔ {xν} ∈ E(X/ν)⇔ {xνπ} ∈ E(X/ν)⇔
⇔ {x̂νπ} = {x, y}f ∈ E(X).
Таким образом, f ∈ SEndX и по лемме 3.1 f∗ = π ∈ SMonX/ν.
Предложение 3.1 доказано.
Обобщенным лексикографическим произведением U [(Yu)u∈U ] графа X и графов (Yu)u∈U
называется такой граф, у которого
V (U [(Yu)u∈U ]) = {(u, yu)|u ∈ U, yu ∈ Yu},
а {(u, yu), (v, y′v)} является ребром U [(Yu)u∈U ] тогда и только тогда, когда {u, v} ∈ E(U) или
u = v и {yu, y′u} ∈ E(Yu).
Вполне несвязный граф, т. е. граф без ребер, называется 0-графом.
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 6
ПОЛУГРУППЫ СИЛЬНЫХ ЭНДОМОРФИЗМОВ БЕСКОНЕЧНЫХ ГРАФОВ И ГИПЕРГРАФОВ 747
Предложение 3.2 [4]. Пусть X — произвольный неориентированный граф без кратных
ребер, U = X/ν — его канонический сильный фактор-граф, Yu, u ∈ U — 0-графы такие, что
|Yu| = |u| для всех u ∈ U. Тогда
X ∼= U [(Yu)u∈U ].
Далее будем отождествлять вершины графа X и соответствующие им элементы из обоб-
щенного лексикографического произведения U [(Yu)u∈U ].
Пусть C — малая категория, R — моноид, который действует справа на множестве Ob C
объектов этой категории, и M =
⋃
x,y∈Ob C
MorC(x, y) — множество всех морфизмов категории
C. Через Map(Ob C,M) обозначим множество всех отображений из Ob C в M.
Положим
W = {(r, f)| r ∈ R, f ∈ Map(Ob C,M), xf ∈ MorC(x, xr) для всех x ∈ Ob C}
и для всех (r, f), (s, g) ∈W определим умножение
(r, f)(s, g) = (rs, fgr),
где x(fgr) = xf(xr)g для любого x ∈ Ob C и xf(xr)g — композиция морфизмов xf и (xr)g
в категории C. Заданная таким образом операция ассоциативна. Кроме того, в полугруппе W
есть единица (1, e), где e ∈ Map(X,M) такой, что xe ∈ MorC(x, x) — тождественный морфизм
ix для любого объекта x из C.
Моноид W с таким умножением называется сплетением моноида R с категорией C и
обозначаетсяR wr C. Данная конструкция является двойственной к конструкции, определенной
в [4], где умножение определялось следующим образом:
(r, f)(s, g) = (rs, fpg).
Пусть G = U [(Yu)u∈U ] — произвольный граф класса G. Определим малую категорию KG,
положив ObKG = {Yu |u ∈ U } и обозначив для любых двух объектов Yu, Yv ∈ ObKG через
MorK(Yu, Yv) множество всех отображений из Yu в Yv. Тогда
MorKG =
⋃
u,v∈U
MorKG(Yu, Yv)
и моноид SMonU естественно действует справа на ObKG:
Yuα = Yuα, α ∈ SMonU.
Таким образом, получаем сплетение SMonU wr KG моноида SMonU и малой категории
KG.
Пусть (α, f) ∈ SMonU wr KG, где α ∈ SMonU, f ∈ Map (ObKG,MorKG). Тогда Yuf ∈
∈ Map (Yu, Yuα) для всех Yu ∈ ObKG. Через fu будем обозначать Yuf, где yufu ∈ Yuα для всех
yu ∈ Yu. Одним из основных результатов данной работы является следующая теорема.
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 6
748 Е. А. БОНДАРЬ, Ю. В. ЖУЧОК
Теорема 3.1. Пусть G = U [(Yu)u∈U ] — произвольный граф класса G, KG — малая кате-
гория, определенная ранее. Тогда
SEndG ∼= SMonU wr KG.
Доказательство. Пусть G ∈ G — произвольный граф, ζ ∈ SEndG. По лемме 3.1 преобра-
зование ζ∗ ∈ SMonU. Определим отображение
p : ObKG → MorKG : Yu 7→ pu,
где для каждого u ∈ U имеем
pu : Yu → Yuζ∗ : yu 7→ yv, если (u, yu)ζ = (v, yv).
Таким образом, (u, yu)ζ = (uζ∗, yupu), и корректно заданным будет отображение
ξ : SEndG→ SMonU wr KG : ζ 7→ (ζ∗, p).
Пусть ϕ,ψ ∈ SEndG и ϕξ = (ϕ∗, g), ψξ = (ψ∗, h), (ϕψ)ξ =
(
(ϕψ)∗, f). Тогда
(u(ϕψ)∗, yufu) = (u, yu)(ϕψ) =
(
(u, yu)ϕ)ψ = (uϕ∗, yugu)ψ =
=
(
(uϕ∗)ψ∗, (yugu)huϕ∗) =
(
u(ϕ∗ψ∗), yu(guhuϕ∗)).
Следовательно,
u(ϕψ)∗ = u(ϕ∗ψ∗), yufu = yu(guhuϕ∗).
Итак,
(ϕψ)ξ =
(
(ϕψ)∗, f) = (ϕ∗ψ∗, ghϕ∗) = (ϕ∗, g)(ψ∗, h) = (ϕξ)(ψξ),
т. е. ξ — гомоморфизм.
Пусть ϕ,ψ ∈ SEndG такие, что ϕ 6= ψ. Тогда (u, yu)ϕ 6= (u, yu)ψ для некоторого (u, yu) ∈
∈ G. Следовательно, либо uϕ∗ 6= uψ∗, либо uϕ∗ = uψ∗ и yugu 6= yuhu, т. е. ϕξ 6= ψξ в обоих
случаях.
Далее, возьмем произвольный элемент (γ, q) ∈ SMonU wr KG. Отсюда γ ∈ SMonU, qu ∈
∈ Map(Yu, Yuγ). Рассмотрим преобразование µ графа G такое, что (u, yu)µ = (uγ, yuqu) для
всех (u, yu) ∈ G. Поскольку для любого (v, yv) ∈ G
vµ∗ = ((v, yv)µ)ν = ((vγ, yvqv))ν = vγ,
то µ∗ ∈ SMonU, откуда по лемме 3.1 имеем µ ∈ SEndG. При этом ясно, что µξ = (γ, q).
Теорема 3.1 доказана.
Заметим, что все конечные неориентированные графы без кратных ребер также удовлетво-
ряют условию (1). В самом деле, пусть G — конечный неориентированный граф без кратных
ребер и γ — его сильный эндоморфизм. Так же, как и при доказательстве леммы 3.1, можно
показать, что γ отображает элементы различных классов эквивалентности ν в элементы разных
классов. Следовательно, в силу конечности G в образе любого сильного эндоморфизма этого
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 6
ПОЛУГРУППЫ СИЛЬНЫХ ЭНДОМОРФИЗМОВ БЕСКОНЕЧНЫХ ГРАФОВ И ГИПЕРГРАФОВ 749
графа всегда будет хотя бы один представитель каждого класса эквивалентности ν. Предпо-
ложим, что элементы x, y из G ν-эквивалентны, при этом (xγ, yγ) /∈ ν. Тогда для некоторого
z′ ∈ G имеем {xγ, z′} ∈ E(G) и {yγ, z′} /∈ E(G). Если z ∈ z′νγ
−1, то {x, z} ∈ E(G) и
{y, z} /∈ E(G), что противоречит условию xνy.
Таким образом, теорема 3.1 справедлива для любых неориентированных графов без крат-
ных ребер, удовлетворяющих условию (1). В частности, если граф G конечен, то в качестве
следствия получаем следующий результат.
Теорема 3.2 [4]. Пусть G = U [(Yu)u∈U ] — конечный неориентированный граф без крат-
ных ребер. Тогда
SEndG ∼= AutU wr KG.
4. Сильные эндоморфизмы бесконечных n-однородных гиперграфов. Для конечных
n-однородных гиперграфов описание моноида сильных эндоморфизмов в терминах сплетения
группы и малой категории было анонсировано в [14]. В настоящей работе получен подобный
результат для бесконечных n-однородных гиперграфов, удовлетворяющих условию, аналогич-
ному (1).
Пусть V — произвольное непустое множество, E — семейство непустых (необязательно
различных) подмножеств из V. Пара (V, E) называется гиперграфом с множеством вершин V
и множеством ребер E .
Равные подмножества в E называются кратными ребрами. Если вершина x ∈ V принадле-
жит ребру e ∈ E , говорят, что они инцидентны. Число вершин, инцидентных данному ребру
e ∈ E , называется степенью ребра e и обозначается |e|. Степенью ρ(v) вершины v ∈ V называ-
ется число ребер, инцидентных вершине v.
ЧерезH будем обозначать произвольный гиперграф (V, E).Множество вершин и множество
ребер гиперграфа H будем обозначать также через V (H) и E(H) соответственно.
Пусть n — целое неотрицательное число. Если в гиперграфе H нет кратных ребер и сте-
пень любого ребра e равна n, то гиперграф H называется n-однородным гиперграфом [15].
Обозначим через Cn класс всех n-однородных гиперграфов.
Преобразование α : V → V множества вершин гиперграфа H ∈ Cn называется эндомор-
физмом гиперграфа, если для любогоA ⊆ V из того, чтоA ∈ E , следуетAα ∈ E . Эндоморфизм
α : V → V гиперграфа H ∈ Cn называется сильным эндоморфизмом [16], если для любого
A ⊆ V, |A| = n из того, что Aα ∈ E , следует A ∈ E . Множество всех сильных эндоморфизмов
гиперграфа H ∈ Cn относительно композиции преобразований является полугруппой, которую
далее будем обозначать через SEndH.
Семейством связности N (x) вершины x гиперграфа H ∈ Cn, n ≥ 2, назовем семейство
подмножеств A ⊆ V таких, что
|A| = n− 1 & A ∪ {x} ∈ E .
Лемма 4.1. ПустьH — произвольный гиперграф класса Cn и x, y ∈ H. Тогда существует
сильный эндоморфизм f гиперграфа H такой, что xf = yf в том и только в том случае,
когда выполняется одно из условий:
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 6
750 Е. А. БОНДАРЬ, Ю. В. ЖУЧОК
(i) n = 0;
(ii) n = 1 & ρ(x) = ρ(y);
(iii) n ≥ 2 & N (x) = N (y).
Доказательство. Пусть f ∈ SEndH и xf = yf для некоторых x, y ∈ H. Понятно, что
возможен один из случаев (i), (ii).
Пусть n ≥ 2 и A ⊆ X. Тогда
A ∈ N (x)⇔ A ∪ {x} ∈ E ⇔ Af ∪ {xf} = Af ∪ {yf} ∈ E ⇔ A ∪ {y} ∈ E ⇔ A ∈ N (y).
Таким образом, N (x) = N (y) и необходимость доказана.
Пусть теперь преобразование f гиперграфа H ∈ Cn определяется правилом
zf =
{
x, если z = y,
z — в остальных случаях
для всех z ∈ V. Очевидно, f ∈ SEndH, если n = 0.
Пусть выполняется условие (ii) и a ∈ V. Равносильность a ∈ E ⇔ af ∈ E справедлива
для a = y, так как ρ(x) = ρ(y), и для a 6= y, так как в этом случае af = a. Cледовательно,
f ∈ SEndH.
Пусть далее выполняется условие (iii) и e ⊆ V, |e| = n. Если y /∈ e, то из e ∈ E следует
ef = e ∈ E . Если же y ∈ e, то e = A ∪ {y} и, значит, A ∈ N (x), следовательно,
e ∈ E ⇒ ef = Af ∪ {yf} = A ∪ {x} ∈ E .
Таким образом, f — эндоморфизм.
Пусть ef ∈ E . Если x /∈ ef, то для любого a ∈ ef справедливо af−1 = a, поэтому
e = ef ∈ E . Предположим, что x ∈ ef, т. е. ef = M ∪ {x}, где M ∈ N (x). Тогда либо
e = M ∪ {x} = ef ∈ E , либо e = M ∪ {y} ∈ E , поскольку N (x) = N (y). Случай, когда
e =M ∪ {x, y}, не рассматривается, так как |e| > n. Следовательно, f ∈ S EndH.
Лемма 4.1 доказана.
ПустьH — произвольный гиперграф класса Cn. Из леммы 4.1 следует, что наH естественно
возникает бинарное отношение δ:
xδy ⇔
{
ρ(x) = ρ(y), если n ∈ {0, 1},
N (x) = N (y), если n ≥ 2.
Ясно, что δ — отношение эквивалентности. Обозначим класс эквивалентности, содержащий
элемент a ∈ H, через aδ. Если A ⊆ V, то положим Aδ = {aδ | a ∈ A} . Напомним, что если D =
= {Yi | i ∈ I} — совокупность некоторых подмножеств данного множестваX, то трансверсалью
семейства D называется множество всех представителей, взятых в точности по одному из
каждого подмножества Yi, i ∈ I.
Через H/δ будем обозначать гиперграф, вершины которого состоят из классов эквива-
лентности xδ, x ∈ V, а множество ребер E(H/δ) содержит Aδ, A ⊆ V тогда и только тогда,
когда некоторая трансверсаль семейства Aδ является ребром гиперграфаH. Полученный гипер-
граф назовем каноническим сильным фактор-гиперграфом гиперграфа H. Понятно, что если
Aδ ∈ E(H/δ), то любая трансверсаль семейства Aδ является ребром гиперграфа H.
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 6
ПОЛУГРУППЫ СИЛЬНЫХ ЭНДОМОРФИЗМОВ БЕСКОНЕЧНЫХ ГРАФОВ И ГИПЕРГРАФОВ 751
Обобщенным лексикографическим произведением U [(Yu)u∈U ] гиперграфа U и гиперграфов
(Yu)u∈U назовем такой гиперграф, у которого
V (U [(Yu)u∈U ]) = {(u, yu)|u ∈ U, yu ∈ Yu},
а подмножество A ⊆ V (U [(Yu)u∈U ]) будет ребром тогда и только тогда, когда выполняется
одно из условий:
(i) dom (A) ∈ E(U);
(ii) dom (A) = {a} /∈ E(U) & im (A) ∈ E(Ya).
Предложение 4.1. Пусть H — произвольный гиперграф класса Cn, U = H/δ — его
канонический сильный фактор-гиперграф, Yu, u ∈ U — 0-однородные гиперграфы такие, что
|Yu| = |u| для всех u ∈ U . Тогда
H ∼= U [(Yu)u∈U ].
Доказательство. Для каждого u ∈ U пусть τu — произвольная биекция из класса эквива-
лентности u на множество Yu. Положим
ψ : H → U [(Yu)u∈U ] : x 7→ (xδ, xτxδ).
Пусть x, y — произвольные различные вершины из H. Если (x, y) /∈ δ, то xδ 6= yδ и,
следовательно, xψ 6= yψ. Если (x, y) ∈ δ, то xτxδ 6= yτxδ в силу биективности τu, u ∈ U , и
тогда xψ 6= yψ. Поскольку τu сюръективно, то для любой пары (u, yu) ∈ U [(Yu)u∈U ] существует
t ∈ u такой, что tτu = yu, т. е. tψ = (u, yu).
Поскольку Yu, u ∈ U — 0-однородные гиперграфы, в лексикографическом произведении
U [(Yu)u∈U ] все ребра определяются только условием (i) соответствующего определения. Тогда
для всех A ⊆ V
A ∈ E(H)⇔ Aδ ∈ E(U)⇔ {(xδ, xτxδ) |x ∈ A} = Aψ ∈ E (U [(Yu)u∈U ]) .
Предложение 4.1 доказано.
Далее будем отождествлять вершины гиперграфа H и соответствующие им элементы обоб-
щенного лексикографического произведения U [(Yu)u∈U ].
Пусть Cn — класс всех бесконечных n-однородных гиперграфов H, для которых при любом
ϕ ∈ SEndH выполняется условие
∀ xδ ∈ U ∃ yδ ∈ U : xδϕ ⊆ yδ. (2)
Ясно, что класс C0(C1) совпадает с классом всех бесконечных 0-однородных (1-однородных)
гиперграфов. В случае, когда n ≥ 2 — натуральное, Cn является непустым собственным под-
классом класса всех бесконечных n-однородных гиперграфов.
Лемма 4.2. Пусть H = U [(Yu)u∈U ] — произвольный гиперграф класса Cn. Преобра-
зование ϕ гиперграфа H будет его сильным эндоморфизмом тогда и только тогда, когда
преобразование
ϕ∗ : U → U : xδ 7→ (xϕ)δ
является сильным инъективным эндоморфизмом гиперграфа U.
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 6
752 Е. А. БОНДАРЬ, Ю. В. ЖУЧОК
Доказательство аналогично доказательству леммы 3.1.
Множество всех сильных инъективных эндоморфизмов гиперграфаH образует относитель-
но композиции преобразований полугрупппу, которую обозначим через SMonH. Элементы из
SMonH будем называть сильными мономорфизмами.
Предложение 4.2. Для каждого гиперграфа H класса Cn справедливо равенство
S EndU = SMonU .
Доказательство. ПустьH ∈ Cn. Канонический сильный фактор-гиперграф 0-однородного
гиперграфа является одноэлементным 0-однородным гиперграфом, следовательно, при n =
= 0 имеем S EndU = SMonU . Для случая n ≥ 1 доказательство аналогично доказательству
предложения 3.1.
Предложение 4.2 доказано.
Пусть H = U [(Yu)u∈U ] — произвольный гиперграф класса Cn. Определим малую категорию
KH , положив ObKH = {Yu |u ∈ U }, MorKH =
⋃
u,v∈U MorKH (Yu, Yv), где MorKH (Yu, Yv) —
множество отображений из Yu в Yv. Моноид Mon U при этом естественно действует справа на
множестве объектов этой категории.
Теорема 4.1. Пусть H = U [(Yu)u∈U ] — произвольный гиперграф класса Cn, KH — малая
категория, определенная ранее. Тогда
S EndH ∼= SMonU wr KH .
Доказательство. Пусть ϕ — произвольный сильный эндоморфизм гиперграфа H ∈ Cn. По
лемме 4.2 ϕ∗ ∈ SMonU . Для каждого u ∈ U определим отображение fu множества Yu в Yuϕ∗ ,
положив yufu = yv, если (u, yu)ϕ = (v, yv). Тогда корректно определенным будет отображение
f : ObKH → MorKH : Yu 7→ fu.
Аналогично доказательству теоремы 3.1 можно показать, что отображение
ξ : S EndH → SMonU wr KH : ϕ 7→ (ϕ∗, f)
является изоморфизмом.
Теорема 4.1 доказана.
Заметим, что, как и в случае конечных графов (см. пункт 3), аналогичным образом можно
показать, что конечные n-однородные гиперграфы удовлетворяют условию (2). Следователь-
но, теорема 4.1 справедлива для любых n-однородных гиперграфов, удовлетворяющих усло-
вию (2).
5. Регулярность SEndH. Условия регулярности моноида сильных эндоморфизмов для
конечных неориентированных графов изучались в [4, 10]. В [11] было доказано, что полугруппа
сильных эндоморфизмов произвольного графа регулярна тогда и только тогда, когда сильный
фактор-граф U является S-неразложимым или, что эквивалентно, когда U не содержит ни
одного изоморфного себе собственного подграфа. В этом пункте мы, использовав теорему 4.1,
исследуем регулярность моноида сильных эндоморфизмов гиперграфов класса Cn.
Напомним, что моноид M называется регулярным, если для любого a ∈ M существует
b ∈M такой, что a = aba.
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 6
ПОЛУГРУППЫ СИЛЬНЫХ ЭНДОМОРФИЗМОВ БЕСКОНЕЧНЫХ ГРАФОВ И ГИПЕРГРАФОВ 753
Теорема 5.1. Пусть H = U [(Yu)u∈U ] — произвольный гиперграф класса Cn. Моноид
SEndH регулярен тогда и только тогда, когда гиперграф U не содержит собственных под-
гиперграфов, изоморфных U .
Доказательство. Пусть моноид SEndH регулярен и ϕ,ψ ∈ SEndH такие, что ϕ = ϕψϕ.
Согласно теореме 4.1 ϕ = (ϕ∗, f), ψ = (ψ∗, g). Тогда, так как ϕ∗ = ϕ∗ψ∗ϕ∗, имеем
aψ∗ = aϕ∗−1 для всех a ∈ Imϕ∗,
и, следовательно, (Imϕ∗)ψ∗ = U . Таким образом, если v ∈ U \ Imϕ∗ 6= ∅, то каким бы
ни был образ vψ∗, найдется m ∈ Imϕ∗, m 6= v, такой, что mψ∗ = vψ∗, что противоречит
инъективности ψ∗. Следовательно, Imϕ∗ = U . Таким образом, SMonU = AutU , и, значит,
гиперграф U не содержит собственных подгиперграфов, изоморфных U .
Наоборот, если U не содержит собственных подгиперграфов, изоморфных U , то все элемен-
ты из SMonU сюрьективны и тогда полугруппа SMonU совпадает с AutU . Следовательно,
для любого ϕ можно построить ψ = (ϕ∗−1, g), где
gv ∈ Map(Yv, Yvϕ∗−1), yvgv ∈
{
yv(fvϕ∗−1)−1, если yv ∈ Imfvϕ∗−1 ,
Yvϕ∗−1 — в остальных случаях.
(3)
Для любой пары (u, yu) ∈ U [(Yu)u∈U ] имеем
(u, yu)ϕψϕ = (uϕ∗ϕ∗−1ϕ∗, yufuguϕ∗fuϕ∗ϕ∗−1) = (uϕ∗, yufuguϕ∗fu).
Положим yufu = yu′ ∈ Yuϕ∗=u′ , т. е. yu′ ∈ Imfu′ϕ∗−1 . Тогда согласно (3)
yu′gu′ ∈ yu′(fu′ϕ∗−1)−1 = yu′(fu)
−1.
Кроме того, для любого b ∈ Imfu ⊆ Yu′ и такого a ∈ Yu, что b = afu, справедливо bf−1u fu =
= afu = b, поэтому
yu′gu′fu ∈ yu′f−1u fu = {yu′} = {yufu},
yufuguϕ∗fu = yu′gu′fu = yufu.
Таким образом, (u, yu)ϕψϕ = (uϕ∗, yufuguϕ∗fu) = (uϕ∗, yufu) = (u, yu)ϕ и, следовательно,
SEndH — регулярный моноид.
Теорема 5.1 доказана.
1. Molchanov V. A. Semigroups of mappings on graphs // Semigroup Forum. – 1983. – 27. – P. 155 – 199.
2. Fan S.H. Generalized symmetry of graphs // Electron. Notes Discrete Math. – 2005. – 23. – P. 51 – 60.
3. Kelarev A., Ryan J., Yearwood J. Cayley graphs as classifiers for data mining: The influence of asymmetries // Discrete
Math. – 2009. – 309, № 17. – P. 5360 – 5369.
4. Knauer U., Nieporte M. Endomorphisms of graphs I. The monoid of strong endomorphisms // Arch. Math. – 1989. –
52. – P. 607 – 614.
5. Жучок Ю. В. Ендоморфiзми вiдношень еквiвалентностi // Вiсн. Київ. ун-ту. Фiз.-мат. науки. – 2007. – 3. –
С. 22 – 26.
6. Жучок Ю. В. Полугруппы эндоморфизмов 2-нильпотентных бинарных отношений // Фундам. и прикл. мате-
матика. – 2008. – 14, № 6. – C. 75 – 83.
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 6
754 Е. А. БОНДАРЬ, Ю. В. ЖУЧОК
7. Čuĺik K. Zur Theorie der Graphen // Časopis Pěst. Mat. – 1958. – 83. – P. 133 – 155.
8. Böttcher M., Knauer U. Endomorphism spectra of graphs // Discrete Math. – 1992. – 109. – P. 45 – 57.
9. Böttcher M., Knauer U. Postscript: Endomorphism spectra of graphs // Discrete Math. – 2003. – 270. – P. 329 – 331.
10. Wilkeit E. Graphs with a regular endomorphism monoid // Arch. Math. – 1996. – 66. – P. 344 – 352.
11. Fan S. H. Graphs whose strong endomorphism monoids are regular // Arch. Math. – 1999. – 73. – P. 419 – 421.
12. Li W.-M. Green’s relations on the strong endomorphism monoid of a graph // Semigroup Forum. – 1993. – 47. –
P. 209 – 214.
13. Li W.-M. The monoid of strong endomorphisms of a graph // Semigroup Forum. – 1994. – 49. – P. 143 – 149.
14. Bondar Е. The monoid of strong endomorphisms of hypergraphs // 8-ма мiжнар. алгебр. конф. в Українi: збiрник тез
(англ. мовою) (Луганськ, 5 – 12 липня 2011 р.). – Луганськ: Луган. нац. ун-т iм. Т. Шевченка, 2011. – С. 248 – 250.
15. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. – М.: Наука, 1990. –
384 с.
16. Решетников А. В. Об определениях гомоморфизма гиперграфов // Материалы Х междунар. сем. „ Дискретная
математика и ее приложения” (Москва, 1 – 6 февр. 2010 г.). – М.: Изд-во Моск. гос. ун-та, 2010. – С. 325 – 328.
Получено 02.02.12
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 6
|