Рассмотрим компактное множество K в R^3, определимое в о-минимальной структуре над R, например, полуалгебраическое или субаналитическое. В работе решается задача триангуляции монотонно растущего однопараметрического определимого семейства подмножеств в К. В каждом симплексе триангуляции семейство имеет один из 9 стандартных типов, биективно кодируемых лексикографически монотонными булевыми функциями от трех переменных. Подобные триангуляции полезны для верхних оценок гомологий определимых множеств.

В докладе будут затронуты две проблемы теории сложности вычислений: распознавание изоморфизма (конечных) графов и групп, и нахождение группы автоморфизмов ``симметричных’' объектов. В первом части мы приведем несколько эквивалентных определений размерности Вейсфейлера-Лемана групп и графов, проследим связь этого инварианта с проблемой изоморфизма, и опишем два новых результата: об алгебраической природе этого инварианта [1] и о размерности Вейсфейлера-Лемана графов перествновок [2]. Во второй части, мы поговорим о многомерных комбинаторных объектах, возникающих из групп перестановок и опишем новый результат о вычислении полной группы автоморфизмов такого объекта в случае, когда исходная группа перестановок разрешима [3].

[1] G.Chen, Q.Ren, and I.Ponomarenko, On multidimensional Schur rings of finite groups, J. Group Theory, 27:1, 61-88 (2024), https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdoi.or....

[2] J. Guo, A.L.Gavrilyuk, and I.Ponomarenko, On the Weisfeiler-Leman dimension of permutation graphs, SIAM Journal on Discrete Mathematics, 38:2, 1193-1929 (2024), https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdoi.or....

[3] I.Ponomarenko and A.V.Vasil'ev, On computing the closures of solvable permutation groups, International J. Algebra and Computation, 34:1, 137-145 (2024), doi: 10.1142/S0218196724500036.

Аннотация: Система доказательств резолюция над линейными уравнениями (Res(⊕)) оперирует дизъюнкциями линейных уравнений (линейными дизъюнктами) над полем GF(2); эта система расширяет обычную резолюцию с помощью линейной алгебры над полем GF(2). За последние десять лет было доказано несколько экспоненциальных нижних оценок на размер древовидных Res(⊕) опровержений. Суперполиномиальные нижние оценки на размер опровержений в системе Res(⊕) без ограничений до сих пор неизвестны.

В докладе будет рассказана экспоненциальная нижняя оценка на размер вывода в регулярной версии системы Res(⊕). Регурярная Res(⊕) --- это подсистема Res(⊕), естественным образом обобщающая регулярную резолюцию.
Это первая суперполиномиальная нижняя оценка на фрагмент системы Res(⊕), который строго сильнее древовидной Res(⊕).

Доклад основан на совместной работе с Климом Ефременко и Михалом Гарликом.