Про властивості даграм Хассе NP-критичних частково впорядкованих множин порядку меншого за 8

Тип публікації :
Стаття
Дата випуску :
12 вересня 2024 р.
Автор(и) :
Стьопочкіна, Марина
Мова основного тексту :
Англійська
eKNUTSHIR URL :
DOI :
Журнал :
Том :
78
Випуск :
1
ISSN :
1812-5409
Початкова сторінка :
33
Кінцева сторінка :
35
Цитування :
[APA 7] Стьопочкіна, М. (2024). On properties of the Hasse diagrams of NP-critical posets of order less than 8. Bulletin of Taras Shevchenko National University of Kyiv. Physics and Mathematics, 78(1), 33–35. https://doi.org/10.17721/1812-5409.2024/1.5
[ДСТУ] Стьопочкіна М. On properties of the Hasse diagrams of NP-critical posets of order less than 8. Bulletin of Taras Shevchenko National University of Kyiv. Physics and Mathematics. 2024. Vol. 78, no. 1. P. 33—35. DOI: 10.17721/1812-5409.2024/1.5 (date of access: 25.07.2026).
М. М. Клейнер довів, що частково впорядковані (скорочено ч. в.) множина  має скінченний зображувальний тип тоді і лише тоді, коли вона не містить ч. в. підмножин вигляду  (1, 1, 1, 1)=, (2, 2, 2)=, (1, 3, 3)=, (1, 2, 5) = і (И, 4)=, які називаються критичними ч. в.  множинами. Узагальнення цього критерію на ручний випадок отримано Л. А. Назаровою. Відповідні множини називаються суперкритичними і складаються з ч. в. множин  (1, 1, 1, 1, 1) =, (1, 1, 1, 2) =, (2, 2, 3) =, (1, 3, 4) =, (1, 2, 6) = і (И, 5) =.  Критичні та суперкритичні  ч. в. множини  є також  (відповідно) крититичними щодо слабкої додатності та слабкої невід'ємності квадратичної форми Тітса, яке задається рівністю
У випадку заміни на додатність та  невід'ємність такі ч. в.  множини, які називаються  відповідно P-критичними та NP-критичними, описані автором разом з В. М. Бондаренком (їх число, з точністю до ізоморфізму і дуальності, дорівнює  75 і 115). У цій статті вивчаються комбінаторні властивості  діаграм Хассе NP-критичних ч. в. множин.
Файл(и) :
Вантажиться...
Ескіз
Завантажити
Формат :

Adobe PDF

Розмір :

446.25 KB

Контрольна сума :

(MD5):d0b4b622bfb6a0a974d60214be952aef

Creative Commons Attribution 4.0 International
Якщо не вказано інше, ця робота розповсюджується на умовах ліцензії Creative Commons Attribution 4.0 International