Класифiкацiйнi та комбiнаторнi задачi в теорiї квадратичних форм Тiтса

Рассадкiна М. В. Класифiкацiйнi та комбiнаторнi задачi в теорiї квадратичних форм Тiтса : дис. ... д-ра фіз.-мат. наук : 01.01.06 – алгебра та теорiя чисел. Київ, 2025. 351 с.

Рассадкiна М. В. Класифiкацiйнi та комбiнаторнi задачi в теорiї квадратичних форм Тiтса. – Квалiфiкацiйна наукова праця на правах рукопису.
Дисертацiя на здобуття наукового ступеня доктора фiзико- математичних наук за спецiальнiстю 01.01.06 – алгебра та теорiя чисел. – Полiський нацiональний унiверситет – Київський нацiональний унiверситет iменi Тараса Шевченка, Київ, 2025.
У 70-х роках минулого столiття розпочався новий етап розвитку теорiї зображень, пов’язаний з введенням зображень нових об’єктiв — таких як сагайдаки i частково впорядкованi множини. Об’єднання двох видiв зображень привiв до найбiльш загальних вiльних матричних задач, що дозволило, зокрема, дати точнi означення iнтуїтивно зрозумiлих понять, виник новий метод опису зображень класичних алгебраїчних об’єктiв, який полягає в їх зведеннi до вiльних матричних задач (нових чи вже добре вивчених). Отже, в теорiї зображень виникли рiзнi новi можливостi дослiджень тощо.
Специфiкою нових дослiджень зображень стала i так звана квадратична форма Тiтса. Вперше її ввiв у 1972 р. П. Габрiель для зображень сагайдакiв, а потiм в 1974 р. Ю. А. Дрозд для частково впорядкованих множин. Цi результати стали початком нового напрямку в алгебрi, який пов’язаний iз вивченням зв’язкiв мiж властивостями зобра- жень рiзних об’єктiв та властивостями вiдповiдних квадратичних форм. Дослiдження квадратичних форм Тiтса постiйно вимагають нових iдей i алгоритмiв, вони пов’язанi з рiзними класифiкацiйними i
комбiнаторними задачами.
Дисертацiйна робота присвячена вивченню квадратичних форм Тiтса скiнченних частково впорядкованих (скорочено ч.в.) множин з рiзних точок зору. Вона складається зi вступу i шести роздiлiв.
У вступi наведено загальну характеристику та мету роботи, об- ґрунтовано її актуальнiсть i наукову новизну тощо.
У першому роздiлi дисертацiйної роботи викладено основнi вiдомостi iз теорiї зображень категорiй, сагайдакiв i ч.в. множин, та зв’язок з квадратичними формами Тiтса.
У другому роздiлi детально викладено метод мiнiмаксної еквiвалентностi ч.в. множин, включаючи поняття мiнiмаксної системи твiрних для класiв ч.в. множин, приведено мiркування (з прикладами) про явнi i неявнi класифiкацiї та модифiкацiї класифiкацiй. Новими результатами, викладеними в цьому роздiлi, є модифiкована класифiкацiя P -критичних ч.в. множин (в сенсi опису по класам мiнiмаксних iзоморфiзмiв множин), опис Тiтса i не Тiтса P -критичних ч.в. множин та загальну теорему про ч.в. множини верхньої ширини 3. Для довiльної ч.в. множини знайдено зв’язок мiж нижньою i верхньою шириною як найменшою та найбiльшою шириною в класi всiх множин, мiнiмаксно еквiвалентних заданiй.
У другому роздiлi вивчаються також ч.в. множини з додатною квадратичною формою Тiтса; такi множини називаються додатними. Описано максимальнi додатнi множини i мiнiмальнi додатнi несерiйнi множини. Доведено, що кожна несерiйна додатна множина вкладається в максимальну як нижня або верхня пiдмножина. Доведено, що множина всiх додатних ч. в. множин має мiнiмаксну систему твiрних iз квазi- ланцюгових ч.в. множин (множин, дiаграми Хассе яких є ланцюгами). Доведено, що для неорiєнтованого графа Хассе довiльної зв’язаної несерiйної додатної ч. в. множини iснує додатний цикломатичний каркас. У третьому роздiлi доведено, що довiльна NP -критична ч. в. множина (мiнiмальна множина, квадратична форма Тiтса якої не є невiд’ємною) мiнiмаксно еквiвалентна суперкритичнiй множинi Назарової. Бiльш точно суперкритичнi множини (по одному iз кожного iз шести класiв iзоморфiзму) утворюють канонiчну мiнiмаксну систему твiрних для множини всiх NP -критичних ч. в. множин. Використовуючи це твер- дження, отримано повну загальну класифiкацiю NP -критичних ч.в. множин (їх число, з точнiстю до iзоморфiзму i дуальностi, дорiвнює 115). Отримано також модифiковану класифiкацiю NP -критичних ч. в. множин в тому сенсi, що (з точнiстю до iзоморфiзму i дуальностi) вказано ч.в. множини, що належать кожному iз шести класiв мiнiмаксної еквiвалентностi.
У четвертому роздiлi описано серiйнi невiд’ємнi ч.в. множини з одновимiрним цiлочисловим ядром їхньої квадратичної форми Тiтса (названi Д. Сiмсоном основними). Доведена гiпотеза Сiмсона про немож- ливiсть цiлочислової еквiвалентностi мiж квадратичними формами Тiтса основної ч. в. множини i циклiчної розширеної дiаграми Динкiна. Вве- дено поняття майже додатної ч.в. множини як невiд’ємної множини з максимальною додатною пiдмножиною. Доведено, що множина недодат- них майже додатних множин (названих суттєвими) збiгається з множи- ною основних множин. Це дає можливiсть при дослiдженнi основних ч.в. множин замiнити комбiнаторику квадратичних форм i вiдповiдних їм матриць на комбiнаторику самих ч.в. множин. Описано всi суттєвi май- же додатнi множини (з точнiстю до iзоморфiзму i дуальностi їх 247, не рахуючи P -критичних). Цей результат завершує опис всiх майже додат- них ч.в. множин як аналогiв звичайних i розширених дiаграм Динкiна.
У п’ятому роздiлi введено поняття надсуперкритичних ч. в. множин як природне продовження ряду “критичнi множини Клейнера — надсуперкритичнi множини Назарової”. Тодi клас всiх ч.в. множин, якi їм мiнiмаксно iзоморфнi, є природним продовженням ряду “ P -критичнi множини — NP -критичнi множини”. Згiдно отриманого опису ч.в. множин цього класу їх кiлькiсть, з точнiстю до iзоморфiзму i дуальностi, дорiвнює 203. Цей процес можна продовжити до нескiнченностi, ввiвши iндуктивно поняття m-надсуперкритичної ч. в. множини для довiльного натурального числа.
У шостому роздiлi дослiджуються коефiцiєнти транзитивностi для рiзних класiв ч.в. множин. Знайдено залежностi мiж шириною, висотою та коефiцiєнтом транзитивностi для несерiйних додатних ч. в. множин. А саме, доведено, що якщо kt(S) позначає коефiцiєнт транзитивностi ч.в. множин S, а w(S) i h(S) вiдповiдно її ширину i висоту, то для несерiйних додатних множин S i T маємо такi нерiвностi:
(1) kt(T ) > kt(S), якщо h(T ) > h(S) + 1;
(2) kt(T ) > kt(S) — 1 , якщо h(T ) = h(S) + 1.
(3) kt(T ) ≥ kt(S), якщо w(T ) = w(S) = 3 i h(T ) > h(S);
(4) kt(T ) ≥ kt(S), якщо w(T ) = w(S) = 2, h(T ) > h(S)
i дiаграма Хассе множини T не є циклом.
Для P -критичних ч.в. множин S i T маємо такi нерiвностi: (5 )kt(T ) > kt(S), якщо h(T ) > h(S) + 1;
(5) kt(T ) > kt(S) — 1 , якщо h(T ) = h(S) + 1.
У випадку ж, коли S i T — ч.в. множини, мiнiмаксно еквiвалентнi суперкритичним (вiдповiдно надсуперкритичним) множинам, маємо:
(7) kt(T ) > kt(S), якщо h(T ) > h(S) + 2,
(8) kt(T ) > kt(S) — 1 (вiдповiдно — 1 ), якщо h(T ) = h(S) + 2,
(9) kt(T ) > kt(S) — 1, якщо h(T ) = h(S) + 1.
Окрiм того, для рiзних класiв вказано умови, при яких коефiцiєнт транзитивностi є найбiльшим.