Про властивості даграм Хассе NP-критичних частково впорядкованих множин порядку меншого за 8
DOI:
https://doi.org/10.17721/1812-5409.2024/1.5Ключові слова:
ч. в. множина, критична та суперкритична ч. в. множина, дуальність, діаграма Хассе, мінімаксна еквівалентність0Анотація
М. М. Клейнер довів, що частково впорядковані (скорочено ч. в.) множина має скінченний зображувальний тип тоді і лише тоді, коли вона не містить ч. в. підмножин вигляду (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-критичних ч. в. множин.
Посилання
Kleiner M. M. (1972) Partially ordered sets of finite type. Zap. Nauch. Semin. LOMI, 28, 32–41 [in Russian].
Bondarenko V. M., & Styopochkina M. V. (2005) (Min, max)-equivalence of partially ordered sets and the Tits quadratic form. Problems of Analysis and Algebra: Zb. Pr. Inst. Mat. NAN Ukr., 2, №3, 18-58 [in Russian].
Bondarenko V. M. (2005) On (min, max)-equivalence of posets and applications to the Tits forms. Bull. of Taras Shevchenko University of Kiev (series: Physics& Mathematics), 1, 24-25.
Nazarova L. A. (1975) Partially ordered sets of infinite type. Izv. Akad. Nauk SSSR Ser. Mat., 39, №5, 963-991 [in Russian].
Bondarenko V. M., & Styopochkina M. V. (2008) (Min, max)-equivalency of posets and nonnegative Tits forms. Ukrainian Math. J., 60,№9, 1349-1359. https://doi.org/10.1007/s11253-009-0147-7
Bondarenko V. M., & Styopochkina M. V. (2009) Description of posets critical with respect to the nonnegativity of the quadratic Tits form. Ukrainian Math. J., 61, №5, 734-746. https://doi.org/10.1007/s11253-009-0245-6
Bondarenko V. M., Chervyakov I. V., & Styopochkina M. V. (2015) On properties of the Hasse diagram of P-critical posets. Nauk. Visn. Uzhgorod. Univ., Ser. Mat. and Imfor, 26, №1, 12-15.
Завантаження
Опубліковано
Номер
Розділ
Ліцензія
Авторське право (c) 2024 Maryna Stopochkina
Ця робота ліцензується відповідно до ліцензії Creative Commons Attribution 4.0 International License.
Автори, роботи яких публікуються у цьому журналі, погоджуються з такими умовами:
- Автори зберігають авторські права та надають журналу право на першу публікацію роботи, яка одночасно ліцензується згідно із Creative Commons Attribution License, тобто надається дозвіл іншим ділитися роботою з визнанням авторства роботи та першої публікації в цьому журналі.
- Автори можуть укладати окремі додаткові угоди щодо невиключного розповсюдження опублікованої журналом версії роботи (наприклад, розмістити її у репозитарії наукової установи чи опублікувати у книзі) з підтвердженням її початкової публікації у цьому журналі.
- Дозволяється та заохочується розміщення своїх робіт в мережі Інтернет авторами (наприклад, у репозитаріях наукових установ або на особистих веб-сторінках) до та під час процесу подання, оскільки це може призвести до продуктивного обміну, а також до більш ранніх цитувань опублікованої роботи та їх більшої кількості (див. The Effect of Open Access).
