Preview

Чебышевский сборник

Расширенный поиск

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

https://doi.org/10.22405/2226-8383-2016-17-3-18-27

Полный текст:

Аннотация

Геометрические методы широко используются в комбинаторной теории групп. Теория групп с малыми сокращениями эффективно использует метод групповых диаграмм. Это позволяет решать, в частности, различные алгоритмические проблемы. Одной из таких проблем является проблема степенной сопряжённости. Будучи решённой в классе групп с условиями малого сокращения 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)\}\), являющихся автоматными, изопериметрическое неравенство является квадратичным. То же самое утверждается в известной в теории групп с малыми сокращениями теореме о площади. Оба утверждения ограничивают сверху площадь односвязной приведённой диаграммы в рассматриваемом классе групп квадратичной функцией длины границы.

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

Об авторе

Н. В. Безверхний
Тульский государственный педагогический университета им. Л. Н. Толстого
Россия
доктор физико-математических наук, профессор, профессор


Список литературы

1. Lindon R., Schupp P., 1980, "Kombinatorial group theory". М.: Мir.

2. Gersten S. M., Short H., 1990, "Small cancellation theory and automatic groups". Inventiones mathematicae 102, pp. 305–334.

3. Bezverkhniy N. V., 1999, "The solvability of the membership problem into the cyclic subgroup of C(6)-group". Fundamentalnaya i prikladnaya matematika, v. 5, N 1, pp. 39–46.

4. Parshikova E. V., 2001, "The solvability of the weak power conjugacy problem in


Для цитирования:


Безверхний Н.В. ТЕОРЕМА О ПЛОЩАДИ ДИСКОВОЙ ДИАГРАММЫ НАД С(3)-Т(6)-ГРУППОЙ. Чебышевский сборник. 2016;17(3):18-27. https://doi.org/10.22405/2226-8383-2016-17-3-18-27

For citation:


Bezverkhniy N.V. THE AREA THEOREM FOR THE DISC DIAGRAM OVER С(3)-Т(6)-GROUP. Chebyshevskii Sbornik. 2016;17(3):18-27. (In Russ.) https://doi.org/10.22405/2226-8383-2016-17-3-18-27

Просмотров: 109


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2226-8383 (Print)