Группа Джевонса

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:09, 18 марта 2016.
TemplateDifinitionIcon.svg Определение «Определение 1»

Группа называется группой Джевонса ( отвечает за инвертирование, отвечает за перестановку).

Пусть

"Хвост" задает группу сдвигов (афинную группу).

Берем:

Рассмотрим:

Пусть - все векторы веса

орибталы - пары векторов, у которых вес одинаковый.

Орбиталы группы Джевонса

TemplateDifinitionIcon.svg Определение «Определение 2»

Орбиталы группы Джевонса:

(т.е. орбиталов из векторов одного веса).

вес каждого набора
TemplateExampleIcon.svg Пример Упражнение 1
Нарисовать все орбиталы следующих групп: (веса Хэмминга соответственно равны 2, 3 и 4).


TemplateTheoremIcon.svg Теорема Утверждение 1

Для любой точки взаимно однозначное соответствие между орбитами группы и орбиталами транзитивной группы

Доказательство
Отображение "на" сюръективно, "в" - инъективно.

Пусть - произвольный орбитал:

Тогда орбита а отображение "на", т.к. каждой орбите стабилизатора соответствует подмножество упорядоченных пар:

лежит в орбитале

Кроме того, Т.к. различные орбиталы имеют пустое пересечение, то биективно является отображением "в".


TemplateExampleIcon.svg Пример Пример 1

Орбитал - сумма всевозможных векторов, вес которых равен

все вектора веса

Значит, орбита стабилизатора


TemplateLemmaIcon.svg Лемма «Утверждение 2»

Если - орбитал группы то множество также является орбиталом и имеет следующий вид:


  • Если орбиталы совпадают граф неориентирован, если орбиты не совпадают граф противоположно направлен[1].

Орбиты группы , действующей на множестве Пусть дана группа и ее орбиталы:

Очевидно, что группа ранга (количество орбиталов).

тривиальный орбитал.

Орбиталы всегда можно пронумеровать таким образом, чтобы:

TemplateDifinitionIcon.svg Определение «Определение 3»

Орбитал называется симметричным, если

TemplateTheoremIcon.svg Теорема Утверждение 3

Пусть порядок транзитивной группы четен (т.е. количество элементов в четно). Тогда существует хотя бы один симметричный орбитал.

Доказательство

Т.к. четен, то существует такой, что:

(из теоремы Лагранжа: порядок элемента делит порядок группы), и

Пусть некоторому орбиталу

т.е. переставяем элементы (равенство выполняется по свойству ):


TemplateTheoremIcon.svg Теорема Теорема 1

Пусть транзитивна. Тогда - примитивна (нет нетривиальных блоков) граф связан для любого орбитала (граф не распадается на компоненты связности).

Доказательство
Необходимость:

Доказываем от противного.

Пусть граф не связан и группа примитивна: не связен для некоторого

Обозначим расстояние на графе. Тогда все точки, принадлежащие компоненте связности (для любого построим такие же множества).

Очевидно, (либо все точки переходят в другую компоненту связности, либо остаются в той же).

Возьмем произвольные точки т.е. точки, достижимые из , достижимы и из

Dgdm orbg 6.PNG

Т.к. выбор точки произвольный, то выполняется равенство:

Если и то

противоречие с примитивноcтью группы.

Достаточность:

Граф связен. Пусть группа импримитивна.

- ее нетривиальный блок, Рассмотрим орбитал

Орбитал обладает свойством: Т.к. не 2-транзитивна, то ее ранг больше и существует

Рассмотрим

Т.к. связен, то найдется ребро такое, что:

Пусть

Dgdm orbg 7.PNG
Тогда противоречие с импримитивностью группы.


Примечания

  1. Доказать самостоятельно.