Київський національний університет імені Тараса Шевченка

Кубічка Євген Андрійович

УДК 512.562

Модальність зображень впорядкованих

множин.

01.01.08 - математична логіка, теорія алгоритмів і дискретна математика

Автореферат дисертації на здобуття наукового ступеня
кандидата фізико-математичних наук

Київ - 2006

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

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

національного університету імені Тараса Шевченка

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

Офіційні опоненти: доктор фізико-математичних наук,
старший науковий співробітник
БОНДАРЕНКО Віталій Михайлович,
Інститут математики
Національної Академії наук України,
провідний науковий співробітник;

доктор фізико-математичних наук, доцент
БОДНАРЧУК Юрій Вікторович,
Національний університет
“Києво-Могилянська Академія”,
завідувач кафедри математики.

Провідна установа Інститут математики, економіки і механіки при
Одеському національному університеті
імені І. І. Мечникова,
кафедра комп'ютерної алгебри
та дискретної математики, м. Одеса.

Захист відбудеться “10” квітня 2006 року о 14 годині на засіданні спеціалізованої вченої ради Д 26.001.18 при Київському національному університеті імені Тараса Шевченка за адресою: 03127, м. Київ, проспект акад. Глушкова, 6, механіко-математичний факультет.

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

Автореферат розісланий “ 07 ” березня 2006 року.

Учений секретар

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

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

Актуальність теми. Теорія матричних задач знаходиться на стику лінійної алгебри, комбінаторики, теорії зображень та теорії алгоритмів. Вперше, ще неявно, матричні задачі було застосовано в теорії цілочисельних зображень. У явній формі матричні задачі, зокрема, зображення частково впорядкованих множин з'явилися при дослідженнях зображень скінченновимірних алгебр, а саме, при доведенні гіпотез Брауера-Тролла. В роботах Л. О. Назарової та А. В. Ройтера було побудовано алгоритм, що дозволяє визначити, чи має дана частково впорядкована множина скінченну кількість нерозкладних зображень (так звані, множини скінченного типу), і, у випадку скінченності типу, вирахувати всі зображення даної множини. Користуючись цим алгоритмом, М. М. Клейнер отримав критерій скінченності та повний опис зображень множин скінченного типу. З результатів цих робіт, зокрема, слідували такі якісні факти, що стосуються зображень множин скінченного типу:

кільце ендоморфізмів будь-якого нерозкладного зображення є
тривіальним;

в будь-якій розмірності є не більше одного (з точністю до ізоморфізму)
нерозкладного зображення;

кількість зображень і їх вигляд не залежать від основного поля.

Одночасно з цим П. Габріель увів до розгляду зображення колчанів і довів, що колчан має скінченну кількість нерозкладних зображень тоді й лише тоді, коли його підлеглий неорієнтований граф є схемою Динкіна. Він також встановив, що в цьому випадку вектори розмірності нерозкладних зображень збігаються з додатніми коренями відповідних схем Динкіна, причому знову виконуються ті ж властивості 1-3 (див. вище), що й для зображень частково впорядкованих множин.

Доведення П. Габріеля, як і доведення Л. О. Назарової, А. В. Ройтера та М. М. Клейнера грунтувалися на явних обчисленнях. Більш концептуальні доведення дали для колчанів І. Н. Бернштейн, І. М. Гельфанд та В. А. Пономарьов, а для частково впорядкованих множин — Ю. А. Дрозд. Вони побудували функтори віддзеркалень, які переносять на категорію зображень звичайні віддзеркалення, що відповідають деякій цілочисельній квадратичній формі — формі Тітса колчана або частково впорядкованої множини. Після цього доводиться, що будь-яке зображення колчана або частково впорядкованої множини з додатною формою Тітса можна одержати віддзеркаленнями з "тривіальних зображень", вектори розмірності яких — це базові одиничні вектори.

Але поза увагою дослідників довгий час залишалося наступне питання. Припустимо, що частково впорядкована множина S не є множиною скінченного типу. Тим не менш, для фіксованої розмірності цілком можливо, що існує лише скінченна кількість зображень цієї розмірності (з точністю до ізоморфізму). Тоді ми казатимемо, що ця розмірність — розмірність скінченного типу. Виникає задача: дати критерій того, що дана розмірність — скінченного типу, і якщо це так — описати зображення цієї розмірності. Вперше на цю задачу звернули увагу П. Мад'яр, Дж. Вейман та А. Зелевінський. Вони розв'язали її для найпростішого випадку, коли частково впорядкована множина — примітивна, тобто є незв'язним об'єднанням лінійно впорядкованих множин. Простота цього випадку полягає в тому, що він порівняно легко зводиться до зображень колчанів (або орієнтованих графів) і тим самим до результатів В. Каца, який повністю розв'язав питання про розмірності нерозкладних зображень колчанів та кількість нерозкладних зображень в даній розмірності.

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

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

Тому для того, щоб одержати загальні результати, потрібно використовувати іншу техніку. Окрім достатньо відомих алгебричних методів (дії групи на множині, орбіти цієї дії, методи матричних задач), використовувались і більш специфічні методи. Насамперед, це комбінаторні методи, що грунтуються на алгоритмі диференціювання частково впорядкованих множин ширини 3. Метод диференціювання полягає в тому, що початкова частково впорядкована множина зводиться до простішої в певному розумінні множини. Диференційована (похідна) множина має фактично ті самі зображення, що й початкова, але вектор розмірності зображення похідної множини менший за вектор розмірності відповідного зображення початкової множини, що дозволяє використовувати індукцію для доведення різноманітних тверджень.

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

Обґрунтовуючи актуальність теми нашої роботи, слід відзначити, що теорія зображень частково впорядкованих множин органічно поєднується з багатьма іншими напрямками сучасної теорії зображень, які особливо інтенсивно досліджувалися протягом кількох останніх десятиріч. Принагідно відзначимо, що багато важливих відкриттів в цій теорії здійснено вченими київської алгебричної школи. На сьогоднішній день в цьому напрямку активно працюють Ю. А. Дрозд, В. В. Сергійчук, В. В. Кириченко, Н. С. Головащук, С. А. Овсієнко, В. М. Футорний.

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

Зв'язок з науковими програмами, планами, темами. Тематика дисертаційної роботи пов'язана з науково-дослідницькими роботами кафедри алгебри та математичної логіки Київського національного університету імені Тараса Шевченка, тема 01БФ038-03 "Розробка методів асимптотичного інтегрування нелінійних систем, теорії керування в біології та медицині і моделювання процесів взаємодії та деформування суцільних середовищ", підрозділ "Геометричні структури та комбінаторно-геометричні методи дослідження алгебраїчних систем та їх зображень" (номер державної реєстрації 0101U002479).

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

Об'єктом дослідження є зображення частково впорядкованих множин.

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

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

Наукова новизна одержаних результатів. В роботі отримано такі нові наукові результати:*

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

розмірності є додатною, або, що еквівалентно, носій жодної меншої розмірності не є "критичною" множиною і ця розмірність при цьому не є мінімальним уявним коренем форми Тітса. Це твердження є новим і може розглядатися як істотне узагальнення результатів Л. О. Назарової та А. В. Ройтера та Ю. А. Дрозда, де розглядались лише множини скінченного типу незалежно від розмірностей зображень. А також як узагальнення результатів роботи П. Мад'яра, Дж. Веймана та А. Зелевінського, де відповідний критерій був сформульований лише для частково впорядкованих множин особливого, найпростішого, в певному розумінні, типу.подано критерій існування нерозкладних зображень в розмірностяхскінченного типу зображень частково впорядкованих множин. А саме, в розмірності скінченного типу зображення частково впорядкованої множини існує нерозкладне зображення тоді і тільки тоді, коли ця розмірність є дійсним додатнім коренем форми Тітса, тобто форма Тітса дорівнює одиниці на векторі цієї розмірності. При цьому нерозкладне зображення є єдиним і орбіта нерозкладного зображення є відкритою в просторі всіх зображень даної розмірності. Це твердження
можна розглядати як узагальнення критерію Ю. А. Дрозда. А оскільки кожне зображення однозначно розкладається в пряму суму нерозкладних, тому цей критерій разом з наведеним вище результатом завершує повний опис зображень частково впорядкованих множин, розмірності яких є розмірностями скінченного типу.

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

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

Практичне значення одержаних результатів. Результати роботи, в основному, мають теоретичний характер. Їх практичне значення може полягати у використанні при подальших дослідженнях зображень частково впорядкованих множин, при вивченні зображень скінченних алгебр, модулів Коена-Маколея, векторних розшарувань та при розв'язанні інших класифікаційних задач алгебри та комбінаторики.

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

Апробація результатів дисертації. Результати дисертації доповідалися на 4-й Міжнародній Алгебраїчній Конференції в Україні (Львів, серпень 2003), на конференції з теорії зображень (Київ, грудень 2003), на 11-й Міжнародній Конференції з Зображень Алгебр (ICRA XI, Мексика, серпень 2004), на семінарах кафедри алгебри та математичної логіки Київського національного університету імені Тараса Шевченка.

Публікації. Основні результати дисертації опубліковано в 5 працях, з них 3 статті - у фахових наукових виданнях, 2-у матеріалах та тезах міжнародних конференцій.

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

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

У вступі обґрунтовується актуальність вибраної теми, визначаються мета і задачі дослідження, вказується на зв'язок дисертації з науковими програмами Київського національного університету імені Тараса Шевченка, наводяться основні результати і відзначається їх новизна, зазначається де відбувалася апробація цих результатів.

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

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

А саме, нехай d — деяка розмірність зображення частково впорядкованої множини S. Будемо казати, що d — розмірність скінченного типу, якщо існує лише скінченна кількість неізоморфних зображень даної розмірності.

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

Теорема 44. Нехай S —це частково впорядкована множина, d — розмірність її зображення. Тоді наступні умови рівносильні:

d —розмірність скінченного типу.

Для кожного виконується

Не існує такого, що носій — критична множина і —мінімальний уявний корінь для (тобто не існує такого, що носій — критична множина і ).

де через позначено цілочисельну квадратичну форму Тітса, що в літературі визначається наступним чином: для кожного , де маємо

Розмірність d зображення частково впорядкованої множини S є уявним коренем форми Тітса, якщо .

Зауважимо, що всі розмірності, що зазначені в умові 3 Теореми 44 описуються наступною схемою: Існує 5 таких розмірностей, позначимо їх ). На кожному малюнку точками позначено елементи ; номери біля точок — це значення — елементи вектора розмірності. Відношення показано ребрами від х (знизу) до у (згори). Номером в кружечку згори позначено розмірність .

Лема 45. Якщо алгебрична група G алгебрично діє на алгебричному многовиді М, причому має лише скінченну кількість орбіт, то

Імплікації 1 => 2 та 2 => 3 Теореми 44 доводяться порівняно легко за допомогою леми 45 з теорії дій груп на множині. Більш складним для доведення, а також; більш важливим є імплікація 3 => 1.

Нехай - це множина S, продиференційована за максимальним елементом а. Вводяться допоміжні вектори розмірностей зображення, та та такі твердження:

Твердження 46. Нехай d — розмірність зображення множини S, яка задовольняє умову 3 Теореми 44, а f — розмірність , підпорядкована розмірності d. He існує зображення розмірності такого, що носій d' — критична множина id'— мінімальний уявний корінь для S

Твердження 47. Нехай d — розмірність зображення частково впорядкованої множини S, що задовольняє умову 3 Теореми 44, а f — розмірність зображення частково впорядкованої множини , підпорядкована розмірності d. He існує зображення розмірності

Рис. 1: Критичні розмірності

Рис. 2: Критичні розмірності та

такого, що розмірність d' є однією з , , , , і носій d' — така підмножина , що містить принаймні один "новий" елемент.

Лема 48. Якщо в похідній множині є точки х, , ..., з розмірностями відповідно , ,... , , то стара розмірність в точці х є

не меншою за

Наслідок 49. Якщо s — стара розмірність в точці х, an— нова розмірність в точці х, то s > п.

Наслідок 50. Якщо s — стара розмірність в точці х, an— нова розмірність в точці (х, у) диференційованої множини, то s > п.

Використовуючи введену М. М. Клейнером класифікацію можливих похідних множин, що містять принаймні один "новий" елемент, та алгоритм побудови оригінальної множини за похідною шляхом перебору всіх можливих варіантів доведено Твердження 47. Тобто показано, що якщо розмірність зображення похідної множини є однією з , (розглядаємо лише частково впорядковані множини ширини 3), то в оригінальній множині є підмножина одного з типів — , що неможливо. Це є достатнім для доведення імплікації 3 => 1 Теореми 44.

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

Наведемо найбільш характерні випадки:

Випадок 51. * 1°° d' має вигляд , , , , (позначення, як зазначено вище, з роботи М. М. Клейнера). Множина , має вигляд

Тоді множина І = має наступний вигляд

Очевидно, що ця частково впорядкована множина містить примітивну підмножину типу (1,3,3). З наслідків леми 48 маємо, що розмірність в кожній точці не менша за 1. Щоб довести, що розмірність зображення оригінальної множини більша за одну з , , , (в даному випадку — ), достатньо довести, що розмірність в точці а не менша за 2. Це дійсно так, адже розмірність в точці а —це розмірність d'(0) в зображенні похідної множини R, яка, в свою чергу, не менша за 3.

Випадок 62. * * * 2°° d' має вигляд , , , . Множина R мае вигляд

Тоді множина має наступний вигляд

Очевидно, що ця частково впорядкована множина містить примітивну підмножину типу (2,2,2) ( ). 3 наслідків леми 48 маемо, що розмірність в кожній точці не менша за 1. Тому розмірність зображення оригінальної множини більша за .

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

Спочатку доводяться певні допоміжні твердження:

Твердження 70. Зображення V частково впорядкованої множини S є нерозкладним тоді й тільки тоді, коли в його алгебрі ендоморфізмів End(V) немає нетривіальних ідемпотентів, тобто таких ендоморфізмів е, що , причому і .

Наслідок 71. Якщо End (V) = k, то зображення V є нерозкладним.

Головним результатом розділу є наступний критерій.

Теорема 72. Нехай d — розмірність скінченного типу зображення частково впорядкованої множини S. В розмірності d існує нерозкладне зображення V тоді й лише тоді, коли . У цьому випадку нерозкладне зображення розмірності d єдине, End(V) = k і орбіта зображення V є відкритою в просторі всіх зображень розмірності d.

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

Комбінуватимемо диференціювання частково впорядкованих множин з аналогічними теоремі 72 результатам з робіт Ю. А. Дрозда про частково впорядковані множини скінченного типу. А саме, використаємо індукцію за . Випадок |d| = 1 є очевидним. Таким чином, можна вважати, що — це розмірність скінченного типу, Теорема 72 виконується для кожної розмірності скінченного типу d' зображення частково впорядкованої множини S' такого, що , і, більш того, d є точним.

Нехай є нерозкладним елементом, V — відповідне зображення множини S, а М — це блочна матриця, що описує . Вона має вигляд

де М(а) — матриця розміру .

Зафіксуємо елемент і позначимо через ту частину М, що складається з блоків , де . Тоді

Лема 73. Стовпчики матриці є лінійно незалежними.

Лема 74. Нехай частково впорядкована множина S містить підмножину

а V — це нерозкладне зображення множини S, розмірність якого d — скінченного типу. Тоді або d(x) = 0 або d(t) = 0.

Лема 75. Нехай d — розмірність скінченного типу точного зображення частково впорядкованої множини S, яка має ширину щонайбільше 3. Тоді існують максимальні елементи такі, що кожен "новий" елемент з має вигляд для певного і множина також має ширину щонайбільше 3.

Після цих лем формулюється наступне твердження, що є ключовим в доведенні необхідності Теореми 72:

Лема 76. В умовах Теореми 72 для нерозкладного зображення V можна вибрати максимальний елемент таким чином, що .

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

Наслідок 77. Нехай — частково впорядкована множина, "обернена" до S, тобто вона складається з тих самих елементів, що й S, а відношення визначається наступним чином: тоді й тільки тоді, коли . Тоді розмірності скінченного типу для зображень множин S та збігаються, так само як і розмірності скінченного типу, в яких існує нерозкладне зображення. Зокрема, існує взаємно однозначна відповідність між нерозкладними зображеннями, розмірності яких — скінченного типу, для множин S та .

Наслідок 78. Якщо d — розмірність скінченного типу частково впорядкованої множини S, V — нерозкладне зображення розмірності d, а х — довільний елемент з S, то . Зокрема, остання сума не перебільшує d(0).

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

Наведемо тут повністю найбільш характерний випадок, а також результати всіх інших випадків

Випадок 79. S = (1,1,1,1).

Єдине нерозкладне зображення цієї розмірності описується матрицею

Випадок 80. S = (2, 2, 2) = .

Єдине нерозкладне зображення цієї розмірності описується матрицею

Випадок 81. S = (1, 3, 3) = .

Існує три точні нерозкладні зображення, розмірності яких — скінченного типу:

Випадок 82. S = (1, 2, 5) = .

В цьому випадку існує 11 нерозкладних точних зображень, розмірності яких — скінченного типу:

Випадок 83. S = .

Якщо d — точна розмірність скінченного типу, то або d(0) < 5 (тоді обов'язково d(0) = 4), або , або . Припустимо спочатку, що d(0) = 4. Тоді обов'язково для всіх і, і . Позначимо , , , . Тоді

Звідси легко бачити, що є три можливості, при яких : x = y = z = t = 1, або x = 2,y = z = t = 1, або х = у = z = 1,t = 2.

Це дає три точні нерозкладні зображення:

та

Нехай тепер d(0) > 5, але . Продиференціюємо частково впорядковану множину за . Одержимо множину такого вигляду:

де . Вона містить єдину критичну підмножину типу (1,3,3) — це Т = . Нехай знову V — нерозкладне зображення розмірності d, і N — носій d'. Як і у попередньому випадку, легко бачити, що коли , обов'язково N = Т (треба врахувати, що ). Нагадаємо, що ; якщо ж , то 3 зображень множини Т, обчислених вище, лише одне задовольняє умову : це зображення, в якому для всіх . Тоді для всіх . Одержимо зображення

Якщо Т ^ N, то N — множина скінченного типу, і знову можна використати список зображень з роботи М. М. Клейнера. Зауважимо, що, оскільки розмірність d точна, a , обов'язково N. Знов-таки, нескладна перевірка показує, що нерівність виконується лише у випадку, коли і для всіх . Тоді для всіх інших елементів з S. Одержимо нерозкладне зображення

Нарешті, розмірності, для яких , але можна одержати за наслідком 77. Це дає ще два точних нерозкладних зображення, розмірності яких — скінченного типу:

Отже, множина R має 7 точних нерозкладних зображень, розмірності яких — скінченного типу.

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

Дана програма написана з використанням мов програмування РНР та JavaScript і для її функціонування є небхідним Web-сервер з підтримкою РНР, та JavaScript-сумісний Web-браузер. Ознайомитись з роботою програми можна за наступною адресою в Інтернеті: http://kubichka.kiev.ua/projects/progasp.

Програма виконує 2 основні задачі. Першою є пошук всіх розмірностей скінченного типу для зображення введеної користувачем частково впорядкованої множини. Для цього шляхом перебору знаходяться клейнерівські "критичні" підмножини. Тоді визначаються "критичні" розмірності і, згідно з Теоремою 44, розмірностями скінченного типу будуть такі розмірності, які не є більшими за жодну з критичних . Зауважимо, що в цьому випадку розглядаються лише точні зображення, тобто розмірність в кожній точці приймається не меншою за 1. У цьому випадку після машинної звірки усіх -елементних наборів точок з "критичними" підмножинами програмою формується одна з можливих відповідей:

Якщо жоден з наборів не співпав з жодною з "критичних" клейнерівських підмножин, то початкова частково впорядкована множина їх не містить, і, згідно з Теоремами з роботи М. М. Клейнера, будь-яка розмірність зображення даної множини є розмірністю скінченного типу.

Якщо існує такий 4-точковий набір, що співпадає з множиною (1,1,1,1), або існує такий 6-точковий набір, що співпадає з множиною (2, 2, 2), то, виходячи з того, що розглядаються лише точні зображення, розмірність будь-якого зображення буде не меншою за (або відповідно). Тому, згідно з Теоремою 44, розмірність будь-якого точного зображення введеної частково впорядкованої множини не є розмірністю скінченого типу.

Якщо жоден з наборів не співпав з (1,1,1,1) чи (2,2,2), але якийсь з наборів співпав з іншою "критичною" підмножиною, то формується список векторів, і розмірність зображення введеної частково впорядкованої множини є розмірністю скінченного типу тоді і
тільки тоді, коли вона не є більшою жодного зі сформованих векторів.

Другою задачею програми є перевірка того, чи є введена додатково розмірність розмірністю скінченного типу зображення частково впорядкованої множини. Тут використовується п.2 Теореми 44, а саме: для кожної меншої розмірності рахується форма Тітса. У випадку, якщо для кожної меншої розмірності форма є додатною, введена розмірність є розмірністю скінченного типу, в противному випадку виконання програми зупиняється на розмірності, для якої форма менша 1. Тут розглядаються і неточні зображення, для яких можливі нульові координати вектора розмірності зображення.

ВИСНОВКИ

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

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

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

Описані результати узагальнюють відомі результати Л. А. Назарової, А. В. Ройтера, Ю. А. Дрозда про зображення частково впорядкованих множин скінченного типу, а також результат П. Мад'яра, Дж. Веймана та А. Зелевінського про розмірності скінченного типу зображень примітивних частково впорядкованих множин.

Результати дисертації є новими і не мають аналогів у сучасній науковій літературі.

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

Drozd Y. A., Kubichka E. A. Representations of finite type of partially ordered sets// Algebra and Discrete Mathematics - 2004. - 3. - pp. 21-37.

Кубічка Є. А. Зображення частково впорядкованих множин в розмірностях скінченного типу// Вісн. Київ, ун-ту. Сер. Фізико-математичні науки. - 2002. - вип. 3. - С. 39-46.

Кубічка Є. А. Розмірності скінченного типу зображень частково впорядкованих множин// Вісн. Київ, ун-ту. Сер. Фізико-математичні науки. - 2003. - вип. 3. - С. 44-48.

Kubichka E. A. Dimensions of finite type for representations of posets// IV Міжнар. алгебр. конф. в Україні (4-9 серпня 2003р., Львів): Тези доп. - Львів, 2003. - С. 123-124.

5. Kubichka E. A. Representations of finite type of partially ordered sets// Міжнар. алгебр, конф. "C'*-algebras, Lie algebras and related topics" (5-7 грудня 2003р., Київ): Тези доп. - Вид-во ун-ту Упсали, 2003. - С. 13.

АНОТАЦІЯ

Кубічка Є. А. Модальність зображень впорядкованих множин. -Рукопис.

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

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

Ключові слова: частково впорядковані множини, зображення, розмірність, матричні задачі, форма Тітса.

АННОТАЦИЯ

Кубичка Е. А. Модальность представлений упорядоченных множеств. -Рукопись.

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

Диссертация посвящена изучению размерностей конечного типа представлений частично упорядоченных множеств. Рассмотрены такие частично упорядоченные множества бесконечного представимого типа, которые, тем не менее, для фиксированной размерности имеют конечное число неизоморфных представлений этой размерности (такие размерности — т.н. размерности конечного типа). С помощью метода Назаровой-Ройтера "дифференцирования" частично упорядоченных множеств ширины 3, а также других методов алгебры и комбинаторики проведено исследование представлений таких множеств. При этом используются введенные М. М. Клейнером классификация возможных производных частично упорядоченных множеств и алгоритм получения оригинального множества из производного. Получен критерий конечности типа размерности представлений таких множеств. А именно, размерность имеет конечный тип тогда и только тогда, когда форма Титса на каждой меньшей размерности положительна, или, что эквивалентно, не существует такой меньшей размерности, которая является минимальным мнимым корнем формы Титса (т.е. форма Титса равна нулю на этой размерности) и носитель которой при этом — "критическое" множество.

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

Кроме того, вычислены все точные неразложимые представления каждой из "критических" частично упорядоченных множеств, размерности которых имеют конечный тип.

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

Результаты являются новыми и могут рассматриваться как обобщение результатов Л. А. Назаровой, А. В. Ройтера и Ю. А. Дрозда о множествах конечного типа, и результатов П. Мадьяра, Дж. Веймана и А. Зелевинского о примитивных частично упорядоченных множествах.

Ключевые слова: частично упорядоченные множества, представления, размерность, матричные задачи, форма Титса.

ABSTRACT

Kubichka E. A. Modality of representations of ordered sets - Manuscript.

The dissertation for obtaining the scientific degree of the candidate of physical and mathematical sciences on the speciality 01.01.08 - mathematical logic, theory of algorithms and discrete mathematics. Kyiv Taras Shevchenko National University. Kyiv, 2005.

The dissertation studies finite type dimensions of partially ordered sets. Partially ordered sets of infinite dimension type having, for some fixed dimension, finite number of non-isomorphic representations of this dimension are considered. For this kind of partially ordered sets we obtained the criterium of finiteness of dimension type. Namely, the dimension is of finite type if and only if Tits form is positive on every smaller dimension. Also we proposed and proved the criterium of existence of indecomposable representations in finite type dimensions of representations of partially ordered sets. Namely, there exists indecomposable representation in finite type dimension if and only if Tits form is equal to 1 on the vector of this dimension. In this case indecomposable representation is unique up to isomorphism and the orbit of indecomposable representation is open in space of all representations of this dimension. Thus we obtain full description of such class of matrix problems. Moreover, we calculated all sincere indecomposable representations of "critical" partially ordered sets of finite dimension type and we introduced software for computer investigation of some numeric and functional characteristics of partially ordered sets.

Keywords: partially ordered sets, representation, dimension, matrix problems, Tits form.