Напівгрупи часткових автоморфізмів кореневих дерев

Размещено на http://www.allbest.ru/

КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

ІМЕНІ ТАРАСА ШЕВЧЕНКА

УДК 512.53

01.01.06 -- алгебра і теорія чисел

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

НАПІВГРУПИ ЧАСТКОВИХ АВТОМОРФІЗМІВ КОРЕНЕВИХ ДЕРЕВ

Кочубінська Євгенія Анатоліївна

Київ - 2008



Дисертацією є рукопис.

Роботу виконано на кафедрі алгебри та математичної логіки Київського національного університету імені Тараса Шевченка.

Науковий керівник: кандидат фізико-математичних наук, доцент ГАНЮШКІН Олександр Григорович. Київський національний університет Імені Тараса Шевченка, Доцент кафедри алгебри і математичної логіки

Офіційні опоненти: доктор фізико-математичних наук, професор Новіков Борис Володимирович, Харківський національний університет імені В.Н.Каразіна, провідний науковий співробітник кафедри теорії функцій та функціонального аналізу

кандидат фізико-математичних наук ІШУК Юрій Богданович, Львівський національний університет імені Івана Франка доцент кафедри алгебри і логіки

Захист відбудеться “21” квітня 2008 р. о 14 годині на засіданні спеціалізованої вченої ради Д 26.001.18 при Київському національному університеті імені Тараса Шевченка (03022, м. Киів-22, пр-т Глушкова, 6, механіко-математичний факультет).

З дисертацією можна ознайомитись в бібліотеці Київського національного університету імені Тараса Шевченка за адресою: м. Київ, вул. Володимирська, 58.

Автореферат розіслано “17” березня 2008 р.

Вчений секретар спеціалізованої вченої ради Плахотник В.В.



ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Дисертаційну роботу присвячено дослідженню напівгруп часткових автоморфізмів кореневих регулярних дерев. Таким чином, робота є дослідженням у галузі теорії напівгруп.

Одна з основних тенденцій у теорії напівгруп, яка склалася останніми десятиріччями, - це вивчення математичних об'єктів (зокрема, графів) через призму певних напівгруп, які пов'язані з цими об'єктами спеціальним чином.

У теорії груп останніми роками помітний інтерес до груп автоморфізмів дерев. Однією з причин інтересу до груп, що діють на деревах, є те, що різноманітні цікаві приклади груп природним чином зображуються перетвореннями кореневих дерев, наприклад, нескінченні скінченно породжені періодичні групи, групи скінченного росту, фрактальні групи, гіллясті групи.

Але ще у піонерських дослідженнях Р. ФрухтаFrucht R. Herstellung von Graphen mit vorgegebener abstrakter Gruppe // Compos. Math. -- 1938. -- Vol. 6. -- P. 239-250, а згодом і деяких інших авторів (наприклад, СабідуссіSabidussi G. Graphs with given group and given graph-theoretical properties // Canad. J. Math. -- 1957. -- Vol. 9. -- P. 515-525., ІзбіцкіIzbicki H. Unendliche Graphen endlichen Grades mit vorgegebenen Eigenschaften. // Monatsh. Math. -- 1959. -- Vol. 63. -- P. 298-301.) показано, що група автоморфізмів графа містить далеко не повну інформацію про граф. У той самий час деякі напівгрупи перетворень визначають граф, пов'язаний з ними, досить добре. Оскільки майже завжди група автоморфізмів певного об'єкту міститься в напівгрупі деяких часткових відображень, що діють на цьому ж об'єкті, то, звичайно, напівгрупа перетворень несе більше інформації, пов'язаної з об'єктом, у порівнянні з його групою автоморфізмів. Тому вивчення напівгруп перетворень різноманітних графів, зокрема, дерев, є актуальною проблемою для теорії напівгруп.

Дослідженню напівгруп перетворень графів присвячено значну кількість робіт. У статті В. МолчановаMolchanov V. A. Semigroups of mappings on graphs // Semigroup Forum -- 1983. -- Vol. 27 -- P. 155-199 подано вичерпний огляд робіт, присвячених напівгрупам різноманітних перетворень графів, які були опубліковані до 80-х рр. минулого сторіччя. К. МаксономMaxson C. J. Semigroups of order-preserving partial endomorphisms on trees // Colloq. Math. -- 1974. -- Vol. 32. -- P. 25-37 досліджувалася напівгрупа часткових ендоморфізмів дерев, які зберігають порядок. Серед більш пізніх робіт у цьому напрямку відзначимо наступні роботи, які дуже близькі до теми наших досліджень. В. МолчановимMolchanov V. A. Concrete characterization of partial endomorphisms semigroups on graphs // Acta Sci. Math. -- 1987. -- Vol. 51. -- P. 349-363 досліджувалося питання конкретної характеризації напівгрупи часткових ендоморфізмів графа. Напівгрупи ендоморфізмів графів, які понижують порядок, вивчалися в роботі А. ВерницькогоVernitskii A. Semigroups of order-decreasing graph endomorphisms // Semigroup Forum -- 1999. -- Vol. 58. -- P. 222-240. У роботі П. Катаріно та П. Хігінса Catarino P. M., Higgins P. M. The monoid of orientation-preserving mappings on a chain // Semigroup Forum -- 1999 -- Vol. 58, № 2. -- P. 190-206 було досліджено моноїд таких відображень ланцюга, які зберігають орієнтацію.

Оскільки на відміну від довільного графа, дерево “гарно влаштоване”, то й інформація про дерево, яку можна отримати, знаючи властивості його напівгрупи часткових перетворень, може виявитися більш цікавою. Також, враховуючи структуру дерева, деякі напівгрупові властивості можна описати більш докладно, ніж у випадку довільного графа.

Наведений вище короткий огляд показує, що вивчення напівгруп перетворень дерев є актуальною проблемою для теорії напівгруп перетворень. Характеристика напівгруп перетворень графа, з одного боку, може бути отримана з характеристики самого графа. У випадку дерева ця інформація може бути прозоро описана. З іншого боку, з характеристик напівгрупи перетворень можна отримати певні характеристики самого дерева. Результати такого роду можуть бути використані як для класифікації та вивчення властивостей графа, так і для більш глибокого дослідження напівгруп перетворень дерева. Про актуальність теми дисертаційної роботи свідчить також і те, що кількість робіт, присвячених напівгрупам перетворень дерев, постійно зростає.

Зв'язок роботи з науковими програмами, планами, темами.

Дисертаційну роботу виконано в рамках держбюджетної дослідницької теми № 06БФ038 “Розробка алгебраїчних та геометричних методів дослідження з використанням комбінаторних та категорних підходів”, що виконується на кафедрі алгебри та математичної логіки механіко-математичного факультету Київського Національного університету імені Тараса Шевченка (номер державної реєстрації 0106U005862).

Мета і задачі дослідження.

Метою дисертаційної роботи є:

описати властивості напівгрупи часткових автоморфізмів кореневих дерев;

описати властивості піднапівгруп напівгрупи ;

описати підстановочні зображення піднапівгруп напівгрупи ;

дослідити зв'язок часткового вінцевого добутку інверсних симетричних напівгруп з напівгрупою ;

описати зрізи відношень Гріна часткового вінцевого степеню інверсної симетричної напівгрупи та дати їхню класифікацію з точністю до ізоморфізму. автоморфізм кореневий грін вінцевий

Методика дослідження.

У дисертаційній роботі використовуються методи теорії напівгруп та теорії груп.

Наукова новизна одержаних результатів.

У дисертаційній роботі отримано такі нові результати:

запропоноване узагальнення біциклічної напівгрупи та описано його властивості;

описано підстановочні зображення узагальненої біциклічної напівгрупи;

введено узагальнення часткового вінцевого добутку;

означено напівгрупу ConPAutT таких часткових автоморфізмів дерева T, які не рухають кореневу вершину, й область визначення яких є зв'язним графом та описано замкнені інверсні піднапівгрупи напівгрупи ConPAutT;

описано зображення напівгрупи ConPAutT частковими підстановками;

дано абстрактну характеризацію напівгрупи ConPAutT;

описано зрізи часткового вінцевого степеня інверсної симетричної напівгрупи ISn.

Практичне значення отриманих результатів.

Результати роботи мають теоретичний характер і є певним внеском у теорію напівгруп часткових перетворень. Вони можуть бути використані при подальшому вивченні напівгруп часткових перетворень різних алгебро-комбінаторних об'єктів та в спецкурсах з теорії напівгруп.

Особистий внесок здобувача.

Усі результати отримано автором особисто.

Апробація результатів дисертації.

Результати дисертаційної роботи доповідалися на засіданнях семінару з теорії груп та напівгруп при кафедрі алгебри та математичної логіки механіко-математичного факультету Київського національного університету імені Тараса Шевченка (Київ, 2003-2006), на засіданні Київського алгебраїчного семінару (Київ, 2007), на X Міжнародній конференції імені академіка М. Кравчука (Київ, 2004), на V Міжнародній алгебраїчній конференції в Україні (Одеса, 2005), на XI Міжнародній конференції імені академіка М. Кравчука (Київ, 2006), на VI Чесько-Словацькому міжнародному симпозіумі з комбінаторики, теорії графів, алгоритмів та їхніх застосувань (Прага, Чехія, 2006), на Міжнародній конференції з радикалів ICOR-2006 (Київ, 2006), на VI Міжнародній алгебраїчній конференції в Україні (Кам'янець-Подільський, 2007).

Публікації.

За результатами дисертаційної роботи опубліковано 5 статей у фахових виданнях [1-5] та 6 тез [6-11] доповідей на конференціях.

Структура та обсяг дисертації.

Дисертація складається із вступу, чотирьох розділів, висновків та списку використаних джерел. Повний обсяг дисертації становить 126 сторінок, список використаних джерел займає 7 сторінок і містить 61 найменування.

ОСНОВНИЙ ЗМІСТ

У вступі сформульовано мету та задачі дисертаційної роботи, викладено основні результати дослідження.

Перший розділ містить короткий історичний огляд літератури за тематикою дисертації та висвітлює сучасний стан вивчення проблем, схожих до тих, що розглядаються в дисертаційній роботі.

Другий розділ носить базовий та систематизуючий характер і містить необхідні означення та деякі твердження з теорії напівгруп, які використовуються в роботі.

У підрозділі 2.1 наводяться основні поняття теорії напівгруп, такі, як поняття інверсної напівгрупи, головних ідеалів напівгрупи, відношень Гріна.

У підрозділі 2.2 означено частковий вінцевий добуток довільної напівгрупи S з напівгрупою P часткових перетворень деякої множини.

Нехай S -- напівгрупа, ConPAutT -- напівгрупа часткових перетворень множини X. Визначимо множину SPX як множину часткових функцій з множини X у напівгрупу S:

Якщо, то добуток fg визначається наступним чином:

Якщо, то fa визначається таким чином:

Частковим вінцевим добутком напівгрупи S з напівгрупою (P,X) часткових перетворень множини X називається множина

з операцією множення

Частковий вінцевий добуток напівгруп S і (P,X) будемо позначати.

Частковий вінцевий добуток напівгруп відносно так введеної операції множення є напівгрупою. Частковий вінцевий добуток інверсних напівгруп є інверсною напівгрупою.

Підрозділ 2.3 містить означення інверсної симетричної напівгрупи IS(X). Для множини X через IS(X) позначимо множину усіх часткових бієкцій множиниX. На множині IS(X) задається операція множення

Множина IS(X) є напівгрупою, яка називається інверсною симетричною напівгрупою на множині X. Якщо, де, то напівгрупа називається інверсною симетричною напівгрупою рангу , позначається ISn.

Для інверсної симетричної напівгрупи рангу наведено означення ланцюгового розкладу елементів, а також наведено характеризацію відношень Гріна на цій напівгрупі.

У підрозділі 2.4 розглянуто напівгрупу PF паралельних зсувів.

Нехай -- вільний моноїд над алфавітом F.

Розглянемо множину. На цій множині введемо операцію множення наступним чином:

Доведено, що напівгрупа PF є інверсною, описано головні праві та ліві ідеали цієї напівгрупи. Основними результатами цього підрозділу є твердження 2.14 та теорема 2.16.

Твердження 2.14. Нехай, ,. Тоді

aLb тоді і лише тоді, коли;

aRbтоді і лише тоді, коли;

aHb тоді і лише тоді, коли і;

aDb для довільних ненульових;J=D.

Теорема 2.16. Напівгрупа PF є 0-простою.

У третьому розділі дисертаційної роботи розглянуто напівгрупу PAutT часткових автоморфізмів кореневого дерева, тобто таких часткових ін'єктивних відображень, що підграфи, породжені областю визначення та областю значення, є ізоморфними. У підрозділі 3.1 описані деякі загальні властивості цієї напівгрупи. Зокрема, показано, що напівгрупа PAutT є інверсною та описано відношення Гріна на ній.

Теорема 3.4. Нехай. Тоді

fRgтоді і лише тоді, коли dom(f)=dom(g);

fLgтоді і лише тоді, коли ran(f)=ran(g);

fHg тоді і лише тоді, коли dom(f)=dom(g) та ran(f)=ran(g);

fDg тоді і лише тоді, коли.

Твердження 3.5. Нехай. Тоді fJg тоді і лише тоді, коли dom(f) містить підграф, ізоморфнийdom(g), та dom(g) містить підграф, ізоморфний dom(f).

У підрозділі 3.2 введено узагальнення відомої біциклічної напівгрупи.

Нехай T - кореневе n-регулярне дерево з коренем, AutT -- його група автоморфізмів. Зафіксуємо вершину першого рівня V1 і розглянемо деякий частковий автоморфізм: дерева на кореневе піддерево. Для кожної вершини першого рівня зафіксуємо частковий автоморфізм дерева на кореневе піддерево. Інверсну піднапівгрупу напівгрупи PAutT, породжену відображенням a та групою AutT, позначимо B(n), а інверсну піднапівгрупу, породжену множиною, позначимо B[n]. Для спрощення замість писатимемо просто. Зауважимо, що у випадку, коли є нескінченним променем, напівгрупи B(n) та B[n] збігаються з класичною біциклічною напівгрупою, тому їх можна розглядати як узагальнення біциклічної напівгрупи.

У пункті 3.2.1 вивчаються загальні властивості напівгруп B(n) та B[n]. Описано канонічний вигляд елементів напівгруп B(n) та .

Лема 3.8. Для довільного ненульового область визначення та образ є кореневими піддеревами дерева.

Надалі через root (x) будемо позначати корінь області визначення елемента B(n) ( B[n]).

Твердження 3.10. 1. Кожний ненульовий елемент напівгрупи B(n) можна зобразити як, де. Якщо два зображення задають один і той самий елемент напівгрупи B(n), то та,.

2. Кожний ненульовий елемент напівгрупи B[n] можна єдиним чином зобразити у вигляді, де .

Також для B(n) та B[n] досліджено стандартні теоретико-напівгрупові питання: відношення Гріна, вигляд ідемпотентів.

Твердження 3.20. Напівгрупи B(n) і B[n] є 0-простими.

Теорема 3.21 .2. У напівгрупах B(n) та B[n] немає нетривіальних конгруенцій.

У пункті 3.2.2 вивчено підстановочні зображення узагальненої біциклічної напівгрупи B(n).

На інверсній напівгрупі S вводиться відношення природного часткового порядку Замиканням множини називається множина. Якщо, то множина H називається замкненою.

Нехай H -- замкнена інверсна піднапівгрупа інверсної напівгрупи S. На множині елементів напівгрупи S розглянемо відношення Це відношення є головною частковою правою конгруенцією.Надалі класи часткової правої конгруенції називатимемо правими -класами за замкненою інверсною піднапівгрупою H.

Підстановочним зображенням інверсної напівгрупи S називається довільний її гомоморфізм в інверсну симетричну напівгрупу на множині X. Нехай K -- замкнена інверсна піднапівгрупа інверсної напівгрупи S, головна часткова права конгруенція, яка визначена за допомогою K, X -- множина правих класів за K. Розглянемо зображення інверсної напівгрупи S частковими підстановками множини X, де дія визначається правилом: для і . Це зображення називається зображенням напівгрупи S на правих класах за замкненою інверсною піднапівгрупою K. Б. ШайномШайн Б. М. Представления обобщенных групп // Изв. вузов. Математика. -- 1962. -- 28, № 3. -- С. 164-176. доведено, що кожне ефективне транзитивне зображення інверсної напівгрупи S еквівалентне зображенню напівгрупи на множині правих класів за деякою замкненою інверсною піднапівгрупою. Тому опис усіх замкнених інверсних піднапівгруп інверсної напівгрупи є важливим.

Основним результатом пункту 3.2.2 є теорема 3.24.

Через Ni позначено множину{1,2,…i}. Нехай Ek ={0,e1, …, ek}, де,. Множина Ek є інверсною напівгрупою, кожний елемент якої є ідемпотентом.

Теорема 3.24. Кожна замкнена інверсна піднапівгрупа K узагальненої біциклічної напівгрупи, множина E(K) ідемпотентів якої містить найменший ідемпотент, корінь області визначення якого належить k-му рівню, ізоморфна напівгрупі, де.

Напівгрупа, де -- підгрупа групи, ізоморфна замкненій інверсній піднапівгрупі напівгрупи, яка містить найменший ідемпотент e, такий, що.

У підрозділі 3.3 введено напівгрупу ConPAutT всіх часткових автоморфізмів кореневого дерева, область визначення яких є зв'язною та містить кореневу вершину.

Твердження 3.30

Кожне з відношень Гріна R-, L- або H на напівгрупі ConPAutT є перетином відповідного відношення Гріна на PAutT з.

У підрозділі 3.4 вивчається зображення напівгрупи ConPAutT частковими підстановками.

Якщо потрібно підкреслити, що група (напівгрупа) H діє на множині M, то позначатимемо це як (H,M).

Узагальненим частковим вінцевим добутком групи (напівгрупи) (H,M) з набором напівгруп називається множина

з операцією множення

Основним результатом підрозділу 3.4 є теорема 3.34.

Теорема 3.34. Довільна замкнена інверсна піднапівгрупа K напівгрупи ConPAutT ізоморфна узагальненому частковому вінцевому добутку

де Г -- область визначення найменшого ідемпотента напівгрупи K,.

У пункті 3.4.2 знайдено умови еквівалентності ефективних транзитивних зображень напівгрупи ConPAutT.

Теорема 3.36. Нехай

є замкненими інверсними піднапівгрупами напівгрупи ConPAutT. Два зображення та напівгрупи ConPAutT на множині правих -класів за замкненими інверсними піднапівгрупами K1 і K2 еквівалентні тоді і лише тоді, коли H1 і H2 подібні, тобто існують ізоморфізми та, такі, що для довільних,.

У пункті 3.4.3 розглянуто точні зображення напівгрупи ConPAutT.

Теорема 3.38. Нехай T -- кореневе -регулярне k-рівневе дерево. Якщо k>1, то напівгрупа ConPAutT точного ефективного транзитивного зображення не має. Якщо k=1, то точне ефективне транзитивне зображення напівгрупи ConPAutT еквівалентне стандартному зображенню напівгрупи ISn частковими підстановками на множині {1,2,…,n}.

У підрозділі 3.5 дається абстрактна характеризація напівгрупи часткових автоморфізмів дерева ConPAutT.

Теорема 3.47. Нехай S -- скінченна інверсна напівгрупа з одиницею, L-- решітка ідемпотентів напівгрупи S відносно природного часткового порядку, P -- множина нерозкладних в об'єднання елементів решітки L, PIAutP-- напівгрупа таких часткових автоморфізмів частково впорядкованої множиниP, області визначення і значення яких є непорожніми порядковими ідеалами. Нехай відображення задане наступним чином:, де,.

Скінченна інверсна напівгрупа S ізоморфна напівгрупі часткових автоморфізмів деякого скінченного кореневого дерева тоді і лише тоді, коли решітка E(S) ідемпотентів напівгрупи S дистрибутивна, P-- порядковий ідеал решітки L і -- ізоморфізм.

У четвертому розділі розглядається частковий вінцевий степінь інверсної симетричної напівгрупи ISn. Вважаємо, що.

Частковим вінцевим k-м степенем напівгрупи ISn називається напівгрупа

з операцією множення

де, -- частковий вінцевий (k-1)-й степінь напівгрупи ISn .

Основним пунктом підрозділу 4.1 є теорема 4.2.

Теорема 4.2. Нехай T -- кореневе n-регулярне k-рівневе дерево. Тоді

Твердження 4.3. Елемент є ідемпотентом тоді і лише тоді, коли і.

Встановлено також необхідні й достатні умови того, щоб елемент напівгрупи був нільпотентним.

У теоремі 4.6 дано опис відношень Гріна вінцевого добутку.

Теорема 4.6. Нехай -- скінченна інверсна напівгрупа,. Тоді

(f,a) L (g,b) тоді і лише тоді, коли ran(a)=ran(b) і для довільного , де - інверсний до;

(f,a) R (g,b) тоді і лише тоді, коли dom(a)=dom(b) і для довільного f(z) R g(z);

(f,a) H (g,b) тоді і лише тоді, коли ran(a)=ran(b) і dom(a)=dom(b), та для і f(z) R g(z) для;

(f,a) D (g,b) тоді і лише тоді, коли rank(a)=rank(b) і існує відображення, що для всіх. J=D.

Твердження 4.9. Нехай S -- максимальна нільпотентна піднапівгрупа напівгрупи ISn. Тоді є максимальною нільпотентною піднапівгрупою напівгрупи. Будь-яка максимальна нільпотентна напівгрупа має такий вигляд.

Підрозділ 4.2 містить комбінаторні результати, що стосуються напівгрупи.

Для довільної функції F позначимо.

Твердження 4.10., де.

Твердження 4.11. Нехай - множина ідемпотентів напівгрупи. Тоді, де.

Також у цьому підрозділі вивчено комбінаторику відношень Гріна напівгрупи. Зокрема, знайдено кількість D-класів.

Твердження 4.12. Кількість D-класів напівгрупи дорівнює Pk(1), де.

Нехай Г - деяке піддерево n-регулярного k-рівневого дереваT, яке містить кореневу вершину дерева T , -- стабілізатор піддерева Г.

Твердження 4.14. Потужність множини E(DГ) ідемпотентів класу DГ дорівнює

Наслідок 4.15. Кількості R- і L- класів, що містяться у D-класі DГ, однакові і дорівнюють

У підрозділі 4.3 описано H-, R- та L-зрізи напівгрупи. У пункті 4.3.1 зібрано відомі результати про зрізи напівгрупи ISn.

Нехай -- відношення еквівалентності на напівгрупі S. Піднапівгрупа T називається зрізом відношення, якщо T містить точно по одному елементу з кожного класу еквівалентності. Зрізи R-, L-, H- відношень Гріна називаються R-, L-, H- зрізами відповідно. Пункт 4.3.2 містить опис зрізів напівгрупи. Основними результатами цього пункту є твердження 4.22 та теореми 4.28 і4.29.

Для опису R- та L-зрізів нам знадобляться деякі позначення. Нехай - диз'юнктне розбиття множини Nn. Для набору визначимо відображення

так: ставить у відповідність добутку такий елемент, що.

Твердження 4.22. Напівгрупа не містить H-зрізів.

Теорема 4.28.Нехай R0--R-зріз напівгрупи ISn, R1,…, Rk-- -зрізи напівгрупи ISm. Тоді

R-зріз напівгрупи.

Більше того, кожний R-зріз напівгрупи ізоморфний R-зрізові вигляду

Оскільки відображення напівгрупи є антиізоморфізмом, що відображає R-класи на L-класи, то L-зрізи описуються аналогічно (Теорема 4.29)).

Наслідок 4.30. Напівгрупа містить

різних R- (L- зрізів.

Теорема 4.32 та аналогічна їй теорема 4.33 дають змогу для довільного k одержати всі R- та L-зрізи k-го часткового вінцевого степеня напівгрупи ISn.

Теорема 4.32. Нехай - R-зріз напівгрупи ISn, R1 , …, Rk - R -зрізи інверсної напівгрупи S. Тоді -R-зріз напівгрупи.

Більше того, кожний R-зріз напівгрупи ізоморфний

В пункті 4.3.3 показано, що кожний ізоморфізм R- (L-) зрізів є подібністю. Основним результатом є теорема 4.35.

Теорема 4.35. Нехай R1, R2 --R-зрізи напівгрупи ISn, -- ізоморфізм. Тоді існує елемент, такий, що для довільних і виконується рівність.

В пункті 4.3.4 отримано аналогічне твердження щодо ізоморфності R- (L-) зрізів напівгрупи.

Теорема 4.37. Нехай R',R” -- R-зрізи напівгрупи, -- ізоморфізм. Тоді існує такий елемент, що

Іншими словами, якщо і, то і для будь-якого



ВИСНОВКИ

У дисертації отримано нові наукові результати з теорії напівгруп часткових перетворень. Зокрема, досліджено напівгрупу часткових автоморфізмів кореневого -регулярного дерева, введено та досліджено узагальнену біциклічну напівгрупу, досліджено властивості часткового вінцевого степеня інверсної симетричної напівгрупи . Основними результатами є наступні:

описано властивості узагальнених біциклічних напівгруп;

описано підстановочні зображення узагальненої біциклічної напівгрупи;

описано зображення напівгрупи ConPAutT частковими підстановками;

дано абстрактну характеризацію напівгрупи ConPAutT;

описано зрізи часткового вінцевого добутку інверсних напівгруп;

дано класифікацію R- та L-зрізів часткового вінцевого добутку інверсних симетричних напівгруп з точністю до ізоморфізму.

Автор дисертації висловлює щиру подяку своєму науковому керівнику, доценту Ганюшкіну Олександру Григоровичу за постановку розглянутих у дисертаційній роботі задач, цінні поради і постійну увагу до роботи.



СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Кочубінська Є. А. Про одне узагальнення біциклічної напівгрупи // Вісник Київського університету. Серія: фіз.-мат. науки. -- 2004. -- № 4.-- С. 24-30.

2. Кочубінська Є. А. Абстрактна характеризація напівгрупи часткових автоморфізмів кореневого дерева // Вісник Київського університету. Серія: фіз.-мат. науки. -- 2007. -- № 1. -- С. 14-16.

3. Кочубінська Є. А. Підстановкові зображення напівгрупи часткових автоморфізмів кореневого дерева // Вісник Київського університету. Математика. Механіка. -- 2007. -- № 17-18. -- С. 33-37.

4. Kochubinska Ye. Combinatorics of partial wreath power of finite inverse symmetric semigroup // Algebra and Discrete Mathematics. -- 2007. -- no. 1. -- P. 49-60.

5. Kochubinska Ye. On cross-sections of partial wreath product of inverse semigroups // Electron. Notes Discrete Math. -- 2007. -- Vol. 28. -- P. 379-386.

6. Кочубінська Є. А. Про одне узагальнення біциклічної напівгрупи // Матеріали X міжнародної конференції ім. акад. М.Кравчука, Київ, 13-15 травня, 2004.-- К.: ТОВ “Задруга”, 2004. -- С. 421.

7. Kochubinska Ye. Combinatorics of partial wreath power of full inverse symmetric semigroup // Abstracts of 5th International Algebraic Conference in Ukraine, Odessa, July 20-27, 2005. -- Одес. нац. ун-т ім. І.Мечнікова, 2005.-- P. 100-101.

8. Кочубінська Є. А. Абстрактна характеризація напівгрупи часткових автоморфізмів кореневого дерева // Матеріали XI міжнародної конференції ім. акад. М.Кравчука, Київ, 18-20 травня, 2006.-- К.: ТОВ “Задруга”, 2006. -- С. 473.

9. Kochubinska Ye. On cross-sections of partial wreath product of inverse semigroups // Abstracts of Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague, July 10-15, 2006. -- Prague: ITI Series, 2006. -- P. 75.

10. Kochubinska Ye. On - and -cross-sections of partial wreath square of finite inverse symmetric semigroup // Abstracts of International Conference on Radicals ICOR-2006, Kyiv, July 30- August 5, 2006.-- K.: Київ. нац. ун-т ім. Т.Шевченка, 2006.-- P. 43-44.

11. Kochubinska Ye. On isomorphisms of cross-sections of inverse semigroups // Abstracts of 6th International Algebraic Conference in Ukraine, Kamyanets-Podilsky, July 1-7, 2007.-- 2007.-- P. 103-104.



АНОТАЦІЯ

Кочубінська Є.А. Напівгрупи часткових автоморфізмів кореневих дерев -- Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.01.06 -- алгебра і теорія чисел. -- Київський національний університет імені Тараса Шевченка, Київ, 2008.

Дисертаційну роботу присвячено дослідженню напівгруп часткових автоморфізмів кореневих дерев. Введено нові узагальнення біциклічної напівгрупи, досліджено їхні властивості, побудовано підстановочні зображення цих напівгруп на множині правих -класів за замкненими інверсними піднапівгрупами. Розглянуто напівгрупу ConPAutT таких часткових автоморфізмів дерева T, які не рухають кореневу вершину, і область визначення яких є зв'язним графом. Досліджено властивості цієї напівгрупи, отримано підстановочні зображення на множині правих -класів за замкненими інверсними піднапівгрупами, для опису яких введено узагальнення часткового вінцевого добутку напівгруп перетворень, отримано абстрактну характеризацію напівгрупи ConPAutT.

Показано, що у випадку скінченного регулярного дерева T напівгрупа ConPAutT ізоморфна частковому вінцевому степеню інверсної симетричної напівгрупи ISn. Дослідженню властивостей часткового вінцевого добутку напівгрупи ISn присвячено окремий розділ. Отримано комбінаторні результати для часткового вінцевого степеню напівгрупи ISn. Отримано опис R- та L-зрізів часткового вінцевого добутку та одержано класифікацію зрізів з точністю до ізоморфізму. Показано, що напівгрупа не містить H-зрізів.

Ключові слова: кореневе регулярне дерево, частковий автоморфізм, інверсна напівгрупа, частковий вінцевий добуток, зрізи відношень Гріна.



АННОТАЦИЯ

Кочубинская Е.А. Полугруппы частичных автоморфизмов корневых деревьев. -- Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.01.06 -- алгебра и теория чисел -- Киевский национальный университет имени Тараса Шевченко, Киев, 2008.

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

Во введении обоснована актуальность работы, определены предмет, цель и задачи исследования; указаны методы, научная новизна, теоретическое и практическое значение исследования, описаны личный вклад соискателя, апробация полученных результатов, структура диссертации.

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

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

Третий раздел посвящен полугруппам частичных автоморфизмов бесконечных корневых деревьев. Рассмотрена полугруппа PAutT частичных автоморфизмов корневого дерева, то есть таких частичных инъективных отображения , что подграфы, порожденные областью определения и областью значения , изоморфны. Показано, что эта полугруппа является инверсной, описаны отношения Грина на этой полугруппе.

Введены обобщенные бициклические полугруппы. Изучены стандартные теоретико-полугрупповые вопросы: характеризация отношений Грина, канонический вид элементов, вид идемпотентов этих полугрупп. Построены представления этих полугрупп на множестве правых -классов по замкнутым инверсным подполугруппам.

Исследована полугруппа ConPAutT таких частичных автоморфизмов дерева T, область определения которых является связным графом, и которые не двигают корневую вершину. Для этой полугруппы описаны подстановочные представления на множестве правых -классов по замкнутым инверсным полугруппам, для описания строения которых было введено обобщение частичного сплетения полугрупп. Установлено, при каких условиях два представления на множестве -классов по замкнутым инверсным полугруппам будут изоморфны. Показано, что полугруппа ConPAutT частичных автоморфизмов k-уровневого корневого дерева не имеет точного эффективного транзитивного представления при k>1. В случае k=1 точное эффективное представление полугруппы ConPAutT эквивалентно стандартному представлению полугруппы ISn на множестве {1,2,…,n}. Дана абстрактная характеризация полугруппы ConPAutT.

В четвертом разделе рассматривается частичное сплетение инверсной симметричной полугруппы ISn. Показано, что в случае конечного дерева T полугруппа ConPAutT изоморфна сплетению конечного числа копий инверсной симметричной полугруппы ISn. Исследованы свойства частичного сплетения полугрупп ISn. Получены комбинаторные результаты: найдено количество элементов полугруппы , количество идемпотентов и количество разных D-классов этой полугруппы. Также найдено количество R- и L-классов, которые содержатся в данном D-классе. Особое внимание уделено описанию сечений отношений Грина полугруппы . Показано, что полугруппа не содержит H-сечений. Описаны R- и L-сечения этой полугруппы, дана классификация R- (L-)-сечений с точностью до изоморфизма.

Ключевые слова: корневое регулярное дерево, частичный автоморфизм, инверсная полугруппа, частичное сплетение, сечения отношений Грина.



ABSTRACT

Kochubinska Ye.A. Semigroups of partial automorphisms of rooted trees. -- Manuscript.

PhD Thesis in the speciality 01.01.06 -- algebra and number theory. -- Kyiv National Taras Shevchenko University, Kiev, 2008.

The thesis work is devoted to study of semigroups of partial automorphisms of rooted regular trees. New generalizations of bicyclic semigroup are introduced and some properties of generalized bicyclic semigroups are studied. We construct representation of this semigroup by partial permutations on the set of right -classes by closed inverse subsemigroups. The semigroup ConPAutT of partial automorphism of tree T, defined on a connected graph containing root and preserving the level of vertices, is considered and its properties are studied. Generalized partial wreath product is introduced. Due to this construction we get a description of closed inverse subsemigroups and then we construct a permutational representation of semigroup ConPAutT. Abstract characterization of semigroup ConPAutT is obtained.

We prove that for a finite rooted regular tree T the semigroup ConPAutT is isomorphic to k-th partial wreath power of the finite inverse symmetric semigroup ISn. We get combinatorial results for the partial wreath power of semigroup ISn. A description and classification up to isomorphism of R- and L-cross-sections of partial wreath product is given. It is shown that semigroup does not contain H-cross-sections.

Keywords: rooted regular tree, partial automorphism, inverse semigroup, cross-sections with respect to Green's relations.

Размещено на Allbest.ru

...