Логическая сложность свойства наличия индуцированного подграфа, изоморфного данному, для некоторых семейств графов

В настоящей работе изучается задача наиболее эффективной записи на языке первого порядка свойства наличия индуцированного подграфа, изоморфного заданному pattern-графу, тесно связанная с оцениванием временно́й сложности проверки такого свойства. Мы получили ряд новых оценок наименьшей кванторной глубины формулы, определяющей упомянутое свойство для pattern-графов на пяти вершинах, а также для дизъюнктных объединений изоморфных полных многодольных графов. Кроме того, мы доказали, что для любого $\ell\geqslant 4$ найдется граф на $\ell$ вершинах и формула первого порядка кванторной глубины не более $\ell-1$, записывающая свойство содержать индуцированный подграф, изоморфный этому графу.
Библиография: 12 названий.