О ДЕТЕРМИНИРОВАННОСТИ ПУТЕЙ НА ПОДСТАНОВОЧНЫХ КОМПЛЕКСАХ

Работа посвящена изучению комбинаторных свойств детерминированности семейства подстановочных комплексов, состоящих из четырехугольников, склееных друг с другом сторона-к-стороне. Данные свойства являются полезными при построении алгебраических структур с конечным числом определяющих соотношений. В частности, этот метод был использован при построении конечно определенной бесконечной нильполугруппы, удовлетворяющей тождеству x9 = 0. Эта конструкция решает проблему Л.Н. Шеврина и М.В. Сапира. В данной работе исследуется возможность раскраски всего семейства комплексов в конечное число цветов, при котором выполнено свойство слабой детерминированности: если известны цвета трех вершин некоторого четырехугольника, то однозначно определен цвет четвертой стороны, кроме некоторых случаев особого расположения четырехугольника. Даже слабой детерминированности хватает для построения конечно определенной нильполугруппы, при использовании данной конструкции доказательство сокращается в объеме. Свойства детерминированности помогают корректно ввести определяющие соотношения на полугруппе путей, проходящих на построенных комплексах. Определяющие соотношения соответствуют парам эквивалентных коротких путей. Свойства детерминированности изучались ранее в рамках теории замощений; в частности, Кари и Папасоглу был построен набор квадратных плиток, допускающий только апериодические замощения плоскости и обладающий детерминированностью: по цветам двух соседних ребер однозначно определялись цвета двух оставшихся ребер.

детерминированность, апериодические замощения, конечно определенные полугруппы, проблемы бернсайдовского типа