"Записки научных семинаров ПОМИ"

Том 402, стр. 108-147

С.-Петербургское отделение Математического института им. В. А. Стеклова РАН, Фонтанка 27, 191023 Санкт-Петербург, Россия

inp@pdmi.ras.ru

Аннотация: Хорошо известно, что для каждой группы перестановок $G$ нечетного порядка найдется множество точек, стабилизатор которого в $G$ тривиален, а если эта группа примитивна, то найдется и ©база размера не более $3$. Эти результаты обобщаются на когерентную конфигурацию группы $G$ (в этом случае конфигурация шурова и антисимметрическая). Это позволяет построить алгоритм полиномиальной сложности для распознавания и проверки изоморфизма шуровых турниров (т.е. раскрашенных по дугам турниров, когерентные конфигурации которых шуровы). Библ. -- 24 назв.
Ключевые слова: когерентная конфигурация, линейная группа, сплетение, алгоритм Вейсфейлера--Лемана [Coherent configuration, linear group, wreath product, the Weisfeiler--Leman algorithm]