Транзитивность групп преобразований

Пусть G — группа подстановок множества X. Элементы х, у е X называются G-эквивалентными, если g (x) = у для некоторой подстановки g е G. Данное отношение является отношением эквивалентности на X, так как каждый элемент X является циклическим в графе Г$(Х). Классы G-эквивалентности называются областями транзитивности группы G. Если G = (S), где S = {g_t, …, g_p}, то области транзитивности группы G суть компоненты связности в Г₅(Х). Группа подстановок G называется транзитивной (интранзитивной), если X — ее область транзитивности (X разбивается на две или более областей транзитивности). Орбитой элемента хе X относительно группы G (обозначается G (x)) называется область транзитивности группы G, содержащая элемент х.

Обозначим через Х^к множество всех неупорядоченных бесповторных выборок размера к из алфавита X. Свойство транзитивности групп подстановок, определяющее переходы символов х, обобщается на свойство^{-транзитивности} (к — натуральное), определяющее возможность переходов выборок из Х^к.

Неупорядоченные бесповторные выборки (рс^ …, x_k) и {у_х, …, у_}{) из X^k1 называют G-эквивалентными (обозначается (x_v …, x_k) =^G (уу^)), если g (Xj) = Уг для некоторой подстановки g е G_y i = 1,…, k. Отношение =^G является эквиваленцией на X^k.

Подмножества множества X^k образующие классы G-эквивалентности, называются областями k-транзитивности группы G. Группа G называется к-транзитивной, если ее единственная область^{-транзитивности} есть XI*1, и к-интранзитивной в противном случае. Орбитой выборки (х_1? …, x_k) относительно группы G (обозначается G (x_{, …, x_k)) называют область^{-транзитивности} полугруппы G, содержащую эту выборку.

Свойство^{-транзитивности} групп допускает также вероятностную интерпретацию. Вероятностная мера задается на элементах группы, и возможность переходов выборок характеризуется соответствующими вероятностями.

Стабилизатором элемента х в группе подстановок G (обозначается St_v(G)) называется подгруппа всех подстановок группы G, для которых элемент х неподвижный.

Теорема 4.23 (лемма Бернсайда). Для любого х е X и группы подстановок G < S (X)

А Пусть R_x(G) — отношение эквивалентности в группе подстановок G но подгруппе St_v(G): g, h е R_X(G) g/r¹ e St_r(G). Отсюда g, h eR_x(G) gh~^x(x) = x g (x) = h (x). Значит, | {g (x): g e G} | равен числу правых смежных классов G по St_v(G), т. е. I G (x) | = [G: St_v(G)]. Отсюда по теореме Лагранжа получаем нужное равенство. ?

Следствие. Для транзитивной группы G и любогохе X

Теорема 4.24 [2]. Группа подстановок G является^{-транзитивной} G транзитивна и для некоторого х е X является (к — 1)-транзитивной подгруппа St_v(G), рассматриваемая как группа подстановок множества Х {х}. О Группа подстановок G называется регулярной, если для любых х, у е X в G имеется единственная подстановка g такая, что g (x) = у. Регулярность группы подстановок G равносильна следующим условиям [2]:

• а) G транзитивна и St_r(G)I = 1 для любого хе X;
• б) G транзитивна и G| = |х|.

Нижние строки таблиц всех подстановок регулярной группы образуют латинский квадрат над X, т. е. квадратную таблицу порядка |х|, где каждая строка и каждый столбец есть перестановка элементов множества X. Латинский квадрат над X есть таблица функции /: X² —> X, биективной по обеим переменным.