Эта публикация цитируется в
6 статьях
$2$-Замыкание $\frac{3}{2}$-транзитивных групп за полиномиальное время
А. В. Васильевab,
Д. В. Чуриковab a Новосибирский гос. университет,
ул. Пирогова, 1, Новосибирск 630090
b Институт математики им. С. Л. Соболева СО РАН,
пр. Коптюга, 4, Новосибирск 630090
Аннотация:
Пусть
$G$ — группа подстановок конечного множества
$\Omega$.
$k$-Замыкание
$G^{(k)}$ группы
$G$ — это наибольшая подгруппа симметрической группы
$\operatorname{Sym}(\Omega)$, имеющая общие с
$G$ орбиты на
$k$-й декартовой степени
$\Omega^k$ множества
$\Omega$. Группа
$G$ называется
$\frac{3}{2}$-
транзитивной, если она транзитивна и орбиты стабилизатора точки
$G_\alpha$ на множестве
$\Omega\setminus\{\alpha\}$ имеют одинаковую неединичную длину. Доказано, что для
$\frac{3}{2}$-транзитивной группы
$G$ ее
$2$-замыкание
$G^{(2)}$ может быть найдено за время, полиномиальное от мощности множества
$\Omega$. К тому же если группа
$G$ не является дважды транзитивной, то ее
$k$-замыкание для любого натурального числа
$k$ может быть найдено за то же время. С использованием полученного результата доказано существование полиномиального алгоритма, решающего проблему изоморфизма шуровых
$\frac{3}{2}$-однородных когерентных конфигураций, т. е. когерентных конфигураций, естественно ассоциированных с
$\frac{3}{2}$-транзитивными группами.
Ключевые слова:
$k$-замыкание группы подстановок,
$3\over 2$-транзитивные группы,
$3\over 2$-однородные когерентные конфигурации, шуровы когерентные конфигурации, изоморфизм когерентных конфигураций.
УДК:
512.542.7 Статья поступила: 01.10.2018
Окончательный вариант: 15.11.2018
Принята к печати: 19.12.2018
DOI:
10.33048/smzh.2019.60.208