Алгебра инвариантов и восстановление к-орбит группы перестановок

• Автор: Мнухин, Валерий Борисович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Кишинев
• Количество страниц: 131 c. : ил

ГЛАВА I. АЛГЕБРА ИНВАРИАНТОВ ОРБИТ ГРУППЫ

ПЕРЕСТАНОВОК

§ I. . Предварительные определения

§ 2. Алгебры орбит и коорбит

§ 3. Примеры. Алгебра инвариантов графов

§ 4. Некоторые свойства матрицы вложимостей

§ 5. Усиление теоремы Ливингстона-Вагнера

ГЛАВА 2. ВОССТАНОВЛЕНИЕ к-ОРБИТ

§ I. Восстановление орбит: постановка задачи

§ 2. Гиперграфы орбит

§ 3. Ковосстановление несвязных орбит

§ 4. Восстановление орбит большой арности
§ 5. Восстановление орбит импримитивных групп
ЛИТЕРАТУРА

Во многих разделах алгебры еотественно появляется задача: определяется ли алгебраическая система своими подсистемами? Подобные проблемы в теории графов известны как гипотезы Улама-Келли и Хара-ри о вершинном и реберном восстановлении (формулировки приведены ниже). К настоящему времени их справедливость установлена в ряде частных слечаев, однако окончательного решения проблем не найдено (см. [I] и обзоры [2 - 6]). Изучаются также другие задачи восстановления графов, и распространения их на иные классы объектов (орграфы, гиперграфы, отношения, матроиды и др.). При этом, с одной стороны, ряд теорем о восстановлении графов оказывается справедливым и для орграфов, а с другой - гипотеза вершинного восстановления для последних была опровергнута в 1977 году П.Стокмейером [7, 8]. Возникает вопрос: нельзя ли продолжить задачи восстановления на достаточно широкий класс объектов так, чтобы для них существовали аналоги возможно большего числа утверждений о графах?
В диссертации проблемы восстановления переносятся на симмет-ризованные к-орбиты произвольной конечной группы перестановок.
При этом различным группам соответствуют случаи графов, орграфов, реберно-регулярных гиперграфов, ожерелий и т.д., а различным видам задач восстановления - проблемы Улама, Харари, и некоторые другие. Многие группы перестановок обладают невосстановимыми орбитами. В то же время в работе показано, что ряд результатов о графах (например, теоремы Гринуэлла, Ловаса, Мюллера, Татта, лемма Келли) справедлив для к-орбит любых групп. Это означает невозможность доказательства гипотез Улама и Харари на основе только подобных утверждений. Можно предположить, что для решения проблем
восстановления необходимо использовать методы теории групп перестановок.
Предлагаемый подход к задачам восстановления позволяет рассматривать большинство из них с единой точки зрения и применять для их исследования единый метод, основанный на вложении множества к-орбит в алгебру над полем действительных чисел. Этим способом в работе получаются новые результаты как о графах, так и о группах перестановок. Рассмотрим содержание диссертации подробнее.
Одним из способов изучения групп перестановок является сопоставление им тех или иных алгебраических систем. К таким системам относятся <5* -кольца Шура групп перестановок [ 9], их V -кольца
[10, II], ассоциативные схемы [12], универсальные алгебры Красне-ра [13 - 15] , алгебры антирефяексивных отношений (ЙК -алгебры) [16] и некоторые другие. Б диссертации вводится новый подобный объект - алгебра орбит, которая строится следующим образом.
Пусть С=(С,л/) - конечная группа перестановок на множестве 1л/ мощности п. Действие С продолжается на булеан по правилу: ... ,} , где^еС,
а V/ . Орбиты группы перестановок ( С , 2^ ) обозначим
через Ь0. кр ... , Кд, • Таким образом, есть множество, элементами которого служат некоторые подмножества V/ . Если мощность произвольного представителя орбиты Ь. равна к , то ее называют симметризованной к-орбитой группы О (см. [17]). Далее
слово"симметризованная” будем опускать.
Обозначим через множество всевозможных формальных линейных комбинаций 2>Л с коэффициентами ^ из поля К действительных чисел. Зададим на базисных элементах к. операцию умножения:

У-—» <-
для всех индексов J , соответствующих (^^-орбитам. Следовательно, строки матрицы линейно зависимы. Утверждение доказано.
Естественно возникает вопрос о возможности продолжения линейной зависимости столбцов матрицы вложимостей. Утверждение 1.4.6. Если в матрице Уру столбцы линейно зависимы, то они линейно зависимы с теми же коэффициентами
во всех матрицах Ур^у , » ... > Уоу •
Доказательство. Пусть в матрице столбцы, отвечающие ^.-орбитам , к^ , ... , линейно зависимы;
это означает выполнение равенства

Г. -9 й ■
Ц. 1 / ы.
и = ги У
(где не все ^ равны 0) для всякого индекса 4 такого, что ко-орбита и имеет арность р. Ясно, что достаточно показать линейную зависимость столбцов в матрице у ; справедливость утверждения будет следовать отсюда по индукции.
Заметим, что в силу утверждения 1.4

V - 1/ (
Р"**р 7°5
^ (<],-/>+?) р-ь/>чру '
Воспользуемся этой формулой для непосредственного вычисления линейной комбинации столбцов в Ур_1{ у :