ТЕОРЕМА О ПЛОЩАДИ ДИСКОВОЙ ДИАГРАММЫ НАД С(3)-Т(6)-ГРУППОЙ

Аннотация

Геометрические методы широко используются в комбинаторной теории групп. Теория групп с малыми сокращениями эффективно использует метод групповых диаграмм. Это позволяет решать, в частности, различные алгоритмические проблемы. Одной из таких проблем является проблема степенной сопряжённости. Будучи решённой в классе групп с условиями малого сокращения C(6)-T(3), она остаётся открытой в близком классе C(3)-T(6)-групп.

В данной статье исследуется структура односвязных диаграмм над C(3)-T(6)-группами и указывается, как это исследование может быть использовано при решении проблемы степенной сопряжённости.

Основным результатом данной статьи является доказательство теоремы о нижней оценке площади дисковой диаграммы на группой с условиями C(3)-T(6). Известно, что для групп с условиями C(p)-T(q) при \((p,q)\in \{(3,6), (4,4), (6,3)\}\), являющихся автоматными, изопериметрическое неравенство является квадратичным. То же самое утверждается в известной в теории групп с малыми сокращениями теореме о площади. Оба утверждения ограничивают сверху площадь односвязной приведённой диаграммы в рассматриваемом классе групп квадратичной функцией длины границы.

В данной статье доказано, что нижняя граница для площади диаграммы указанного типа тоже является квадратичной функцией длины границы. Важность этого результата видна с точки зрения оценки сложности алгоритма, решающего проблему равенства слов. Он оказывается не менее, чем квадратичной сложности от длины сравниваемых слов.