Z-, R- и H-сечения полугруппы сильных эндоморфизмов неориентированных графов
В статье показано, что моноид сильных эндоморфизмов конечного неориентированного графа без кратных ребер содержит единственное с точностью до изоморфизма R-сечение. Найдены необходимые и достаточные условия существования H -сечениий и построены примеры L-сечений. Доказано, что любое L-, R- и H -сече...
Gespeichert in:
| Veröffentlicht in: | Труды Института прикладной математики и механики |
|---|---|
| Datum: | 2013 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2013
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/124178 |
| 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: | Z-, R- и H-сечения полугруппы сильных эндоморфизмов неориентированных графов / Е.А. Бондарь // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2013. — Т. 27. — С. 41-50. — Бібліогр.: 20 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-124178 |
|---|---|
| record_format |
dspace |
| spelling |
Бондарь, Е.А. 2017-09-22T10:25:59Z 2017-09-22T10:25:59Z 2013 Z-, R- и H-сечения полугруппы сильных эндоморфизмов неориентированных графов / Е.А. Бондарь // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2013. — Т. 27. — С. 41-50. — Бібліогр.: 20 назв. — рос. 1683-4720 https://nasplib.isofts.kiev.ua/handle/123456789/124178 512.53 В статье показано, что моноид сильных эндоморфизмов конечного неориентированного графа без кратных ребер содержит единственное с точностью до изоморфизма R-сечение. Найдены необходимые и достаточные условия существования H -сечениий и построены примеры L-сечений. Доказано, что любое L-, R- и H -сечение полугруппы сильных эндоморфизмов представляет собой прямое произведение соответствующих сечений на симметрических полугруппах. У статтi показано, що моноїд сильних ендоморфiзмiв скiнченного неорiєнтованого графа без кратних ребер мiстить єдиний з точнiстю до iзоморфiзма R-зрiз. Знайдено необхiднi та достатнi умови iснування H -зрiзiв та побудовано приклади L-зрiзiв. Доведено, що будь-який L-, R- та H-зрiз напiвгрупи сильних ендоморфiзмiв є прямим добутком вiдповiдних зрiзiв на симетричних напiвгрупах. In the present paper we show that the strong endomorphism monoid of a finite undirected graph without multiply edges contains a unique R-cross-section up to an isomorphism. We find necessary and sufficient conditions of an existence of H -cross-sections and construct examples of L-cross-sections. Also we prove that any L-, R- and H -cross-section of the strong endomorphism semigroup is isomorphic to the direct product of the corresponding cross-sections in symmetric semigroups. ru Інститут прикладної математики і механіки НАН України Труды Института прикладной математики и механики Z-, R- и H-сечения полугруппы сильных эндоморфизмов неориентированных графов L-, R- та H -зрiзи напiвгрупи сильних ендоморфiзмiв неорiєнтованих графiв L-, R- and H -cross-sections in the strong endomorphism semigroup of the undirected graphs Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Z-, R- и H-сечения полугруппы сильных эндоморфизмов неориентированных графов |
| spellingShingle |
Z-, R- и H-сечения полугруппы сильных эндоморфизмов неориентированных графов Бондарь, Е.А. |
| title_short |
Z-, R- и H-сечения полугруппы сильных эндоморфизмов неориентированных графов |
| title_full |
Z-, R- и H-сечения полугруппы сильных эндоморфизмов неориентированных графов |
| title_fullStr |
Z-, R- и H-сечения полугруппы сильных эндоморфизмов неориентированных графов |
| title_full_unstemmed |
Z-, R- и H-сечения полугруппы сильных эндоморфизмов неориентированных графов |
| title_sort |
z-, r- и h-сечения полугруппы сильных эндоморфизмов неориентированных графов |
| author |
Бондарь, Е.А. |
| author_facet |
Бондарь, Е.А. |
| publishDate |
2013 |
| language |
Russian |
| container_title |
Труды Института прикладной математики и механики |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| title_alt |
L-, R- та H -зрiзи напiвгрупи сильних ендоморфiзмiв неорiєнтованих графiв L-, R- and H -cross-sections in the strong endomorphism semigroup of the undirected graphs |
| description |
В статье показано, что моноид сильных эндоморфизмов конечного неориентированного графа без кратных ребер содержит единственное с точностью до изоморфизма R-сечение. Найдены необходимые и достаточные условия существования H -сечениий и построены примеры L-сечений. Доказано, что любое L-, R- и H -сечение полугруппы сильных эндоморфизмов представляет собой прямое произведение соответствующих сечений на симметрических полугруппах.
У статтi показано, що моноїд сильних ендоморфiзмiв скiнченного неорiєнтованого графа без кратних ребер мiстить єдиний з точнiстю до iзоморфiзма R-зрiз. Знайдено необхiднi та достатнi умови iснування H -зрiзiв та побудовано приклади L-зрiзiв. Доведено, що будь-який L-, R- та H-зрiз напiвгрупи сильних ендоморфiзмiв є прямим добутком вiдповiдних зрiзiв на симетричних напiвгрупах.
In the present paper we show that the strong endomorphism monoid of a finite undirected graph without multiply edges contains a unique R-cross-section up to an isomorphism. We find necessary and sufficient conditions of an existence of H -cross-sections and construct examples of L-cross-sections. Also we prove that any L-, R- and H -cross-section of the strong endomorphism semigroup is isomorphic to the direct product of the corresponding cross-sections in symmetric semigroups.
|
| issn |
1683-4720 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/124178 |
| citation_txt |
Z-, R- и H-сечения полугруппы сильных эндоморфизмов неориентированных графов / Е.А. Бондарь // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2013. — Т. 27. — С. 41-50. — Бібліогр.: 20 назв. — рос. |
| work_keys_str_mv |
AT bondarʹea zrihsečeniâpolugruppysilʹnyhéndomorfizmovneorientirovannyhgrafov AT bondarʹea lrtahzrizinapivgrupisilʹnihendomorfizmivneoriêntovanihgrafiv AT bondarʹea lrandhcrosssectionsinthestrongendomorphismsemigroupoftheundirectedgraphs |
| first_indexed |
2025-11-25T22:46:34Z |
| last_indexed |
2025-11-25T22:46:34Z |
| _version_ |
1850573211538817024 |
| fulltext |
ISSN 1683-4720 Труды ИПММ НАН Украины. 2013. Том 27
УДК 512.53
c©2013. Е.А. Бондарь
L -, R- И H -СЕЧЕНИЯ ПОЛУГРУППЫ СИЛЬНЫХ
ЭНДОМОРФИЗМОВ НЕОРИЕНТИРОВАННЫХ ГРАФОВ
В статье показано, что моноид сильных эндоморфизмов конечного неориентированного графа без
кратных ребер содержит единственное с точностью до изоморфизма R-сечение. Найдены необ-
ходимые и достаточные условия существования H -сечениий и построены примеры L -сечений.
Доказано, что любое L -, R- и H -сечение полугруппы сильных эндоморфизмов представляет со-
бой прямое произведение соответствующих сечений на симметрических полугруппах.
Ключевые слова: моноид, сильный эндоморфизм, отношения Грина, сечение.
1. Введение. Пусть S – некоторая полугруппа и ρ – эквивалентность на ней.
Подполугруппа полугруппы S называется ρ-сечением S, если она содержит в точ-
ности по одному представителю из каждого класса эквивалентности. Естественный
интерес вызывает изучение сечений тех эквивалентностей, которые связаны каким-
либо образом с операцией на полугруппе. В этом смысле важную роль в теории
полугрупп играют отношения Грина.
Изучая редуктивные моноиды, Л.Реннер в своей работе [1] ввел понятие элемен-
та, сохраняющего порядок, и использовал его для описания алгебраических свойств
моноида. Оказалось, что множество элементов, сохраняющих порядок, образует ин-
версный моноид и является H -сечением. Д.Коуэн и Н.Рейли [2] показали, что лю-
бое H -сечение симметрической инверсной полугруппы на множестве X (|X| 6= 3)
состоит только из тех преобразований X, которые сохраняют некоторый зафиксиро-
ванный на X линейный порядок. Позднее, в [3] были описаны R- и, двойственным
образом, L -сечения конечной симметрической инверсной полугруппы. В отличие
от H -сечений, R- (L -) сечения конечной симметрической инверсной полугруппы в
общем случае не изоморфны между собой, а число различных попарно неизоморф-
ных R- (L -) сечений равно числу всех возможных разложений положительного
целого числа n в неупорядоченную сумму положительных целых чисел. В [4] было
показано, что каждое конечное частично упорядоченное множество можно вложить
в некоторое идемпотентное D-сечение конечной симметрической инверсной полу-
группы. Для бесконечной симметрической инверсной полугруппы описание H -, R-
(L -) сечений можно найти в [5].
Сечения отношений Грина изучались и на других полугруппах. Так, в [6] класси-
фицированы все R- (L -) сечения полугруппы Брауэра. В [7] описаны сечения всех
отношений Грина на симметрической инверсной 0-категории, подсчитано их коли-
чество в конечном случае и найдены условия изоморфности сечений. Для конечной
симметрической полугруппы Tn все H - и R-сечения описаны в [8]. При этом до-
казано, что R-сечение единственно с точностью до изоморфизма. В то же время
в [9] построены примеры неизоморфных L -сечений для T4. Таким образом, в слу-
41
Е.А. Бондарь
чае симметрической полугруппы не имеет места двойственное описание L -сечений.
Строение R-сечений бесконечной симметрической полугруппы можно найти в [10].
Теорема Кэли для полугрупп дает естественную мотивацию для изучения раз-
личных подполугрупп симметрической полугруппы. Среди всех таких подполу-
групп, благодаря своей информативности, на первый план выходят различные по-
лугруппы эндоморфизмов алгебраических систем и, в частности, реляционных. Це-
лью настоящей статьи является изучение L -, R- и H -сечений моноида сильных
эндоморфизмов конечного неориентированного графа без кратных ребер. Понятие
сильного эндоморфизма графа было введено в [11] и изучалось вместе с другими ти-
пами эндоморфизмов, например, в работах [12]–[14]. Точное представление моноида
сильных эндоморфизмов конечного неориентированного графа без кратных ребер в
виде сплетения группы и некоторой малой категории было получено в [15]. Позже
этот результат был обобщен для некоторых конечных n-однородных гиперграфов в
[16], а для определенных бесконечных графов и гиперграфов – в [17].
Статья построена следующим образом. В §2 приведены основные определения
и факты, необходимые для дальнейшего изложения материала. Третий параграф
посвящен исследованию строения R- и L -сечений полугруппы сильных эндомор-
физмов. В §4 показано, что моноид сильных эндоморфизмов конечного неориенти-
рованного графа имеет единственное H -сечение.
2. Предварительные сведения. Все не определенные в работе понятия можно
найти, например, в [18]–[20].
Хорошо известно, что на любой полугруппе всегда можно определить пять отно-
шений эквивалентности L ,R,H , D ,J , называемых отношениями Грина. Напом-
ним, что два элемента полугруппы S называются L - (R-) эквивалентными, если они
порождают один и тот же главный левый (правый) идеал в S и J -эквивалентными,
если они порождают один и тот же двусторонний идеал. Композиция отношений эк-
вивалентности L и R обозначается через D , а их пересечение – через H .
Пусть G = (V, E) – произвольный конечный неориентированный граф без крат-
ных ребер с множеством вершин V и множеством ребер E. Mножество вершин и ре-
бер графа G будем также обозначать, соответственно, V (G) и E(G). Преобразование
f множества вершин V графа G называется сильным эндоморфизмом, если для всех
x, y ∈ V условие {x, y} ∈ E выполняется тогда и только тогда, когда {xf, yf} ∈ E.
Множество SEndG всех сильных эндоморфизмов относительно композиции преоб-
разований образует подполугруппу с единицей в полугруппе всех эндоморфизмов
графа G.
Для произвольного преобразования f графа G через Sf обозначается правиль-
ный подграф из G такой, что V (Sf ) = V (G)f .
Пусть ϕ : X → Y – произвольное отображение, A – подмножество из X. Через ρϕ
обозначается отношение равнозначности отображения ϕ, а через ϕ|A – ограничение
ϕ на A.
Отношения Грина на SEndG описывает следующая теорема:
Теорема 1. [13] Пусть G – произвольный конечный неориентированный граф
без петель и кратных ребер, f, g ∈ SEndG. Тогда
42
L -, R- и H -сечения полугруппы сильных эндоморфизмов неориентированных графов
(i) (f, g) ∈ R тогда и только тогда, когда ρf = ρg;
(ii) (f, g) ∈ L тогда и только тогда, когда Sf = Sg;
(iii) (f, g) ∈ H тогда и только тогда, когда ρf = ρg и Sf = Sg;
(iv) (f, g) ∈ D тогда и только тогда, когда Sf
∼= Sg.
Для конечных неориентированных графов без кратных ребер (возможно, с пет-
лями) описание отношений Грина на SEndG идентично.
Говорят, что две вершины x и y графа G смежны, если множество {x, y} яв-
ляется ребром этого графа. Множеством связности N(x) вершины x ∈ V назы-
вается множество всех вершин графа G, смежных с вершиной x. Определим на
множестве вершин графа G отношение эквивалентности ν, положив xνy ⇔ N(x) =
= N(y). Через xν обозначим класс эквивалентности по ν, содержащий x. Канони-
ческим сильным фактор-графом G/ν называется граф, множество вершин которо-
го – фактор-множество V/ν, а множество {aν , bν} является ребром тогда и только
тогда, когда {a, b} ∈ E(G).
Как было упомянуто выше, полугруппу сильных эндоморфизмов конечного
неориентированного графа без кратных ребер можно представить в виде сплете-
ния группы и малой категории:
SEndG ∼= AutU wr KG, (1)
где U – канонический сильный фактор-граф графа G, KG – категория, объектами
которой являются классы из U , а морфизмами – отображения (подробнее см. [15]).
В связи с этим представлением каждый элемент из SEndG будем отождествлять с
некоторой парой (α, f), где α ∈ AutU , f ∈ Map(ObKG,MorKG) и для любого A ∈ U
Af = fA, fA ∈ Map(A, Aα).
Положим везде далее G – конечный неориентированный граф без кратных ре-
бер, U – его канонический сильный фактор-граф, |U | = m. Если X – n-элементное
множество, то симметрическая полугруппа T (X) также обозначается через Tn.
Пусть S(G) = {(α, g) ∈ SEndG|α = iU}, где iU – тождественный автоморфизм
U , gA ∈ T (A), A ∈ U . Очевидно, S(G) образует подполугруппу полугруппы SEndG.
Cледующая лемма имеет непосредственное отношение к основным результатам
статьи.
Лемма 2. Пусть K – одно из отношений Грина L , R или H на S(G). Лю-
бое K -сечение K полугруппы S(G) изоморфно прямому произведению некоторых
K -сечений K1, K2, . . . ,Km симметрических полугрупп T (A1), T (A2), . . . , T (Am),
Ai ∈ U .
Доказательство. Из строения (1) SEndG видно, что для ϕ = (α, q) ∈ SEndG от-
ношение ρϕ и образ im(ϕ) зависят на самом деле, соответственно, от ρqAi
и im(qAi)
отображений qAi ∈ Map(Ai, Aiα), Ai ∈ U . У элементов (α, q) ∈ S(G) отображе-
ния qAi представляют собой преобразования из T (Ai). Пусть K – произвольное
43
Е.А. Бондарь
K -сечение полугруппы S(G) и (iU , f), (iU , g) ∈ K – два произвольных элемента.
Для каждого i ∈ {1, 2, . . . ,m} обозначим через Ki множество таких преобразований
hAi ∈ T (Ai), что (iU , h) ∈ K. Заметим, что для любого i ∈ {1, 2, . . . , m}
(
(iU , f)(iU , g)
)∣∣∣
Ai
= (iU , fg)|Ai = fAigAi ∈ T (Ai),
откуда fAigAi ∈ Ki. Таким образом, Ki – подполугруппа T (Ai), 1 ≤ i ≤ m. Понятно,
что Ki, 1 ≤ i ≤ m должна содержать хотя бы по одному представителю из каждого
класса эквивалентности K на T (Ai). Зафиксируем произвольное i и предположим,
что Ki содержит два K -эквивалентных на T (Ai) преобразования: pAi и qAi .
Заметим, что сечение K всегда будет содержать идемпотент (iU , h), определен-
ный по правилу: hAj – некоторое константное преобразование в случае если j 6= i,
1 ≤ j ≤ m, а hAi = iAi . Понятно, что произведения (iU , p)(iU , h), (iU , q)(iU , h) ∈ K.
Обозначим α = (iU , ph), β = (iU , qh). Для всех j ∈ {1, 2, . . . , m} имеем тогда
Aj(ph) = pAjhAj =
{
hAj , если j 6= i,
pAi , в противном случае;
Aj(qh) = qAjhAj =
{
hAj , если j 6= i,
qAi , в противном случае.
Учитывая, что pAiK qAi получим αK β, следовательно, α = β, откуда pAi = qAi .
Таким образом, Ki является K -сечением на T (Ai).
Пусть Ki – K -сечение на T (Ai), 1 ≤ i ≤ m,
1 4
Рис. 1. Граф Y
K – множество всех элементов (iU , f) ∈ S(G), для
которых fAi ∈ Ki для всех i, 1 ≤ i ≤ m. По-
скольку умножение элементов из S(G) сводится к
умножению преобразований на классах, то, очевид-
но, K образует подполугруппу в S(G), изоморфную
K1 ×K2 × . . . ×Km. При этом в K содержатся представители каждого из классов
эквивалентности K на S(G): любой элемент (iU , h) ∈ S(G) будет K -эквивалентен
(iU , h′) ∈ K такому, что h′Ai
K hAi , h′Ai
∈ Ki, 1 ≤ i ≤ m. Если же (iU , f), (iU , g) ∈ K
– два произвольных элемента и (iU , f)K (iU , g), то fAiK gAi (1 ≤ i ≤ m), откуда
fAi = gAi . Из доказанного выше следует, что K есть K -сечение полугруппы S(G)
такое, что K ∼= ∏m
i=1 Ki. ¤
Заметим, что если K = D = J , в общем случае K изоморфно вкладывается в∏m
i=1 Ki. Рассмотрим, например, граф Y (рис. 1).
Имеем A1 = {1, 2}, A2 = {3, 4}. Без ограничения общности, можем считать, что
K1 = {( 12
12 ) , ( 12
11 )}, K2 = {( 34
34 ) , ( 34
33 )}. Прямое произведение K1 × K2 содержит с
точностью до изоморфизма сильные эндоморфизмы ϕ = ( 1234
1233 ), ψ = ( 1234
1134 ), причем
нетрудо видеть, что Sϕ
∼= Sψ. Таким образом, K1 ×K2 не может служить сечением
для S(G).
3. Описание R-сечений. Установим связь между R-сечениями SEndG и R-
сечениями полугруппы S(G).
44
L -, R- и H -сечения полугруппы сильных эндоморфизмов неориентированных графов
Лемма 3. Пусть R ⊆ SEndG. Множество R есть R-сечение полугруппы S(G)
тогда и только тогда, когда R является R-сечением полугруппы SEndG.
Доказательство. Покажем, что всякое R-сечение R на S(G) является R-се-
чением и для SEndG. Действительно, пусть (β, f) – произвольный элемент из
SEndG. Понятно, что для всякого fAi ∈ Map(Ai, Aiβ), Ai ∈ U можно найти та-
кие преобразования hAi ∈ T (Ai), что ρhAi
= ρfAi
. Пусть (iU , h) ∈ S(G) такое, что
ρhAi
обладает указанным свойством для всех Ai ∈ U . Тогда (β, f)R(iU , h).
Пусть теперь R – R-сечение полугруппы SEndG. Покажем, что R ⊆ S(G).
Предположим, что некоторый сильный эндоморфизм ϕ = (β, f) /∈ S(G) принад-
лежит R. Тогда, во-первых, ϕ2 6= ϕ, и во-вторых, βl = iU для некоторого натурально-
го l ≥ 3. Рассмотрим преобразования ϕ1 = ϕl, ϕ2 = (ϕ1)2 = ϕ2l, ϕ2 = (ϕ1)3 = ϕ3l, . . .
и т. д. пока для некоторого r не получим ϕr = ϕrl – идемпотент. Это означает, что
преобразование ϕr из R ∩ S(G). Сравним теперь преобразования ϕr и ϕϕr из R: с
одной стороны ϕϕr 6= ϕr, поскольку им соответствуют разные автоморфизмы β и
iU , а с другой стороны – ρϕϕr = ρϕr , поскольку ρϕ ⊆ ρϕr . Из полученного противо-
речия следует, что R ⊆ S(G). Таким образом, R является R-сечением полугруппы
S(G). ¤
Теперь, используя Лемму 2, можем описать R-сечения моноида сильных эндо-
морфизмов конечного неориентированного графа без кратных ребер.
Теорема 4. Полугруппа SEndG имеет единственное с точностью до изомор-
физма R-сечение R ∼= R1 × R2 × . . . × Rm, где Ri – R-сечение симметрической
полугруппы T (Ai), 1 ≤ i ≤ m.
Доказательство. Следует из лемм 2 и 3, а также того, что для каждого класса
Ai ∈ U можно построить единственное с точностью до изоморфизма R-сечение
полугруппы T (Ai) [8]. ¤
Учитывая, что число всех R-сечений полугруппы Tn равно n! [8], получаем
Следствие 5. Пусть ki – мощность класса Ai ∈ U , 1 ≤ i ≤ m. Число всех
различных R-сечений полугруппы SEndG равно
m∏
i=1
ki!.
Аналогичная связь существует и между L -сечениями S(G) и SEndG.
Лемма 6. Пусть L ⊆ SEndG. Множество L есть L -сечение полугруппы S(G)
тогда и только тогда, когда L – L -сечение полугруппы SEndG.
Доказательство. Пусть L – L -сечение полугруппы S(G), (β, f) ∈ SEndG –
произвольный элемент. Положим A′i = Ai ∩ im(β, f) для всех Ai ∈ U , 1 ≤ i ≤ m.
Тогда (β, f)L (iU , g), где im(gAi) = A′i для всех Ai ∈ U . Таким образом, любой
сильный эндоморфизм L -эквивалентен некоторому из S(G). Поэтому L -сечение L
полугруппы S(G) является L -сечением и для SEndG.
Пусть теперь L – L -сечение SEndG. Покажем, что L содержится в S(G). Пред-
положим, что некоторый сильный эндоморфизм ϕ = (β, f) /∈ S(G) принадлежит
L. Следовательно, βl = iU для некоторого натурального l ≥ 3. Пусть k ≥ l –
такое натуральное число, что преобразование ϕk = ϕkl – идемпотент. Таким об-
разом, преобразование ϕk из L ∩ S(G). Так как im(fAi) ⊇ im(fkl
Ai
) и fkl
Ai
– идем-
45
Е.А. Бондарь
потент, то im(fAi) содержит, по крайней мере, по одному представителю каждого
из классов эквивалентности ρfkl
Ai
, для всех Ai ∈ U . Поэтому im(ϕϕk) = im(ϕk).
Так как ϕk, ϕϕk ∈ L, то должно выполняться равенство ϕk = ϕϕk. Но указанные
преобразования неравны в силу того, что им соответствуют разные автоморфиз-
мы: ϕk = (iU , fkl), а ϕϕk = (β, f)(iU , fkl) = (β, fkl+1). Полученное противоречие
доказывает L ⊆ S(G). ¤
Из лемм 2 и 6 получаем
Следствие 7. Любое L -сечение L полугруппы SEndG изоморфно прямо-
му произведению некоторых L -сечений L1, L2, . . . , Lm симметрических полугрупп
T (A1), T (A2), . . . , T (Am), Ai ∈ U .
Напомним, что L -сечением для Tn может служить следующая конструкция [9].
Пусть на множестве N = {1, 2, . . . , n} задан некоторый линейный порядок ≺.
Обозначим через M ⊆ N такое непустое подмножество, что
M = {i1 ≺ i2 ≺ . . . ≺ ik}.
Положим
τM =
(
1 2 . . . k − 1 k k + 1 . . . n
i1 i2 . . . ik−1 ik ik . . . ik
)
.
Тогда L = {τM |M ⊆ N, M 6= ∅} – L -сечение для Tn.
Пример. Рассмотрим граф, изображенный на рис. 2.
i
h
g
f
ed
c
b
a
1 { , , }A a b c=
2 { }A d=
3 { }A e=
4 { , , , }A f g h i=
U*G
Рис. 2. Граф G∗ и его канонический фактор-граф U
Как видно по каноническому фактор-графу U , описание L -сечений монои-
да SEndG∗ сводится к описанию L -сечений симметрических полугрупп на трех-,
одно-, и четырехэлементном множествах.
Очевидно, что T1 имеет единственное L -сечение, равное T1. Обозначим его L1.
Положим a ≺ b ≺ . . . ≺ i. Тогда согласно приведенной выше конструкции L -
сечениями для T3 и T4 будут, соответственно, полугруппы:
L3 =
{(
abc
aaa
)
,
(
abc
bbb
)
,
(
abc
ccc
)
,
(
abc
abb
)
,
(
abc
acc
)
,
(
abc
bcc
)
,
(
abc
abc
)}
,
L4 =
{(
fghi
ffff
)
,
(
fghi
gggg
)
,
(
fghi
hhhh
)
,
(
fghi
iiii
)
,
(
fghi
fggg
)
,
(
fghi
fhhh
)
,
(
fghi
fiii
)
,
(
fghi
ghhh
)
,
(
fghi
giii
)
,
(
fghi
hiii
)
,
(
fghi
fghh
)
,
(
fghi
fgii
)
,
(
fghi
fhii
)
,
(
fghi
ghii
)
,
(
fghi
fghi
)}
.
46
L -, R- и H -сечения полугруппы сильных эндоморфизмов неориентированных графов
Для T4 можно построить другой пример L -сечения (см. [9]):
L′4 =
{(
fghi
ffff
)
,
(
fghi
gggg
)
,
(
fghi
hhhh
)
,
(
fghi
iiii
)
,
(
fghi
ffhh
)
,
(
fghi
ffii
)
,
(
fghi
gghh
)
,
(
fghi
ggii
)
,
(
fghi
ffgg
)
,
(
fghi
hhii
)
,
(
fghi
fghh
)
,
(
fghi
fgii
)
,
(
fghi
ffhi
)
,
(
fghi
gghi
)
,
(
fghi
fghi
)}
.
Таким образом, примерами L -сечений моноида сильных эндоморфизмов графа
G∗ являются следующие полугруппы:
L3 × L1 × L1 × L4
∼= L3 × L4,
L3 × L1 × L1 × L′4 ∼= L3 × L′4.
4. Описание H -сечений. Для описания H -сечений моноида сильных эндо-
морфизмов нам понадобятся следующие вспомогательные леммы.
Лемма 8. Если U содержит хотя бы один класс мощности > 2, то полугруппа
SEndG не имеет H -сечений.
Доказательство. Не нарушая общности рассуждений, предположим, что
|A1| > 2, где A1 ∈ U , |U | = m. Проведем доказательство, опираясь на подобное
в [8], дополнив его необходимыми изменениями. Определим три следующих H -
класса: H1,H2, H3. Пусть H1 содержит элементы ϕ = (α, g) ∈ SEndG, у которых
G/ρϕ = {{a11}, {a12, . . . , a1|A1|}, A2, . . . , Am}, и образ равен {a11, a13, a2, . . . , am},
где A1 = {a11, a12, . . . , a1|A1|}, ai ∈ Ai, 2 ≤ i ≤ m – произвольные фиксированные
элементы. Из представления (1) (см. §2) видно, что для любого i ∈ {1, 2, . . . ,m} най-
дется такое j ∈ {1, 2, . . . ,m}, что Aiα = Aj . Причем, очевидно, A1α = A1, поскольку
остальные Ai, 2 ≤ i ≤ m принадлежат разбиению целиком. Таким образом, имеем
A1gA1 = {a11, a13} и AigAi = {aj}, где i, j ∈ {2, 3 . . . , m} и Aiα = Aj .
Подобным образом определим H2: пусть всем элементам из класса H2 соответ-
ствуют разбиение {{a11, a12}, {a13, . . . , a1|A1|}, A2, . . . , Am} и образ {a12, a13, a2, . . . ,
am}. Тогда если (β, f) ∈ H2 и Aiβ = Aj для некоторых i, j, то по аналогии с предыду-
щими рассуждениями A1β = A1 и, следовательно, A1fA1 = {a12, a13}, AifAi = {aj},
где i, j ∈ {2, 3 . . . , m}.
Наконец, пусть всем элементам из H3 соответствуют разбиение {{a11, a13},
{a12, . . . , a1|A1|}, A2, . . . , Am} и образ {a11, a12, a2, . . . , am}. Если (γ, h) ∈ H3 и для
каждого i ∈ {1, 2, . . . , m} индекс j ∈ {1, 2, . . . ,m} такой, что Aiγ = Aj , то имеем
A1hA1 = {a11, a12}, если i = j = 1, и AihAi = {aj} – в остальных случаях.
Поскольку квадрат любого элемента каждого из классов H1, H2 и H3 сохраня-
ют и разбиение, и образ, то представители H -сечения полугруппы SEndG будут
идемпотентами. Таким образом,
ϕ1 =
(
a11 a12 a13 . . . a1|A1| A2 . . . Am
a11 a13 a13 . . . a13 a2 . . . am
)
∈ H1,
47
Е.А. Бондарь
ϕ2 =
(
a11 a12 a13 . . . a1|A1| A2 . . . Am
a12 a12 a13 . . . a13 a2 . . . am
)
∈ H2,
ϕ3 =
(
a11 a12 a13 a14 a15 . . . a1|A1| A2 . . . Am
a11 a12 a11 a12 a12 . . . a12 a2 . . . am
)
∈ H3.
Следовательно, H -сечение содержит ψ = ϕ1ϕ2ϕ3 = (µ, q) и ψ2 = (µ2, p). Однако
A1qA1 =
(
a11 a12 a13 . . . a1|A1|
a12 a11 a11 . . . a11
)
, A1pA1 =
(
a11 a12 a13 . . . a1|A1|
a11 a12 a12 . . . a12
)
,
т.е. ψ, ψ2 неравны и принадлежат одному и тому же H -классу. Следовательно, в
условиях предложения невозможно построить H -сечение полугруппы SEndG. ¤
Имеет место следующая лемма о существовании H -сечений в SEndG.
Лемма 9. Полугруппа SEndG имеет H -сечение тогда и только тогда, когда
все классы из U мощности ≤ 2 и для любого (β, f) ∈ SEndG, и всех двухэлемент-
ных классов A ∈ U выполняется Aβ = A или |Aβ| = 1.
Доказательство. Предположим, что H – некоторое H -сечение полугруп-
пы SEndG. По лемме 8 для любого A ∈ U выполняется |A| ≤ 2. Пусть
C = {ϕ ∈ SEndG|G/ρϕ = U}. Очевидно, что для любого γ ∈ C имеем γ2 так-
же из C, и im(γ) = im(γ2). Поэтому в пересечении H ∩ C будут находиться все
идемпотенты из C, и только они.
Предположим теперь, что для некоторого (β, f) ∈ SEndG существует такой
класс A ∈ U , что |A| = 2 = |Aβ| и Aβ 6= A. Не нарушая общности рассужде-
ний, можем считать, что |A1| = |A2| = 2 и A1β = A2. Пусть A1 = {a11, a12}, ai –
произвольные фиксированные представители классов Ai, i ∈ {2, 3, . . . , m}, тогда
(iU , g) =
(
a11a12 A2 . . . Am
a11a12 a2 . . . am
)
∈ SEndG.
Рассмотрим произведение (iU , g)(β, f) = (β, h), где A1hA1 = {a21, a22} и AihAi =
aifAi ∈ Aiβ для всех i ∈ {2, 3, . . . , m}. Таким образом, в SEndG существует H -
класс, элементам которого соответствуют разбиение {{a11}, {a12}, A2, . . . , Am} и об-
раз {a21, a22, a2fA2 , a3fA3 , . . . , amfAm}. Пусть (β, h′) элемент указанного класса, при-
надлежащий H. Тогда произведение
(β, h′)(iU , g) =
(
A1 A2 . . . Am
a2 a2fA2 . . . amfAm
)
∈ C,
но не является идемпотентом, т. е. не принадлежит H. А это противоречит началь-
ному предположению. Отметим здесь также, что из доказанного следует γH γ2
для любого γ ∈ SEndG. Таким образом, все элементы из H идемпотентны, откуда
H ⊆ S(G). Следовательно, H – H -сечение для S(G).
Наоборот, пусть все классы из U мощности ≤ 2, и для любого (β, f) ∈ SEndG,
и всех двухэлементных классов A ∈ U выполняется Aβ = A или |Aβ| = 1. Согласно
48
L -, R- и H -сечения полугруппы сильных эндоморфизмов неориентированных графов
[8] на T (Ai), Ai ∈ U существуют и определены единственным образом H -сечения
Hi, 1 ≤ i ≤ m. По лемме 2 прямое произведение H1 × H2 × . . . × Hm изоморфно
некоторому H -сечению H полугруппы S(G).
Покажем, что для любого (β, f) ∈ SEndG найдется H -эквивалентный элемент
из S(G). Для каждого fA ∈ Map(A,Aβ), A ∈ U определим сюръективное преобразо-
вание pAβ : Aβ → im(fA). Рассмотрим теперь сильный эндоморфизм (iU , p) ∈ S(G).
Нетрудно видеть, что im(iU , p) = im(β, f). Для любого A ∈ U , если A 6= Aβ, то
|Aβ| = 1 и |A ∩ im(β, f)| = 1, откуда A, Aβ ∈ ρ(β,f) ∩ ρ(iU ,p). Если же A = Aβ, то
pAβ = pA = fA и, очевидно, ρfA
= ρpA . Таким образом, ρ(β,f) = ρ(iU ,p). Следователь-
но, (β, f)H (iU , p) и H является H -сечением для SEndG. ¤
Из лемм 2 и 9 следует описание H -сечений моноида SEndG.
Теорема 10. Если полугруппа SEndG имеет H -сечение H, то оно единствен-
но, причем H ∼= H1 ×H2 × . . .×Hm, где Hi – H -сечение T (Ai).
Выводы Описание L -, R- и H -сечений полугруппы сильных эндоморфизмов
конечного неориентированного графа без кратных ребер сводится к описанию со-
ответствующих сечений на симметрических полугруппах, которые уже полностью
или частично изучены (см. Введение). При этом H -сечение SEndG можно постро-
ить тогда и только тогда, когда все классы из U одно- или двухэлементны, а мо-
ноид SEndG удовлетворяет некоторому ограничению. В таком случае полученное
H -сечение моноида SEndG будет единственным. R-сечение моноида сильных эн-
доморфизмов конечного неориентированного графа без кратных ребер можно по-
строить всегда, и оно единственно с точностью до изоморфизма. Полное описание
L -сечений полугруппы SEndG сводится к вопросу об описании L -сечений симмет-
рической полугруппы, который, как известно, пока остается открытым (см., напр.,
[20]).
1. Renner L. Analogue of the Bruhat decomposition for algebraic monoids II // Journal of Algebra. –
1986. – Vol. 101 (2). – P. 303–338.
2. Cowan D., Reilly N. Partial cross-sections of symmetric inverse semigroups // International Journal
of Algebra and Computation. – 1995. – Vol. 5 (3). – P. 259–287.
3. Ganyushkin O., Mazorchuk V. L - and R- Cross-Sections in I S n // Communications in Algebra.
– 2003. – Vol. 31 (9). – P. 4507–5423.
4. Pekhterev V. Idempotent D-cross-sections of the finite inverse symmetric semigroup ISn // Algebra
and Discrete Mathematics. – 2008. – Vol. 3. – P. 84–87.
5. Pekhterev V. H -, R- and L -cross-sections of the infinite symmetric inverse semigroup // Algebra
and Discrete Mathematics. – 2005. – Vol. 1. – P. 92–104.
6. Kudryavtseva G., Maltcev V., Mazorchuk V. L - and R-cross-sections in the Brauer Semigroup //
U.U.D.M. Report 2004:43. – ISSN 1101-3591.
7. Жучок Ю.В. Сечения отношений Грина на симметрической инверсной 0-категории // Алгебра
и логика. – 2012. – Т. 51. – № 4. – С. 458–475.
8. Pekhterev V. H - and R-cross-sections of the full finite semigroup Tn // Alg. Discrete Math. – 2003.
– Vol. 2 (3). – P. 82–88.
9. Kozhuhov I.B. On transversals of the semigroup Tn for the relation L // Kamyanets–Podolsky,
July, 1–7, 2007. – P. 110.
10. Пєхтєрєв В.О. R-зрiзи напiвгрупи TX // Математичнi студiї. – 2004. – Т. 21 (2). – С. 133–139.
11. Čuĺik K. Zur Theorie der Graphen // Časopis Pěst. Mat. – 1958. – Vol. 83. – P. 133–155.
49
Е.А. Бондарь
12. Böttcher M., Knauer U. Endomorphism spectra of graphs // Discrete Mathematics. – 1992. –
Vol. 109. – P. 45–57.
13. Li W-M. Green’s relations on the strong endomorphism monoid of a graph // Semigroup Forum.
– 1993. – Vol. 47. – P. 209–214.
14. Zhuchok Y.V. The monoid of endomorphisms of disconnected hypergraphs // Algebra and Discrete
Mathematics. – 2013. – V. 16, No. 1 – P. 134–150.
15. Knauer U., Nieporte M. Endomorphisms of graphs I. The monoid of strong endomorphisms // Arch.
Math. – 1989. – Vol. 52. – P. 607–614.
16. Бондарь Е.А., Жучок Ю.В. Представления моноида сильных эндоморфизмов конечных n-
однородных гиперграфов // Фундамент. и прикл. матем. – 2013. – Т. 18 (1). – С. 21–34.
17. Бондарь Е.А., Жучок Ю.В. Полугруппы сильных эндоморфизмов бесконечных графов и ги-
перграфов // Укр.мат.журн. – 2013. – Т. 65 (6). – С. 743–754.
18. Клиффорд А., Престон Г. Алгебраическая теория полугрупп. – М: Мир, 1972. – Т. 1. – 278 с.
19. Knauer U. Algebraic Graph Theory: Morphisms, Monoids and Matrices // De Gruyter studies in
mathematics. – 2011. – Vol. 41 – 308 p.
20. Ganyushkin O., Mazorchuk V. Classical Finite Transformation Semigroups: An Introduction. –
Springer-Verlag, 2009. – 317 p. – (Algebra and Applications, v. 9).
E.A. Bondar
L -, R- and H -cross-sections in the strong endomorphism semigroup of the undirected
graphs.
In the present paper we show that the strong endomorphism monoid of a finite undirected graph without
multiply edges contains a unique R-cross-section up to an isomorphism. We find necessary and sufficient
conditions of an existence of H -cross-sections and construct examples of L -cross-sections. Also we prove
that any L -, R- and H -cross-section of the strong endomorphism semigroup is isomorphic to the direct
product of the corresponding cross-sections in symmetric semigroups.
Keywords: monoid, strong endomorphism, Green’s relations, cross-section.
Є.О. Бондар
L -, R- та H -зрiзи напiвгрупи сильних ендоморфiзмiв неорiєнтованих графiв.
У статтi показано, що моноїд сильних ендоморфiзмiв скiнченного неорiєнтованого графа без крат-
них ребер мiстить єдиний з точнiстю до iзоморфiзма R-зрiз. Знайдено необхiднi та достатнi умови
iснування H -зрiзiв та побудовано приклади L -зрiзiв. Доведено, що будь-який L -, R- та H -зрiз
напiвгрупи сильних ендоморфiзмiв є прямим добутком вiдповiдних зрiзiв на симетричних напiв-
групах.
Ключовi слова: моноїд, сильний ендоморфiзм, вiдношення Грiна, зрiз.
Луганский национальный ун-т им. Тараса Шевченко
bondareug@gmail.com
Получено 06.12.12
50
|