Моноиды сильных эндоморфизмов гиперграфов Бондарь Евгения Алексеевна

Содержание к диссертации

Введение

Раздел 1.Общие сведения 16

1.1. Некоторые понятия теории полугрупп 16

1.2. Графы, гиперграфы и их эндоморфизмы 20

1.3. Эндоморфизмы отношений эквивалентности 24

1.4. H -, и R-cечения конечной симметрической полугруппы 31

Раздел 2. Точные представления моноидов сильных эндоморфизмов гиперграфов 33

2.1. Сильные эндоморфизмы бесконечных графов 33

2.1.1. Об одном классе бесконечных графов 33

2.1.2. Сильные эндоморфизмы бесконечных графов выделенного класса 35

2.1.3. Случай произвольных бесконечных графов 40

2.2. Моноиды сильных эндоморфизмов n-однородных гиперграфов 41

2.2.1. Некоторые свойства n-однородных гиперграфов 41

2.2.2. Точные представления моноидов сильных эндоморфизмов конечных n-однородных гиперграфов 45

2.3. Сильные эндоморфизмы бесконечных n-однородных гиперграфов 51

2.3.1. Точное представление моноидов сильных эндоморфизмов гиперграфов из одного класса 51

2.3.2. Случай произвольных n-однородных гиперграфов 54

2.4. Регулярность моноидов сильных эндоморфизмов n-однородных гиперграфов 55

2.4.1. Конечный случай 56

2.4.2. Бесконечный случай з

2.5. Об определяемости гиперграфов сильными эндоморфизмами. 58

Раздел 3. Описание L-, R- и H -сечений моноидов сильных эндоморфизмов конечных графов 61

3.1. L -, R- и H -сечения моноидов сильных эндоморфизмов конечных графов 61

3.1.1. Предварительные сведения 61

3.1.2. R- и L - сечений моноида сильных эндоморфизмов графа 64

3.1.3. H -сечений моноида сильных эндоморфизмов графа 67

3.2. L -сечения конечной симметрической полугруппы Tn 70

3.2.1. Определения L-семейства 71

3.2.2. Описание L -сечений полугруппы Tn 77

3.2.3. Число L -сечений полугруппы Tn 90

3.2.4. Классификация L -сечений Tn до изоморфизма 94

Заключение 102

Литература

• Графы, гиперграфы и их эндоморфизмы
• Сильные эндоморфизмы бесконечных графов выделенного класса
• Случай произвольных n-однородных гиперграфов
• H -сечений моноида сильных эндоморфизмов графа

Введение к работе

Актуальность темы. К производным структурам данного математического объекта относят различные алгебраические системы, связанные с этим объектом. В алгебре исследования производных структур восходят к работам Э. Галуа (XIX век). Со второй половины XX века понятие производных структур приобретает общематематическую значимость: изучение производных структур различных математических объектов становится одним из мощных течений в математике. Достаточно вспомнить, например, полугруппы непрерывных линейных операторов банаховых пространств в функциональном анализе, группы путей в топологии, синтаксические моноиды в теории автоматов. Производные структуры математического объекта зачастую несут существенную информацию об этом объекте и к тому же дают удобный язык для его описания. О важности изучения производных структур свидетельствует появление на стыке алгебры и других областей математики таких активно развивающихся дисциплин, как алгебраическая геометрия, алгебраическая топология, алгебраическая теория автоматов и т.д.

В алгебре типичными примерами производной структуры алгебраической системы являются группа автоморфизмов, моноид эндоморфизмов, полугруппа соответствий, решетка подсистем, решетка конгруэнций и т.д.

Рассмотрим основные постановки задач, связанные с производными структурами. При этом мы следуем классификации таких постановок, данной в монографии Л.Н. Шеврина и А.Я. Овсянникова¹ применительно к решеткам подполугрупп. Здесь мы не даем обзор соответствующей литературы (хотя в диссертации он имеется).

Направление 1. Классификация производных структур, задача пред-¹ Шеврин Л.Н. Полугруппы и их подполугрупповые решетки: в 2-х частях. / Л.Н. Шеврин, А.Я. Овсянников. — Свердловск: Изд-во Урал.ун-та. — 1990. — Ч.1 : Полугруппы с некоторыми типами решеток подполугрупп и решеточные характеризации классов полугрупп. — 238 с.

ставимости. Естественно возникает задача выяснить, обладает ли всякая производная структура данного класса алгебраических систем какими-то специфическими свойствами. Здесь возникает широкий диапазон возможностей — от случаев, когда производные структуры оказываются настолько специфичными, что их удается полностью классифицировать, до противоположных случаев, когда в качестве производной структуры может быть реализован любой алгебраический объект подходящего типа.

Направление 2. Определяемость производной структурой. Вопрос заключается в следующем: что можно сказать о двух алгебраических системах A и B, если их производные стуктуры одного и того же типа изоморфны? Говорят, что алгебраическая система A из некоторого класса определяется своей производной структурой в классе , если для любой алгебраической системы B из изоморфизма производных структур, соответствующих A и B, следует, что A = B.

Направление 3. Изучение объектов с ограничениями на производные структуры. Например, для производных решеток рассматриваются ограничения типа дистрибутивности или модулярности, а для производных моноидов часто рассматривается ограничение регулярности. Напомним, что моноид называется регулярным, если для каждого его элемента a существует такой элемент b, что a = aba.

Направление 4. Взаимосвязь между различными производными структурами одного и того же объекта. Классическим примером жесткой взаимосвязи является теория Галуа: решетка подполей заданного расширения поля однозначно восстанавливается по группе автоморфизмов этого расширения. Противоположной ситуацией является независимость производных структур, когда свойства одной структуры никак не влияют на свойства другой производной структуры того же объекта. Независимость производных структур

для основных классов алгебраических систем изучалась В.А. Баранским².

Областью наших интересов являются полугруппы сильных эндоморфизмов неориентированных графов и их естественных обобщений - гиперграфов

— в рамках направлений 1-3. Всюду дальше под «графом» будем понимать
неориентированный граф без кратных рёбер. Понятие сильного эндоморфиз
ма графа ввел Чулик³ в 1958 г. Пусть G = (V_} Е) граф с множеством
вершин V и множеством рёбер Е. Отображение / : V —> V называется силь
ным эндоморфизмом графа G, если {ж,у} Є Е ^ {xf,yf} Є Е для любых
ж, у Є V. Кнауэр и Нипорте⁴ доказали, что моноид сильных эндоморфизмов
конечного графа представим в виде сплетения группы подстановок и малой
категории. При этом было показано, что для бесконечного случая данная
теорема неверна. Естественно возникает задача:

Задача 1. Найти точное представление моноида сильных эндоморфизмов бесконечного графа.

Гиперграфы⁵ представляют собой обобщения графов, когда ребрами могут быть произвольные подмножества множества вершин, а не только двух-и одноэлементные подмножества. В настоящее время теория гиперграфов — бурно развивающийся раздел математики на стыке теории графов, комбинаторики, топологии и компьютерных наук.

Задача 2. Найти точные представления моноидов сильных эндоморфизмов конечных и бесконечных гиперграфов.

В рамках направления 1 естественно изучать моноиды сильных эндоморфизмов при помощи сечений относительно подходящих эквивалентностей. Для произвольного отношения эквивалентности р на полугруппе S подполу-

² Баранский В. А. Независимость производных структур в классах алгебраических систем [дис. на
соиск. степ. д. ф.-м. н.]. - Свердловск, 1986.

³ Cullk K. Zur Theorie der Graphen / K. Cullk // Casopis Pest. Mat. - 1958. - 83. - P. 133-155.

⁴ Knauer U. Endomorphisms of graphs I. The monoid of strong endomorphisms / U. Knauer, M. Nieporte
// Arch. Math. - 1989. - Vol. 52. - P. 607-614.

⁵ Зыков А. А. Гиперграфы / А. А. Зыков // Успехи математических наук. - 1974. - Т. 29. № 6(180).

- С. 89-153.

группа S' полугруппы S называется р-сечением⁶, если S' содержит в точности по одному представителю из каждого класса эквивалентности. Естественно изучать сечения относительно эквивалентностей, связанных со строением исходной полугруппы, в частности, для отношений Грина. На сегодняшний день сечения отношений Грина уже изучались, например, на инверсной и симметрической⁷ полугруппах преобразований, инверсной 0-категории⁸. Таким образом, возникает

Задача 3. Выяснить, существуют ли сечения отношений Грина на моноиде сильных эндоморфизмов конечного графа. В случае, если такие сечения существуют, описать их.

Оказалось, что описание «?-, &-, Ж-сечений моноида сильных эндоморфизмов тесно связано с описанием этих сечений на конечной симметрической полугруппе <%_. Все Ж- и ^-сечения полугруппы 5; описал В. А. Пехтерев. Он показал, что существует единственное с точностью до изоморфизма ^-сечение ЗГ(Х). Пара неизоморфных ^-сечений ,% была построена И. Б. Кожу-ховым⁹. Вопрос описания и классификации ^-сечений полугруппы ЗГ_п до настоящего времени оставался открытым и явно формулировался в литературе.

Задача 4. Описание и классификация ^-сечений конечной симметрической полугруппы.

Перейдем теперь к направлению 2. Кнауэр и Нипорте показали, что моноид сильных эндоморфизмов конечного графа является регулярным¹⁰. Фан выяснил условия, при которых моноид сильных эндоморфизмов бесконечного

⁶GanyushkinO. Classical Finite Transformation Semigroups: An Introduction. / O. Ganyushkin, V. Mazorchuk. - Springer-Verlag, 2009. - Algebra and Applications, vol. 9. - 317 p.

⁷ Pekhterev V. Ж- and ^-cross-sections of the full finite semigroup T_n / V. Pekhterev // Alg. Discrete
Math. - 2003. - Vol. 2. № 3. - P. 82-88.

⁸ Жучок Ю. В. Сечения отношений Грина на симметрической инверсной 0-категории / Ю. В. Жу
чок // Алгебра и логика. - 2012. - Т. 51. № 4. - С. 458-475.

⁹ Kozhuhov I. B. On transversals of the semigroup T_n for the relation Jz? / I. B. Kozhuhov // Kamyanets-
Podolsky, July, 1-7, 2007. - P. 110.

¹⁰ KnauerU., NieporteM. Endomorphisms of graphs I. The monoid of strong endomorphisms.

графа является регулярным¹¹.

Задача 5. Найти условия, при которых моноиды сильных эндоморфизмов гиперграфов являются регулярными.

Наконец, в рамках направления 3 естествен следующий вопрос.

Задача 6. Определяется ли гиперграф своим моноидом сильных эндоморфизмов?

Цель работы — решить задачи 1–6.

Методы исследования. В работе применяются методы теории полугрупп, связанные с конструкциями сплетения моноида с малой категорией; комбинаторные методы; методы теории графов и гиперграфов.

Научная новизна. Все результаты диссертации являются новыми.

Апробация работы. Основные результаты диссертационной работы были представлены на VIII Международной алгебраической конференции в Украине (г. Луганск, июль 2011 г.), XIV и XV Международных научных конференциях имени академика Михаила Кравчука (г. Киев, апрель 2012 г. и май 2014 г.), Международной математической конференции, посвященной 70-летию В.В. Кириченко (г. Николаев, июнь 2012 г.), IX Международной алгебраической конференции в Украине (г. Львов, июль 2013 г.), Международной алгебраической конференции, посвященной 100-летию со дня рождения Л.A. Калужнина (г. Киев, июль 2014 г.), Международной конференции и школе молодого ученого «Группы и графы, алгоритмы и автоматы», посвященной 80-летию В.A. Белоногова и 70-летию В.A. Баранского (Екатеринбург, август 2015 г.), а также на X Международной алгебраической конференции в Украине, посвященной 70-летию Ю.A. Дрозда (Oдесса, август 2015 г.).

Автор выступал с докладами по теме диссертации на семинаре кафедры алгебры и системного анализа (Луганский национальный университет имени

¹¹ Fan S. Graphs whose strong endomorphism monoids are regular / S. Fan // Arch. Math. — 1999. — Vol. 73. — P. 419–421.

Тараса Шевченко, 2011–2013 гг.), семинаре «Алгебраические системы» под руководством профессора Л.Н. Шеврина (Уральский федеральный университет, октябрь 2014 г., март 2015 г., март 2016 г.).

Публикации. По результатам исследования опубликовано 15 работ: 7 научных статей и 8 тезисов докладов на научных конференциях.

Основные результаты диссертации опубликованы в []-[]. Из них статьи [], [], []-[] опубликованы в изданиях из списка, рекомендованного ВАК РФ. Статья [] является переводом статьи [].

Личный вклад автора. Диссертация является самостоятельной научной работой, которая содержит собственные идеи автора, позволившие решить поставленные задачи. Работа содержит теоретические и методические положения и выводы, сформулированные автором лично. Публикации [], [] выполнены в соавторстве с научным руководителем. Научному руководителю принадлежат постановки задач, обсуждения возможных путей решения, а также теоремы 7–8 в статье [] и теорема 4.1. в статье []. Утверждения указанных теорем на защиту не выносятся. Использованные в диссертации идеи или положения других авторов имеют соответствующие ссылки.

Структура и объем диссертации. Диссертация состоит из введения, трех разделов и списка литературы. Объем диссертации составляет 110 страниц.

Графы, гиперграфы и их эндоморфизмы

Через S1 (S) обозначают полугруппу S, если она содержит 1 (0), или, в противном случае, полугруппу S с присоединенной 1 (0).

Напомним, что моноид S называется регулярным, если для каждого его элемента а существует такой элемент 6, что а = aba (см., напр., [10]).

Полугруппы преобразований. Для любых непустых множеств X, У множество всех отображений из X в У будем обозначать через Map (X, У). Если а Є Мар(Х,У), то через im (а) будем обозначать область значений отображения а. Мощность im(a) называется рангом преобразования и обозначается через rk(a). Образ элемента х Є X при отображении а будем обозначать через ха. Ядро а будем обозначать через kera. Напомним, что kera = {(а, Ъ) Є X х X аа = Ьа}. Если X — произвольное непустое подмножество X, то через ах будем обозначать ограничение отображения а на X .

Пусть X — произвольное непустое множество. Преобразованием множества X называется всякое отображение этого множества в себя. Множество всех преобразований множества X вместе с операцией х(а(3) = (ха)(3 для всякого ж Є X, образовует полугруппу. Эта полугруппа называется симметрической полугрупппой и будет обозначаться через ЗГ(Х) или X, если Х = п. Множество всех взаимнооднозначных преобразований множества X (перестановок) называется симметрической группой и обозначается У(Х). Тождественное преобразование множества X будет обозначаться idx, а для константного преобразования с одноэлементным образом {х}, ж Є X, будем писать сх.

Отметим, что композиция отображений везде в работе осуществляется слева направо. Бинарные отношения. Под бинарным отношением на множестве X мы понимаем подмножество р декартового произведения X х X. Если а, Ь — элементы множества X и (а, Ь) Є р, то будем также писать а р Ь и говорить «а находится в отношении р с Ь». Если р и а — отношения на X, то их композиция р о а определяется следующим образом: (а, Ь) Є р о т, если существует такой элемент ж Є X, что (а, ж) Є р и (ж, Ь) Є ст. Бинарная операция «о» ассоциативна, и, таким образом, множество всех бинарных отношений является полугруппой относительно операции «о».

Отношение р на множестве X называется эквивалентностью, если оно является рефлексивным, транзитивным и симметричным. Любое отношение эквивалентности определяет разбиение множества на классы эквивалентности, которые не пересекаются. Множество таких классов называется фактор-множеством и обозначается Х/р. Через ар обозначается класс эквивалентности множества X по р, который содержит а Є X. Множество всех отношений эквивалентности на X обозначим через Eq(X).

Через %х обозначается диагональное отношение на множестве X, а через wj - универсальное отношение: гх = {{а,а) а Є X}, wx = X х X. Бинарное отношение называется тривиальным, если оно диагонально или универсально.

Отношения Грина. Левым (правым) идеалом [10] называется такое непустое подмножество А из S, что SAC A (AS С А). Двусторонним идеалом, или просто идеалом называется такое подмножество, которое является и правым, и левым идеалом.

На любой полугруппе всегда можно определить пять отношений эквивалентности ,М,Ж, 2), J, так называемые отношения Грина. Два элемента полугруппы S называются J-(M-)эквивалентными, если они порождают один и тот же главный левый (правый) идеал в S и -эквивалентными, если они порождают один и тот же главный двусторонний идеал. Композиция отношений эквивалентности J и М обозначается через 2), а их пересечение — через Ж.

Описание отношений Грина на конечной симметрической полугруппе хорошо известно (см., например, [10]): если а,/З Є &(Х) — произвольные преобразования, то aJ /3 im(a) = im(/3); а (3 кета = кет(3; аЖ/3 im (а) = im (/3) и kera = кет/3; a /3 im(a) = im(/3); Сплетение моноида с малой категорией. Говорят, что задана категория с [4], если задан класс ОЬ элементов, которые называются объектами, и для каждой пары объектов (А, В) из с задано множество Moiv(A, ), которое называется множеством морфизмов А в В. При этом 1. для любых двух морфизмов / Є Moiv(A, Б) и д Є Мог#(В,С) определена композиция морфизмов fg; 2. композиция морфизмов ассоциативна, то есть f(gh) = (fg)h для любых / Є Moiv(A, В), де Moiv(B, С), /г Є Moiv(C, D); 3. для каждого объекта А из существует тождественный морфизм id Є Moiv(A, Л) такой, что idA f = fidA = f для любого / Є Moiv(A, В); 4. множества морфизмов для разных пар объектов попарно не пересекаются. Класс элементов отличается от множества тем, что класс не может быть элементом никакого другого класса, в частности множества. Категория называется малой, если класс её объектов является множеством.

Сильные эндоморфизмы бесконечных графов выделенного класса

В этом пункте получено представление моноидов сильных эндоморфизмов бесконечных n-однородных гиперграфов, удовлетворяющих условию, аналогичному (2.1), в виде сплетения моноида группы и малой категории. Далее, подобно пункту 2.1 показано, что этот результат справедлив для некоторого подмоноида моноида сильных эндоморфизмов произвольного бесконечного п-однородного гиперграфа.

Точное представление моноидов сильных эндоморфизмов гиперграфов из одного класса. Заметим, что все определения и результаты пункта 2.2.1, кроме предложения 2.2.1, верны для произвольного (в том числе бесконечного п-однородного гиперграфа). Таким образом, для бесконечного п-однородного гиперграфа Я определены отношение 5 на V{H), канонический сильный фактор-гиперграф U, обобщенное лексикографическое произведение гиперграфов, справедлива лемма 2.2.1 и предложение 2.2.2.

Пусть С - класс всех бесконечных n-однородных гиперграфов Я, для которых при любом (р Є SEnd Я выполняется условие: V xs Є U Зу6 Є U : xsipQys. (2.6) Ясно, что класс 0 (i) совпадает с классом всех бесконечных 0-однородных (1-однородных) гипергафов. В случае, когда п 2 - натуральное, С является непустым собственным подклассом класса всех бесконечных п-однородных гиперграфов. Докажем для сильных эндоморфизмов бесконечных следующую лемму, которая является аналогом леммы 2.1.1 для графов. Лемма 2.3.1. Пусть Я = U[(Yu)ueU] - произвольный гиперграф класса п. Преобразование р гиперграфа Н будет его сильным эндоморфизмом тогда и только тогда, когда преобразование (р : U - U : х5 {x(p)s является сильным инъективным эндоморфизмом гиперграфа U. Доказательство. Пусть р Є SEnd#, ж, у Є V(Я) такие, что х6 ф у6. Если п = 0, то \Ы\ = 1 и мы немедленно получаем утверждение леммы. При п = 1 \U\ = 2. По определению сильного эндоморфизма для любого х Є V(H) если Хір Є Я(Я), то ж Є Е(Н). Следовательно, р(ж ) = 1 р(х) = 1, и таким образом, ір всегда равен idw.

Пусть п 2. Поскольку Ж( у , то без ограничения общности можем считать, что существует подмножество А С V(H), такое, что А Є ЛГ(х) и А ф Я(у). Тогда (ИиЛ) = {x(p}UA(p Є (Я), и ({x}UAtp = {X(p}UA(p І (Я), следовательно, (x(p)s ф {y(p)s. Таким образом, р инъективно. Пусть хи ..., хп Є V(H). Тогда {(жі)5,..., (xn)s} Є (Я/Я) {жь ..., хп} Є (Я) {жіу?,..., хпір} Є (Я) {(ад) ,..., (xnip)s} = {{хл)5,...,{хп)5} 8{Н/5). Таким образом, р сильный мономорфизм гиперграфа H/S. Если же для преобразования р гиперграфа Я выполняется р Є SMon Н/6, то для любых хи ..., хп Є У (Я) {жі,..., жп} Є (Я) {(жі)5,..., (жп) J Є (Я/Я) {(ж1)а,..., (xn)s}(p = {(x1p)s,..., (xnip)6} Є Є(Н/8) {х1ір,...,хпір}еЄ(Н). П Множество всех сильных инъективных эндоморфизмов гиперграфа Я образует относительно композиции преобразований полугрупппу, которую обозначим через ЭМопЯ. Элементы из ЭМопЯ будем называть сильными мономорфизмами.

Утверждение 2.3.1. Для каждого гиперграфа Я класса С справедливо равенство SEndW = SMonW. Доказательство. Пусть Я Є С. Канонический сильный фактор-гиперграф 0-однородного гиперграфа является одноэлементным 0-однородным гипергра фом, следовательно, при п = 0 имеем SEndW = SMonW. Для случая п 1 доказательство аналогично доказательству утверждения 2.1.1. Пусть Я = U[(YU)U&A] произвольный гиперграф класса С, /Ся - малая категория, определенная в пункте 2.2.2.1. Напомним, что ОЬ/Ся = {К и Є W}, Мог/Ся = \JU,VUMOTICH(YU,YV), где Mor (yu,y;) - множество отображений из Уи в Yv. Моноид SMonW естественно действует справа на множестве объектов этой категории. Таким образом, получаем следующее сплетение:

Случай произвольных n-однородных гиперграфов

Имеет место следующая лемма о существовании Jf-сечений в SEnd G. Лемма 3.1.5. Полугруппа SEndG имеет Ж-сечение тогда и только тогда, когда все классы из U мощности 2 и для любого (/3, /) Є SEnd G и всех двухэлементных классов AeU выполняется А[5 = А или \А[5\ = 1. Доказательство. Предположим, что Я - некоторое Jf-сечение полугруппы SEndG. По лемме 3.1.4 для любого А Є U выполняется \А\ 2. Пусть С = {(р Є SEnd G I G/ ker (ф) = U}. Очевидно, что для любого 7 Є С имеем 72 также из С, и im (7) = im (т2). Поэтому в пересечении Я П С будут находиться все идемпотенты из С и только они.

Предположим теперь, что для некоторого (/3, /) Є SEnd G существует такой класс А Є U, что \А\ = 2 = Л/3 иЛ А Не нарушая общности рассуждений, можем считать, что А = \А2\ = 2 и Аф = А2. Пусть А = {ашаі2}, аг произвольные фиксированные представители классов А, і Є {2,3,...,m}, тогда (апа12 А2 ... АД (idj/,p) = Є SEnd G. \ аца\2 a2 ... aTO / Рассмотрим произведение (idu,g)((3J) = (/3,/i), где АфА1 = {a2ha22} и Лг/гАг = аг/Аг Є Л/3 для всех і Є {2,3,...,m}. Таким образом, в SEndG существует Jf-класс, элементам которого соответствуют разбиение {{ац}, {ai2}, А2,...,Ат} и образ {а2Ь a22,a2fM, а3/л3, ,amfAm}. Пусть (/3,/І ) элемент указанного класса, принадлежащий Я. Тогда произведение {{3)ti)(idU)g) = \Al М " Ат Є С, \а2 a2fA2 ... amfAmJ но не является идемпотентом, т. е. не принадлежит Я. А это противоречит начальному предположению. Отметим здесь также, что из доказанного следует 7 72 для любого 7 Є SEndG. Таким образом, все элементы из Я идемпотент-ны, откуда Я С S(G). Следовательно, Я - Jf-сечение для S(G).

Наоборот, пусть все классы из U мощности 2, и для любого (/З,/) Є SEnd G и всех двухэлементных классов А є U выполняется А/3 = А или \А/3\ = 1. Согласно [52] на 3?(АІ), А{ Є U существуют и определены единственным образом Jf-сечения Яг, 1 і т. По лемме 3.1.1 прямое произведение Я: х Я2 х ... х Нт изоморфно некоторому Jf-сечению Я полугруппы S{G).

Покажем, что для любого {(3J) Є SEnd G найдется Jf-эквивалентный эле мент из S{G). Для каждого fA Є Мар(ДА/3), А є U определим сюръектив ное преобразование рАр : А/3 -+ im{fA). Рассмотрим теперь сильный эндо морфизм (idu,p) Є S(G). Нетрудно видеть, что im(i W) = im (,/). Для любого А є С/, если Л А/3, то А/3 = 1 и А П hn(/3,/) = 1, откуда А, А/З Є ker (/3, /) П ker (idu,p). Если же Л = Л/3, то рАр = рА = fA и, очевид но, ker (/А) = кет(рА). Таким образом, ker(/3J) = ker(id ,p). Следовательно, (/3, f)Jt?(idu,p) и Я является Jf-сечением для SEnd G. Из лемм 3.1.1 и 3.1.5 следует описание Jf-сечений моноида SEndG. Теорема 3.1.4. Если полугруппа SEndG имеет Ж-сечение Я, то оно единственно, причем Я #i х Я2 х ... х Нт, где Нг - Jf-сечение Т(Л), Л є С/. сечения конечной симметрической полугруппы X Как было отмечено выше, для более полного представления об Jz -сечениях моноида SEndG, необходимо ясное представление о строении -сечений симметрической полугруппы 2Гп. Отметим, что в доказательствах мы будем постоянно использовать тот факт, что произвольное Jz -сечение Sn содержит в точности одно преобразование с образом М для каждого непустого подмножества М С X.

Определения L-семейства. Понятие L-семейства играет первостепенную роль в описании Jz -сечений полугруппы , так как фактически с помощью L-семейства по образу определяется ядро преобразования, входящего в Jz -сечение.

Основное определение L-семейства. Напомним, что строгий порядок — это асимметричное и транзитивное бинарное отношение. Пусть X — непустое конечное множество и — строгий порядок на X. Определим строгий порядок - на семействе непустых подмножеств множества X следующим образом: А - В если для всех а є Л и всех Ь Є В, а Ь.

Пусть {1, 2}+ обозначает свободную полугруппу слов над алфавитом {1, 2}, через {1, 2} обозначим свободный моноид над {1, 2}, а 0 - пустое слово.

Определение 3.2.1. Пусть X конечное множество (возможно пустое) и пусть — строгий порядок на X. Индексированное семейство подмножеств {Аа}а ={1,2} множества X назовем -семейством над (X, ) если для любого а Є {1,2} : (a) А0 = X; (b) если \Аа\ 1, то Аа1 = Аа2 = 0; (c) если \Аа\ 1, то Аа1 и Аа2 непусты и Аа1 - Аа2, Аа = Аа1 U Аа2. Будем говорить, что {Аа}ае{12 -семейство над X, если {Aa}a{12} является -семейством над (X, ) для некоторого произвольного фиксированного строгого линейного порядка на X. Для простоты будем писать просто = {Ла}вместо = {Ла}аЄ{1,2},.

Напомним, что дерево — это связный граф, не содержащий циклов. Полное бинарное дерево — это дерево, в котором выделена в точности одна вершина (узел) степени 2, а все остальные вершины имеют степень 3 или 1. Вершины, степень которых равна 1, называются листьями. Каждая вершина кроме корня дерева имеет единственного родителя. Потомок вершины v — это вершина, родителем которой является узел v. Таким образом, в полном бинарном дереве каждая вершина v является либо листом, либо имеет в точности двух потомков (левого и правого).

Нетрудно видеть, что произвольное -семейство = {Аа} над непустым множеством может быть представлено в виде полного бинарного дерева Т(), вершинами которого служат множества {Аа}, а пара {Aa,A&}, а, Ъ Є {1,2} является ребром тогда и только тогда, когда а = Ы или Ь = аг, где і = 1, 2 (см. рис. 3.3). Полное бинарное дерево, представляющее -семейство, для удобства мы будем обозначать также просто вместо Г().

H -сечений моноида сильных эндоморфизмов графа

Так как (Ла, ж)а-р, ар Є Lb то (р(Аа, х)ар = ар. Последнее возможно для любых ар как (3.4), только если tp(Aa, х)\Х\Аа = idXV4a, (р(Аа,х)\Аа = сх. (ii) Пусть x,teAa,zeX\Aa.C одной стороны, (сгір(Аа,х))т = CZT = сг, и (сгт)(ір(Аа,х)т) = сг ((р(Аа,х)т), (3.5) следовательно, cz {(p{Aa,x)r) = cz . С другой стороны, (ct(p(Aa,х))т = схт = сх, и (ctT)(ip(Aa,x)T) = ct/(ip(Aa,x)T), (3.6) следовательно, се(ір(Аа,х)т) = сх1. Рассмотрим х ((р(Аа,х)т)-1 Є kerір(Аа,х)т. Для всех teAa,zeX\Aa получим cz ф сх, (так как хфх), cz,(y(Aa, х)т) = cz , сг((р(Аа,х)т) = сх . Таким образом, х,(ч (Аа,х)т)-1 = {И\іеАа}, и значит {f t Є AJ Є Х/кег(/9(Ла,ж)г. Как видно из доказательства след ствия 3.2.4, Г2 и UaGL2X/kera совпадают как семейства подмножеств множе ства X, таким образом найдется такое Ва/ Є Г2, при некотором а Є {1, 2} , что Ва, = { є AJ. В силу биективности г, получим Ла = \Ва,\. Более того, согласно (3.5) и (3.6), (( (Л, ж)г)Х\Во/ = і&Х\ва, и (у?(Ла,ж)г)Во/ = сж,, х Є Ва/. Следовательно, (Ла, х)т = р{Ва,,х ) и сх/ = схт. П Обозначим множество всех подмножеств множества X через U(X).

Лемма 3.2.11. Пусть Lx L2, ф : С/(Х) - С/(Х) : М М о амт = ам . Имеют место следующие утверждения: (і) Ла Є Г2 для любых Аа Є Гь 98 (ii) {Аа(3)ф = Ааф{(3т) для любых Аа є Г1 и /З є L1 Доказательство. (i) Понятно, что если \Аа\ = 1, то Ааф Є Г2. Пусть \Аа\ 1иа = аА Є U. Пусть для произвольного фиксированного элемента UJ JTLa 1 XeAa (р(Аа,х)т = (р(ВаЧх ), где Ба/ Є Г2, х Є Ба/ и Ла = Ба/. Поскольку а(р{Аа,х) = сж, получим (ат)р(Ва/,ж ) = сж/, следовательно, im (аг) С Ва/. Предположим, что rk (а) rk (ar) и обозначим через /3 преобразование из L2 такое, что im (/Г) = Ва/.

Пусть (JeL1 преобразование, с образом im (6) С Аа. Точно также как в лемме 3.2.5, (iv) можно показать, что существует 7 Є Ь1, у которого im (7U ) = im(). Обозначим это преобразование . Таким образом, для всех 6 Є U у которых im () С Ла, найдется 7е5 Є L1 такое, что

Пусть /3 = /3V"1. Поскольку p ip(Ba4x ) = с, получим (/3 р(Д» ,ж ))т-1 = (Ла,ж) = сж, следовательно im (/3) С Ла. Таким образом, /3 = аб 3, откуда /3 = (ar)( r).Но rk (/З ) = rk ((ar)( r)) rk (ar) rk (a). Полученное противоречие доказывает, что rk(a) = rk (ar). Следовательно, im(ar) = \Aa\ = \Bal\ и im (ar) С Ва, откуда im (ar) = Bal. Таким образом, OLAT = aBa/, следовательно, Ааф = Ba/ є Г2. (ii) Предположим, что Ла Є Г1 и /З Є L1. Пусть aAr = аВа, Ва Є Г2. Обозначим [5т через /3 . Тогда {аАаР)т = {aAJ)r = {аВа/)/3 = аАаф(3 = а(Ааф)рі) что, по определению ф, означает (Аа/3)ф = Ааф(/3т). П Следствие 3.2.5. Пусть L1 L2, ф - функция из леммы 3.2.11. Тогда для всех Аа,АьеТ1: (i) Aa = \Ааф\; (ii) если Aa С Аъ, то Ааф С Ль ; (iii) если ЛаПЛ = 0, то Ааф П А = 0 99 Доказательство. (і) Пусть Аа Є Гь х Є Аа, и ( р(Аа,х))т = {Ва/)х ) для некоторых Ва, Є Г2, ж Є Ва , при этом Ла = \Ва \ (см. лемму 3.2.10, (И)). Из доказательства леммы 3.2.11, (і) следует, что Ааф = Ва/. Таким образом, \Аа\ = \Ааф\. (ii) Пусть Аа С Аь и z Є Аь - произвольный фиксированный элемент. Предположим, что ((p(Ab, z))r = if {By, z ) для некоторых By Є Г2, z Є By. По лемме 3.2.10, (ii), czr = cz , следовательно, {z} = {z }. С одной стороны, (Aa(p(Ayz))i/j = {z}4 = {zf}. С другой стороны, по лемме 3.2.11, (ii), (Aaip(Ayz))i/j = (Aai/j)(ip(Ayz)T) = (Ааф)ір(Ву,/). Следовательно, (Д МДлО = М, откуда Ла С By = Аьф. (ііі) Пусть АаГ\Аь = 0. Зафиксируем z Є Ab и пусть (р(Аь, z))r = (p(Bv, z ) для подходящих By Є Г2, У Є БЬ/. Предположим у Є Аа - произвольный элемент, и сут = Су . По определению тогда получим {у}ф = {у }- С одной стороны, (у р(Аъ, г))ф = {у}ф = {у }, где у ф z . С другой стороны, по лемме 3.2.11, (ii), ({y}ip(Ayz))i/j = ({у}іІ )( р(Аь,г)т) = {y }ip(By,z ). Таким образом, у (р(Ву} z ) = у , у ф z для всех у Є Аа. Следовательно, {у1 су = сут, уеАа}П Аьф = {у су = сут, у Є Аа} П By = 0. Согласно пункту (ii) этого следствия {у } = {у}ф С Ааф. Поскольку т биективно, получим \Аа\ = \у\с = СуТ, уеАа}\. Согласно (і) имеет место \Аа\ = \Аа ф\, следовательно, Ааф = {у \ су = сут} у Є Аа}. Таким образом, Ааф П Аьф = 0. Теперь мы можем доказать следующую лемму. Лемма 3.2.12. Если Lx L2, то Г і Г2.

Доказательство. Понятно, что лемма справедлива при \Х\ = 1. Предположим, что \Х\ 2. Рассмотрим ограничение функции ф из леммы 3.2.11 на Гі (которое мы также будем обозначать через ф). Согласно (i) леммы 3.2.11, ф : Гі - Г2. Нетрудно видеть из следствия 3.2.5, что либо Ахф = Вх и А2ф = Б2, либо Ахф = В2 и А2ф = Вх. Предположим, что Ахф = Вх и А2ф = В2. Докажем индукцией по \а\, что для всех а Є {1,2} , Ааф = Ва. Мы уже знаем, что это так для \а\ = 1. Пусть к 1 и предположим, что Ааф = Ва для всех а Є {1,2} при \а\ /с. Пусть &г Є {1,2} , &г = к и Аы є Гь Как было показано в лемме 3.2.5, существует преобразование 7 Є Ьі такое, что Аъ1 = Аы, т.е., 7л = а .. По определению 3.2.5,