Содержание к диссертации
Введение
ГЛАВА I. Алгебра инвариантов орбит группы перестановок 17
I. Предварительные определения 17
2. Алгебры орбит и коорбит. 22
3. Примеры. Алгебра инвариантов графов 34
4. Некоторые свойства матрицы вложимостей 41
5. Усиление теоремы Ливингстона-Вагнера 51
ГЛАВА 2. Восстановление к-Ореит 65
I. Восстановление орбит: постановка задачи 65
2. Гиперграфы орбит 75
3. Ковосстановление несвязных орбит 84
4. Восстановление орбит большой арности 98
5. Восстановление орбит импримитивных групп 112
Заключение
- Примеры. Алгебра инвариантов графов
- Усиление теоремы Ливингстона-Вагнера
- Ковосстановление несвязных орбит
- Восстановление орбит импримитивных групп
Введение к работе
Во многих разделах алгебры естественно появляется задача: определяется ли алгебраическая система своими подсистемами? Подобные проблемы в теории графов известны как гипотезы Улама-Келли и Хара-ри о вершинном и реберном восстановлении (формулировки приведены ниже). К настоящему времени их справедливость установлена в ряде частных слечаев, однако окончательного решения проблем не найдено (см. [I] и обзоры [2 - 6]). Изучаются также другие задачи восстановления графов, и распространения их на иные классы объектов (орграфы, гиперграфы, отношения, матроиды и др.). При этом, с одной стороны, ряд теорем о восстановлении графов оказывается справедливым и для орграфов, а с другой - гипотеза вершинного восстановления для последних была опровергнута в 1977 году П.Стокмейером [7, 8]. Возникает вопрос: нельзя ли продолжить задачи восстановления на достаточно широкий класс объектов так, чтобы для них существовали аналоги возможно большего числа утверждений о графах?
В диссертации проблемы восстановления переносятся на симмет-ризованные к-орбиты произвольной конечной группы перестановок. При этом различным группам соответствуют случаи графов, орграфов, реберно-регулярных гиперграфов, ожерелий и т.д., а различным видам задач восстановления - проблемы Улама, Харари, и некоторые другие. Многие группы перестановок обладают невосстановимыми орбитами. В то же время в работе показано, что ряд результатов о графах (например, теоремы Гринуэлла, Ловаса, Мюллера, Татта, лемма Келли) справедлив для к-орбит любых групп. Это означает невозможность доказательства гипотез Улама и Харари на основе только подобных утверждений. Можно предположить, что для решения проблем
- 4 -восстановления необходимо использовать методы теории групп перестановок.
Предлагаемый подход к задачам восстановления позволяет рассматривать большинство из них с единой точки зрения и применять для их исследования единый метод, основанный на вложении множества к-орбит в алгебру над полем действительных чисел. Этим способом в работе получаются новые результаты как о графах, так и о группах перестановок. Рассмотрим содержание диссертации подробнее.
Одним из способов изучения групп перестановок является сопоставление им тех или иных алгебраических систем. К таким системам относятся
Пусть G=(G,W) - конечная группа перестановок на множестве W мощности п. Действие С продолжается на булеан 2 по правилу: {Zafc.,2^ , ... ,} = O^fjZ^/j -,^1 } , ГДЄ ^6 G,
a z*^f ^/ . Орбиты группы перестановок ( Q , 2W ) обозначим через h0» Kj, ... , Кд. . Таким образом, К^ есть множество, элементами которого служат некоторые подмножества W . Если мощность произвольного представителя орбиты г\с равна k , то ее называют симметризованной к-орбитой группы Q (см. [17]). Далее слово "симметризованная" будем опускать.
Обозначим через С множество всевозможных формальных ли
нейных комбинаций У^,Гс1ч: с коэффициентами rL из поля TR дей
ствительных чисел. Зададим на базисных элементах К. операцию ум
ножения: „
- 5 -Здесь число ^.. равно деленному на мощность орбиты кд количеству пар подмножеств, первое из которых лежит в k- , а второе -в Ц. , таких, что их объединение принадлежит орбите k». Произве-дение произвольных элементов из L определим по линейности. Не-трудно видеть, что тем самым и превращается в конечномерную ассоциативно-коммутативную алгебру над полем 1R . Обозначим через L, орбиту, состоящую из дополнений к элементам орбиты h , и рассмотрим линейный оператор о/: С —*- С , переводящий каждую орбиту пс в с/сА;) = Аа,/; . Алгебру С вместе с фиксированным базисом |к0» пн * ... , W0J и оператором ос t назовем алгеброй орбит группы Q . Независимо это понятие было введено в 1982 году
Симонсом [18]; подробнее об этой работе сказано ниже.
/
Отметим, что в определении чисел #\. можно было бы заменить
объединение на любую другую операцию над подмножествами конечного множества, например, пересечение. Но так как всякая подобная операция выразима через объединение и дополнение, то ничего нового это не даст: структурные константы ЛТ. новой алгебры получаются из .. с помощью ос. . Б частности, пересечению соответствует 'у,. = УҐ s, Этим и объясняется включение оператора of в
0tj ио/СО о/С/)
определение алгебры орбит.
Назовем инвариантом орбит группы QSCG>W) действительнозначную функцию f: 2 -^1R , определенную на подмножествах W $ и такую, что ее значению на элементах всякой орбиты п. совпадают.
/О
Множество всех инвариантов образует алгебру Д относительно операций поточечного сложения и умножения:
(/,+А)(с)= /Сс) + /г(с) , /fjg6 ffit
(4АКО =/СО/гСс), ce2w,
(у/,)(с) = r/(e), reTR.
В 1.2 дается конструктивное построение алгебры й и показывается ее изоморфность С . Как векторные пространства, fl и С сопряжены: Й =(С )* — Нот—(C^IR)' Поэтому fl называется в работе также алгеброй коорбит. В ряде случаев она удобнее алгебры орбит С и их естественно рассматривать параллельно.
Изучению алгебр Л и С посвящена первая глава диссертации. В ее первом параграфе вводятся некоторые предварительные определения и рассматривается одна из возможных интерпретации элементов алгебр орбит и коорбит единичной группы. В полном объеме алгебры Я и С вводятся в 1.2. Следующий параграф 1.3. посвящен примерам; наиболее важный из них - алгебра инвариантов графов. Напомним, что парной симметрической группой Sn =(^,Wfi9 называется группа перестановок, индуцируемая действием сишлетрическои группы St%:s(SntW) на множестве W(!t) всех неупорядоченных пар различных элементов из W. Хорошо известно взаимно-однозначное соответствие между к-орбитами этой группы и n-вершинными графами с
oft) к ребрами (см. [19], с. Ю6 ). Тем самым образующие алгебры С *
nSU)
можно рассматривать как графы, а элементы алгебры коорбит Н * -как инварианты графов, то есть действительнозначные функции, определенные на множестве всех п-вершинных графов и не зависящие от способа нумерации их вершин. Поэтому С п и п * естественно называть алгеброй графов и алгеброй инвариантов графов. Идея построения алгебры графов восходит, по-видимому, к статье А.А.Зыкова [20]. Позднее это понятие возникало в книге [21]; в работах [22 - 25] оно применялось для изучения задач теории графов. Близкая конструкция рассматривалась в статье Д.Ю.Григорьева [26].
Важным инструментом для работы с алгебрами орбит является матрица вложимостей группы перестановок, определяемая следующим образом. Пусть к. и h. - две орбиты группы ( G , 2 ). Выберем в
h. произвольный элемент; количество входящих в него как подмноже-ства элементов из кг обозначим через % и будем называть кратностью вложения орбиты к. в к. . Числа vj образуют квадратную ( N+i , N+1)-матрицу V(Q), называемую в диссертации матрицей вложимостей группы С . Структурные константы Yc алгебры орбит выражаются через кратности вложения:
г/-±с-<Г*">№ . (2)
^ ,0 = 0
где m - мощность произвольного представителя орбиты h . Тем самым изучение алгебры орбит во многом сводится к исследованию свойств матрицы V(C); этому посвящен 1.4. Устанавливаемые соотношения позволяют проводить вычисления в алгебрах fl и С
Для парной симметрической группы кратность вложения Vj равна количеству подграфов графа П , изоморфных Г. (здесь и далее под подграфом графа Г понимается граф, получаемый из Г удалением некоторых ребер; в литературе иногда в этом случае используется термин "суграф"). Матрицу V(SC^ ) назовем матрицей вложимости графов. Первоначально она возникла в работах физиков, посвященных модели Изинга ферромагнетиков [27, 28]. Позднее ее свойства (вне связи с какими-либо алгебрами) изучались в статьях Л.Бордзаккини и К.Пулито [29 - 31]. Полученные ими результаты обобщаются и улучшаются в диссертации.
В 1.5 на основе свойств алгебры орбит усиливается первая теорема Ливингстона-Вагнера; напомним ее формулировку и историю. Группа перестановок С называется ^-однородной, если она имеет единственную симметризованную ^ -орбиту (это определение равносильно обычно используемому в литературе, см. [32]). В своей книге [33] по теории игр фон Нейман и Моргенштерн поставили вопрос:
- 8 -верно ли, что всякая ^-однородная группа Q является и (-1)-однородной? Ответ на него был найден в 1965 году Ливингстоном и Вагнером [34] в виде утверждения:
Пусть число А/к равно количеству к-орбит группы перестановок Q степени п . Тогда справедливы неравнества
%<#,... <А/1п/а (3)
(Здесь [^/2] - наименьшее целое, большее или равное n/2 , например, [3/2] =2.) Эти неравенства (точнее, эквивалентное им высказывание) обычно называется в литературе первой теоремой Ливинг-стона-Вагнера. Ее доказательство в [34] использует теорию характеров симметрических групп. В дальнейшем этот результат передоказывался Виландом [35] теоретико-числовым методом, Берковым и Гобби [36] для случая бесконечного или достаточно большого конечного п с помощью теоремы Рамсея, Кантором [37], Камероном [38, 39] и другими. В 1982 году появилась статья Симонса [18], в которой он улучшается следующим образом:
Множество всех к-орбит группы перестановок Q степени п однозначно определяет все ее ^-орбиты, если й к и к+<ъ . (В качестве гипотезы эта теорема была сформулирована в [36].) Для доказательства Симоне использует алгебру орбит. Однако в [18] отсутствует понятие матрицы вложимостей V( G); использование ее свойств позволяет усилить результат Симонса:
[Теорема А. Пусть п. - произвольная к-орбита груп-пы перестановок Q . Назовем к подорбитой орбиты К. , ее-ли по крайней мере один элемент из nL входит как подмножество в какой-нибудь элемент из к- (другими словами, если V/ >0 ). Тогда множество всех с-подорбит орбиты к- од-нозначно определяет все ее р-подорбиты, если р^Ри p + fek.
- 9 -Si)
В частности, если A^J - количество *f-подорбит орбиты к- ,
"о ** /Wi ^ /V2 ^-..^ '%,, (4)
Если положить здесь k-={V} , то получим результат Симонса, а неравенства (4) превратятся в теорему Ливингстона-Вагнера (3). Фактически в 1.5 доказано более общее утверждение, но чтобы не усложнять изложение, здесь приводится его просто формулируемое следствие. Из результатов 1.5 вытекают также некоторые неравенства для чисел граней заданной размерности симплициальных комплексов.
Перейдем к содержанию второй главы диссертации. Одной из основных проблем теории графов является гипотеза реберного восстановления, поставленная Ф.Харари [40] в 1964 году:
Пусть Г - непомеченный граф с ^ вершинами и m ребрами. Удаляя каждый раз по одному ребру, сопоставим Г набор Н(Г) из m графов с (т>~ / ) ребрами. Набор Н(Г) однозначно определяет исходный граф Г, если гп>4. Несложно перенести ее на к-орбиты:
Пусть К. - произвольная к-орбита группы перестановок ( Q, , W ), а с. 'ss{Ze^2e , ...,ак} - какой-нибудь ее элемент. Удаляя из с. по одной точке г^ , построим набор множеств
Каждый его элемент cj ^{^«А лежит в некоторой ( к--/ )-орбите
h . Тем самым п. соответствует набор орбит H(kc)=<^Ut., U., ... «., J\ У (корректность этого определения легко проверяется). Назовем орбиту h. восстановимой, если она определяется набором Н(к); другими словами, если НСЦО^НСКО^Ф* К. = К. . Требуется найти необходимые и достаточные условия восстановимоети орбит группы Q . Несложно проверить, что для Gi~Sn эта задача совпадает с
- 10 -проблемой реберного восстановления графов. Многие группы имеют невосстановимые орбиты. Например, они есть у всякой циклической группы Ск при h^ (см. 2.1). Анализ примеров невосстановимых орбит позволяет лучше понять трудности, возникающие при попытках доказательства гипотезы Харари.
В 1972 году Л.Ловас заметил [413, что всякий h-вершинный граф с числом ребер )т>> ^0^)/4 , реберно-восстановим. Этот результат был несколько улучшен Шмайхелем в 1975 году [42], а в 1977 году В.Мюллер показал [43], что то же самое справедливо при т> 4+&х> (ml) ~- ^&&n . При ri>-/0 оценка Мюллера улучшает границу Ловаса. Параграф 2.4. настоящей работы посвящен доказательству следующего достаточного условия восстановимости орбит:
Теорема В. Пусть в орбите Кг имеется хотя бы одна подорбита h. такая, что выполняется неравенство
где Z. - количество элементов в орбите h, ,
to} - мощность произвольного представителя из U- , *(j) - номер орбиты, состоящей из дополнений к элементам К- .
Тогда hL восстановима.
Следст вие. Если для орбиты hj справедливо хотя бы одно из неравенств:
с > rt/2 , (7)
тс>4+ &^z. 9 (8)
то она восстановима. В частности, все к-орбиты группы Q восстановимы при к > miia п/2 } -І+ %z 1С! } .
- II -
Отметим, что задача восстановления орбит групп перестановок ранее независимо была поставлена Э.М.Лившицем (неопубликованная рукопись [44]), который доказал свошли методами условие (7) и указал для каждого целого числа k > Z группу перестановок степени 2к, обладающую невосстановимыми к-орбитами. Тем самым неравенство (7), вообще говоря, неулучшаемо: равенство достигается, например, на невосстановимых орбитах групп S^ , Cg, группы вращений 3-мерного куба и др. Неулучшаемо и (8); здесь равенство достигается на 3-орбитах циклической группы Cg.
В случае Q -3^ условия (7) и (8) совпадают соответственно с результатами Ловаса и Мюллера. Формула (6) существенно улучшает их. Например, для 5-вершинных графов неравенство Мюллера позволяет заключить, что реберно-восстановими все графы с числом ребер т><8, а оценка Ловаса утверждает то же самое для m> 6". Как показывают вычисления, теорема В позволяет распознать восстановимость всех графов с т>^" и трех графов с т«-4 ; всего с ее помощью восстановимо 68% графов на 5 вершинах, причем доля восстановимых графов увеличивается с ростом числа вершин. Это представляет интерес в связи с тем, что восстановимость h-вершинных графов с гщ ребрами, где 4 ^ т 4 n , к настоящему времени установлена, и доказательства гипотезы Харари равносильно улучшению оценок типа Ловаса-Мншлера до »т> > n . Однако детальный анализ формулы (6) выходит за рамки этой работы. Из теоремы В вытекают и другие результаты о графах: например, показывается восстановимость соединения графов (следствие 2.4.6 ) и исследуется структура невосстановимых графов, не вложимых в свои дополнения (следствия 2.4.3" и 2.4.5" ).
Исторически проблеме реберного восстановления в теории графов предшествовал ее вершинный вариант - гипотеза Улама-Келли:
При г\^3 всякий h-вершинный граф Г однозначно определяет-
- 12 -ся набором подграфов, получаемых поочередным удалением вершин вместе со всеми инцидентными им ребрами. Б 2.1 она обобщается на орбиты следующим образом (с этого момента условимся считать группу Q транзитивной):
Выберем и зафиксируем hrv-орбиту h.«{c//c^ ...,^} группы перестановок Q ; элементы этой орбиты обозначены через С1 ( /?= I, 2, ... , ). Пусть к- - произвольная к-орбита той же группы, и с/* - один из ее элементов. Построим набор множеств
< с?\ е,« с W.с« .... С^Ч с« > . О)
Каждый его элемент лежит в некоторой орбите к !' ; . Тем самым к-сопоставляется набор Ц(^у) — <С к V , к*'1*...3 к.'' ' >, причем легко видеть, что он не зависит от выбора элемента с'&*.
Как показано в 2.1, если Q -«?п , а к. соответствует графу Ki h . , то задача восстановления орбит по набору [J. совпадает с проблемой Улама-Келли. Взяв Ь.-^Аі//ґ ,, приходим к восстановлению графа Г по подграфам, получаемым удалением сразу с различных вершин вместе с инцидентными им ребрами. Выбирая в качестве kL иные графы, будем получать задачи восстановления, не рассматривавшиеся, насколько это известно автору, ранее в литературе.
Согласно договоренности, группа Q транзитивна, значит у нее единственная 1-орбита kf={0^},{4j}>-«- >{**]}. Заметим, что иЛ к- ) отличается от набора Н(к-) » определяемого формулой (5), только, быть может, вхождениями орбиты к; . Это наводит на мысль обозначить через Н-(к-) набор, получаемый из Ц-(к-) удалением всех к. . Задачи восстановления орбит по наборам Uc и И назовем соответственно слабым и сильным восстановлением по модулю орбиты к. (или к.-восстановлением). Слабые задачи аналогичны проблеме Улама-Келли, а сильные - проблеме Харари. Выше уже рас-
- ІЗ -
сматривалось сильное h -восстановление.
Естественно возникает вопрос о переносе теоремы В на случай сильного восстановления по модулю орбиты п. » nY. В общем это достаточно сложно. Однако для орбит r\ , никакие два элемента которых не пересекаются (что возможно, если группа G импримитивна), такое обобщение получено в 2.5. Примером задач подобного типа служит восстановление смешанных графов; для него устанавливаются неравенства типа Ловаса-Мюллера (следствие 2.5.6).
Параграф 2.3 посвящен слабому восстановлению. В нем использу
ется следующее усиление понятия восстановимости. Назовем орбиту
ковосстановимой по модулю h. (или п.-ковосстановимой), если
кратности ее вложений в орбиты с одинаковыми наборами U- совпа
дают: : :
В частности, граф Г вершинно-ковосстановим, если во всяких двух графах с совпадающими наборами вершинно-исключенных подграфов число подграфов, изоморфных Г, одинаково. Доказано (см. утверждение 2.3.3), что h -ковосстановимая орбита к-восстановима.
Вершинная воостановимость графов с изолированными вершинами очевидна. Утверждение об их ковосстановимости называется в литературе леммой Келли; впервые оно было доказано в [45]. Там же была показана воостановимость несвязных графов; затем этот результат неоднократно передоказывался [46 - 49]. Ковосстановимость несвязных графов была впервые установлена Таттом [50, 51] в 1977 году, Его доказательство основано на свойствах дихроматического многочлена и довольно сложно; простые доказательства, использующие алгебру графов, были даны в 1982 году независимо Кокеем [24] и автором [74] . Аналоги всех перечисленных результатов справедливы и для к-орбит. Для их формулировки необходимо прежде всего ввести для
- 14 орбит понятие связности. Этому посвящен параграф 2.2, где каждой паре орбит сопоставляется гиперграф. Напомним определения (см. [52]).
Гиперграфом называется пара ( V , Е ), где V - непустое конечное множество вершин, а - семейство непустых подмножеств
, называемых гиперребрагли. (Кроме того, обычно считается, что обединение всех гиперребер совпадает с множеством вершин. Здесь этого не требуется.) Когда мощность каждого гиперребра равна двум, гиперграф превращается в граф (возможно, с кратными ребрами). Два гиперграфа Vt=*(\ft) и Ч%? =(V$') изоморфны, если между множествами их вершин существует биекция р ' V~^V такая, что образ всякого гиперребра из (при естественном продолжении р на 2 ) является гиперребром в S5f'. Если V s V , '^ , то называется подгиперграфом гиперграфа ^. Гиперграф связен, если всякие его две вершины можно соединить цепочкой пересекающихся гиперребер, и несвязен в противном случае. Максимальный связный подтиперграф в У называется его компонентой связности. Будем называть г -полньм такой гиперграф S5*7, у которого семейство гиперребер состоит из всех v -элементных подмножеств множества вершин
, и любые два таких подмножества входят в одинаковое число раз. Если значение г несущественно, будем говорить просто о полном гиперграфе.
Как и при построении набора (9), зафиксируем орбиту к. группы G . Выберем в к-орбите к. той же группы какой-нибудь эле-мент Cf)={iL^ftiz^I...tz^t^ и с помощью 1а. сопоставим ему следующим образом гиперграф V5?ft}. В качестве его вершин возьмем все z-элементов орбиты Ц —{cijcz?> -">czlfi Чтобы построить гиперреб-ра, каждой из к точек U«0 с/ сопоставим множество —
г у
—{с'<;Ц|2л%(С у тех элементов из" Ц , в которые эта точка вхо-
- 15 -дит. Набор -<^Sf^lf ...,^> возьмем в качестве семейства гиперребер для Vj . Можно показать (см. утверждение 2.2.1), что гиперграфы, отвечающие различным элементам из к. , изоморфны. Назовем V.*\ рассматриваемый с точностью до изоморфизма, гипергра-
фом по модулю к .орбиты U. .
Если С, ~SH , то гиперграфы по модулю К, n_i оказываются обычными графами, соответствующими орбитам группы S^ . Существенное отличие графов от гиперграфов орбит состоит в том, что разным орбитам могут отвечать изоморфные гиперграфы; примеры этого приведены в 2.2.
Теперь основные результаты параграфа 2.3 (теоремы 2.3.-/ и 2.3.2 ) можно сформулировать так:
Теорема С. Пусть гиперграф 5К' несвязен, причем по крайней мере одна из его компонент связности - полный гиперграф. Тогда орбита In. ковосстановима по модулю к. . Если класс изоморфизма гиперграфа Щу однозначно определяет орбиту п- , то для ее k.-ковосстановимости достаточно несвяз-нос ти
Отсюда немедленно следуют приведенные выше результаты Татта и Кел-ли. С помощью теоремы С получается также новое достаточное условие реберной восстановимости графов (утверждение 2.3.5 ), и простое доказательство вершинной восстановимости хроматического многочлена и числа графа (утверждение 2.3.? ). Из результатов 2.3 вытекает равносильность гипотезы Улама-Келли утверждению:
Алгебра L * п-вершинных графов при ъ^З порождается как кольцо несвязными графами.
Основные результаты диссертации опубликованы в \7к\ -[79] .> Они докладывались на четвертом Одесском научно-исследовательском семинаре по графам, гиперграфам и алгебраическим системам (сен-
тябрь 1980 г.), П Всесоюзной школе-семинаре по дискретной оптимизации в Вадул-луй-Водэ (сентябрь 1983 г.), на региональных циклах заседаний научно-исследовательского семинара по комбинаторной математике при Самаркандском госуниверситете им. А.Навои (октябрь 1983 и 1984 гг.), семинарах по теории графов в Институте проблем управления (Москва, март 1984 г.), в Белорусском госуниверситете (Минск, май 1984 г.), в Кишиневском госуниверситете игл. В.И.Ленина; семинарах по теории групп перестановок в Институте системных исследований (Москва, март 1984 г.), Киевском госуниверситете им. Т.Г.Шевченко (апрель 1984 г.); на алгебраическом семинаре Института математики с ВЦ АН MCGP.
Автор благодарен участникам перечисленных семинаров за замечания, способствовавшие улучшению работы. Он особенно признателен А.З.Зеликовскому, А.А.Иванову, кандидатам физико-математических наук А.К.Кельмансу и В.А.Уфнаровскому за проявленное внимание.
диссертация выполнена под руководством д.ф.-м.н., профессора А.А.Зыкова; автор глубоко благодарен ему за постоянную поддержку.
Примеры. Алгебра инвариантов графов
Изучению алгебр Л и С посвящена первая глава диссертации. В ее первом параграфе вводятся некоторые предварительные определения и рассматривается одна из возможных интерпретации элементов алгебр орбит и коорбит единичной группы. В полном объеме алгебры Я и С вводятся в 1.2. Следующий параграф 1.3. посвящен примерам; наиболее важный из них - алгебра инвариантов графов. Напомним, что парной симметрической группой Sn =( ,Wfi9 называется группа перестановок, индуцируемая действием сишлетрическои группы St%:s(SntW) на множестве W(!t) всех неупорядоченных пар различных элементов из W. Хорошо известно взаимно-однозначное соответствие между к-орбитами этой группы и n-вершинными графами с к ребрами (см. [19], с. Ю6 ). Тем самым образующие алгебры С nSU) можно рассматривать как графы, а элементы алгебры коорбит Н -как инварианты графов, то есть действительнозначные функции, определенные на множестве всех п-вершинных графов и не зависящие от способа нумерации их вершин. Поэтому С п и п естественно называть алгеброй графов и алгеброй инвариантов графов. Идея построения алгебры графов восходит, по-видимому, к статье А.А.Зыкова [20]. Позднее это понятие возникало в книге [21]; в работах [22 - 25] оно применялось для изучения задач теории графов. Близкая конструкция рассматривалась в статье Д.Ю.Григорьева [26].
Важным инструментом для работы с алгебрами орбит является матрица вложимостей группы перестановок, определяемая следующим образом. Пусть к. и h. - две орбиты группы ( G , 2 ). Выберем в h. произвольный элемент; количество входящих в него как подмноже-ства элементов из кг обозначим через % и будем называть кратностью вложения орбиты к. в к. . Числа vj образуют квадратную ( N+i , N+1)-матрицу V(Q), называемую в диссертации матрицей вложимостей группы С . Структурные константы Yc алгебры орбит выражаются через кратности вложения: где m - мощность произвольного представителя орбиты h . Тем самым изучение алгебры орбит во многом сводится к исследованию свойств матрицы V(C); этому посвящен 1.4. Устанавливаемые соотношения позволяют проводить вычисления в алгебрах fl и С
Для парной симметрической группы кратность вложения Vj равна количеству подграфов графа П , изоморфных Г. (здесь и далее под подграфом графа Г понимается граф, получаемый из Г удалением некоторых ребер; в литературе иногда в этом случае используется термин "суграф"). Матрицу V(SC ) назовем матрицей вложимости графов. Первоначально она возникла в работах физиков, посвященных модели Изинга ферромагнетиков [27, 28]. Позднее ее свойства (вне связи с какими-либо алгебрами) изучались в статьях Л.Бордзаккини и К.Пулито [29 - 31]. Полученные ими результаты обобщаются и улучшаются в диссертации.
В 1.5 на основе свойств алгебры орбит усиливается первая теорема Ливингстона-Вагнера; напомним ее формулировку и историю. Группа перестановок С называется -однородной, если она имеет единственную симметризованную -орбиту (это определение равносильно обычно используемому в литературе, см. [32]). В своей книге [33] по теории игр фон Нейман и Моргенштерн поставили вопрос: -верно ли, что всякая -однородная группа Q является и (-1)-однородной? Ответ на него был найден в 1965 году Ливингстоном и Вагнером [34] в виде утверждения:
Пусть число А/к равно количеству к-орбит группы перестановок Q степени п . Тогда справедливы неравнества, Здесь [ /2] - наименьшее целое, большее или равное n/2 , например, [3/2] =2.) Эти неравенства (точнее, эквивалентное им высказывание) обычно называется в литературе первой теоремой Ливинг-стона-Вагнера. Ее доказательство в [34] использует теорию характеров симметрических групп. В дальнейшем этот результат передоказывался Виландом [35] теоретико-числовым методом, Берковым и Гобби [36] для случая бесконечного или достаточно большого конечного п с помощью теоремы Рамсея, Кантором [37], Камероном [38, 39] и другими. В 1982 году появилась статья Симонса [18], в которой он улучшается следующим образом:
Множество всех к-орбит группы перестановок Q степени п однозначно определяет все ее -орбиты, если й к и к+ ъ . (В качестве гипотезы эта теорема была сформулирована в [36].) Для доказательства Симоне использует алгебру орбит. Однако в [18] отсутствует понятие матрицы вложимостей V( G); использование ее свойств позволяет усилить результат Симонса:
Пусть п. - произвольная к-орбита груп-пы перестановок Q . Назовем к подорбитой орбиты К. , ее-ли по крайней мере один элемент из nL входит как подмножество в какой-нибудь элемент из к- (другими словами, если V/ 0 ). Тогда множество всех с-подорбит орбиты к- од-нозначно определяет все ее р-подорбиты.
Усиление теоремы Ливингстона-Вагнера
Следующий пример очень важен для дальнейшего изложения и будет постоянно использоваться.
Пример 1,3.3. (Алгебра инвариантов графов). Напомним некоторые определения. Графом Г (без петель и кратных ребер) называется пара (W,E), где 1 =(4 2 } непустое конечное множество вершин, a "={er ,..vem}c l /w_ ьшо жество неупорядоченных пар элементов из W ; каждая такая пара называется ребром. Если = W г\ то граф называется полным и обозначается через Kh . Два графа Т СУ,В) И T=CWl ) изоморфны, если между множествами их вершин можно установить такое взаимно-однозначное соответствие jp:W- "W t что пара 0 ( ) j является ребром графа Г тогда и только тогда, когда (} -ребро в Г , Изоморфизм графа Г на себя называется автоморфизмом; множество всех автоморфизмов образует группу Hu(V). Сопоставим каждой вершине графа Г точку на плоскости, а каждому ребру - линию, соединяющую соответствующие точки. Тем самым Г отвечает геометрический объект, топологические свойства которого зависят только от класса изоморфизма графа. Поскольку изоморфные графы отличаются лишь метками на вершинах, то классы изоморфизма называют также непомеченными графами. В дальнейшем под графом Г всегда понимается класс изоморфизма; входящие в него помеченные графы будут обозначаться через "г . Известно (см. [ /] , с. 2//), что в классе Г всего 1/\йчіТ\ помеченных графов.
В основе теории перечисления графов лежит следующая связь между графами и орбитами. Пусть S - симметрическая группа перестановок множества S{4 J-) }. Определим действие S на множестве F-W всех неупорядоченных пар различных элементов из IV , по правилу: l2 ;,7 = {2 1,7 л}» где seS . Получаемая при этом группа перестановок =( ,1 1) называется парной симметрической группой ([19], с. 106), На S можно смотреть как на группу перестановок ребер полного графа K"h , индуцированную всевозможными перенумерациями его вершин. Например, если занумеровать вершины и ребра К4 так, как показано на рисунке : то перестановка вершин (г%ъ?9г )еЗп порождает перестановку ребер =(е.ЄгЄлХеге+Єс) е Sc" , и т.д. Пусть Ь.= [сг\с..., ;}- одна из m-орбит группы Sb . Каждый ее элемент 0/ = ( , ,..., определяет помеченный граф, образуемый ребрами , Єи , ... , Wm . Граф, соответствующий другому элементу этой же орбиты, отличается от первого только нумерацией вершин. Поэтому между классами изоморфизма h--вершинных графов с m ребрами и пл-орбитами группы о п существует взаимно-однозначное соответствие. Для случая п=4 и приведенной на рисунке нумерации ребер графа К оно выглядит
Таким образом, можно считать, что элементами алгебры орбит С h служат всевозможные формальные линейные комбинации "кТТ, суммирование в которых проводится по всем непомеченным п -вер nSa шинным графам. Будем называть и п алгеброй графов.
Как известно, на множестве графов определены многочисленные операции: дополнение, декартово произведение, соединение, и др. В то же время результат многих естественных преобразований графа определен неоднозначно. Таковы, например, процедуры удаления вершины или ребра, возникающие в формулировках гипотез Улама-Келли и Харари о восстановлении (см. 2.1). Понятие алгебры орбит позволяет рассматривать подобные преобразования как операторы так, как это делалось в 1.1 для алгебры подмножеств. Применению такого подхода к задачам восстановления посвящена вторая глава диссертации.
Выясним смысл элементов алгебры коорбит /} . Вспомним, что согласно определению 1.2.3, инвариантом орбит группы G=CG, Ю называется всякая действительнозначная функция, определенная на подмножествах W и такая, что на элементах любой орбиты ее значения совпадают. Отсюда получим, что инвариантом орбит группы оп являются функции, определенные на множестве всевозможных помеченных h-вершинных графов, и принимающие одинаковые значе - 39 -ния на изоморфных графах. Подобные функции в литературе называют инвариантами графов (см. [і], с. Z6 ). Поэтому R естественно называть алгеброй инвариантов графов.
Несложно выявить теоретико-графовый смысл и других введенных ранее понятий. Например, лемма 1.2.I позволяет утверждать, что кратность вложения j орбит группы Sb равна числу подгра -фов графа Tj , изоморфных Т? . Другими словами, для вычисления y необходимо зафиксировать некоторую нумерацию верпин графа и подсчитать число таких подмножеств его ребер, что образуемый ими граф изоморфен TJ . Пользуясь формулой (1.2.15), можно вычислить структурные константы fc? . Однако умножению графов в С п можно придать более наглядный смысл, рассматривая каждый элемент соответствующей орбиты как помеченный граф. Пусть Т -Cty v) и V - СК ЕЛ - два помеченных графа на одном и том же множестве вер-шин W. Назовем их наложением помеченный граф (W, ЕсиЕЛ, всякое ребро которого входит по крайней мере в один из TJ или Т? . Если считать помеченные графы элементами булеана (2-2 , то наложению соответствует объединение множеств. Поэтому для нахождения структурных констант # .. нужно:
Ковосстановление несвязных орбит
Известен ряд обобщений проблем восстановления. Во-первых, они формулируются для объектов, отличных от графов (например, для орграфов, гиперграфов, бесконечных графов, отношений, матро-идов, и др.). Кроме того, рассматривается восстановление графов по наборам, отличным от (J и Н (по элементарным стягиваниям и гомоморфным образам, остовным деревьям, и т.д., см [5]). В любом случае схема задачи восстановления такова:
Пусть X - множество элементов произвольной природы. Известен закон f , ставящий в соответствие каждому элементу х G X набор (х) ={х{ ос , ос t .,. у элементов того же множества. Введем на X отношение эквивалентности (Р , полагая ос 555 , если наборы /Ссс) и /Су) совпадают;
Элемент «эсе X называется восстановимым, если класс эквивалентности, в который он входит, состоит только из него самого, и невосстановимым в противном случае. Требуется найти необходимые и достаточные условия восстановимое элемента эс.
Ни для одной из перечисленных ранее задач восстановления окончательного решения не найдено, хотя для проблем Улама и Ха-рари установлены многочисленные достаточные условия восстанови-мости. Во многих задачах возникают невосстановимые элементы; в частности, гипотеза Улама для орграфов была опровергнута в 1977г. П.Стокмейером [7, 8].
Б этом параграфе формулируется ряд задач восстановления орбит групп перестановок, частными случаями которых являются проблемы вершинного и реберного восстановления графов. При этом приводится только способ построения набора орбит; формулировка соответствующей задачи получается из приведенной выше схемы. В дальнейшем группа Q считается транзитивной. Это ограничение вызвано удобством изложения.
Займемся сначала обобщением проблемы Харари, как наиболее простым и играющем в дальнейшем главную роль. Пусть h. = {c , С , ... , С - произвольная к -орбита транзитивной группы перестановок Q . Выберем произвольный ее элемент С/ = 12 , 2ь , ... , 2с 1 и образуем набор из к его подмно-жест мощности (К-"/ ): Каждое множество / (2 Л входит в некоторую ( К- 4)-орбиту К - группы С, . Тем самым каждой орбите к. соответствует набор U(U.) — \]n-, ІП , ... , к- / . Если взять G= S и вспомнить результаты 1.3 о связи графов с орбитами парной симметрической группы, можно заметить совпадение набора Н с набором (2.1.2) в формулировке гипотезы Харари. Поэтому задача восстановления орбиты по ее набору Н действительно является обобщением Пусть к - какая-нибудь {К-і )-орбита группы G . Из опре-деления кратности вложения следует, что Кк входит в набор И (к-) ровно V? раз. Значит, эквивалентным орбитам соответствуют одина-ковые столбцы в матрице VK_i к . В силу утверждения 1.4.6, те же столбцы совпадают во всех матрицах V0)K , Vr , ... , VK_/)K Таким образом, проблема восстановления орбит группы С сводится к поиску одинаковах столбцов в матрице V(C) — Г . Напомним (см. введение), что группа перестановок ( С, ,W ) называется к-однородной, если она транзитивно действует на множестве W всех к-элементных подмножеств W . Другими словами: если у группы G ровно одна к-орбита. Таким образом, для к-однородной группы С все матрицы VQ C) , V1k+I (О , ... , VKtK+, СС) являются строками. Так как сумма элементов в любом столбце матрицы V „(С) равна ( ) (см. тождество (1.4.4)), то все ( К+-/)-орбиты к-однородной группы G эквивалентны. Назовем этот класс эквивалентности тривиальным. Непосредственные вычисления показывают, что кроме тривиально эквивалентных, все орбиты групп En , on , циклических групп Сп при h 5 и диэдральных групп Dh при п 7 восстановимы. Однако отсутствие эквивалентных орбит у группы перестановок является скорее исключением, чем правилом. Например, на рисунке ниже приведено по одному представителю каждой из 3-орбит циклической Покажем, что и все группы Сп при п 6 имеют невосстановимые орбиты. Напомним, что цикловым индексом Z ( G ; St , S% , ... , Sn ) группы перестановок G называется многочлен от П переменных Он широко используется для решения задач перечисления, поскольку из теоремы Пойа ( [19], с. 49) следует, что где А/х - количество к-орбит группы Q . Выражение в левой части этой формулы обычно обозначается через Теорема 2.1.1. Пусть Q - к-однородная группа перестановок. Если у нее существует надгруппа / G такая, что то С имеет нетривиальные эквивалентные орбиты. Доказательство. Поскольку /7 - надгруппа Q , то всякая орбита группы Р переходит в себя под действием любой перестановки из С, , и следовательно, есть объединение орбит G . Отсутствие в правой части (2.1.5) члена показывает, что все m-орбиты группы Q являются также и орбитами группы F ; в част - 70 -ности, это так при т к- --/1. Обозначим через с к+і наименьший показатель степени -6 , встречающийся в правой части (2.1.5). Тогда /f-орбит группы С больше, чем /-орбит группы Р , и значит, некоторая -орбита Us группы Р имеет вид k/=n \}\\JJ-.., где hp fteJ ljeG} и hf((cc») [#G} - орбиты группы а . Выберем из h и Ь. по представителю с/ и ci . Так как оба этих элемента лежат в одной орбите группы Р , они переводятся друг в друга действием некоторой перестановки ye Р : cf—Cc ) . Пусть теперь h -коорбита группы Q , причем арность пл. этой коорбиты меньше вгп =щ- . Согласно (2.1.5), К является одновременно и коорбитой группы Р . Учитывая это, вычислим кратности вложения і?- и " :
Восстановление орбит импримитивных групп
Вершина гиперграфа называется изолированной, если она не входит ни в одно гиперребро. Договоримся обозначать число J . \ изолированных вершин гиперграфа Vcj через Pj , а число вершин, принадлежащих гиперребрам - через т\ ; таким образом, rnj i p(-J = = z. . При = 9 форглула (2.2.2) превращается в выражение (1.4.6) для величины "i J . Поэтому имеет место Следствие 2.2.2. Число J3/ изолированных вершин в гиперграфе Щ равно v,r .
Очевидно, что если в VCj есть изолированные вершины (т.е., "VjfC) 0 ), то орбита \г\. несвязна по модулю la. . Понятие несвязной орбиты будет существенно использоваться в следующем параграфе; там же понадобится Утверждение 2.2.3. Пусть Г - связный граф, а М - мо дуль , отличный от графов 2 » 2 3 2» Тогда гиперграф по модулю М графа Г либо связен, либо имеет изолированные вершины, доказательство. Очевидно, что если граф Г связен, то для каждой пары Ц, , ? его ребер найдется последователь ность е , ?ь/ е«0 ребер такая, что у _ и v есть общая верпина для всякого - = 1, 2, ... , t- / . Каждому из ребер в гиперграфе соответствует гиперребро % . Покажем, что если модуль М удовлетворяет условию утверждения, то общая вершина есть и у каждой пары гиперребер е и ? Это возможно только если ffir связен или имеет изолированные вершины; тем самым утверждение будет доказано.
Заметим, что имеющий хотя бы одно ребро граф М отличен от -Pg , 2P2 , 3P2 , ... тогда и только тогда, когда в нем есть пара смежных ребер. Зафиксируем такую пару в М, и будем называть ее вилкой. Согласно определению, вершины гиперграфа У г представляют собой всевозможные вложения модуля М в полный граф К . (Напомним, что вложение графа Гу в Т% - это такое множество ребер в Го, что образуемый ими граф изоморфен IV; вложения графа в Kh являются элементами орбиты, соответствующей этому графу.) Легко видеть, что для любой пары смежных ребер в Кл наіідется вложение М в Кл , совмещающее выбранную вилку с этой парой. В частности, каждая пара ребер е , . ,,( =1 А ?,..., if-/ ) графа Г входит по крайней мере в одно вложение модуля М в Kh. Соответствующая вершина гиперграфа Vz , принадлежит каждому из гиперребер V , , поскольку по определению гиперребро є а состоит из всех вложений, включающих в себя ребро е . Итак, ft6 "4 0 для всех Ч,- /, Z , ... , -/ , и утверждение до-казано. Автор благодарен А.З.Зеликовскому, обратившему его внимание на это свойство гиперграфов.
Замечание 2.2.1. Посмотрим, как связаны между собой гиперграф 5f/ орбиты U. и гиперграфы орбит из ее Ь.-на-бора и.(к)={к / \ка г\ ... ,1 ) (см. (2.1.7)). Пользуясь определениями, нетрудно заметить, что гиперграф по модулю hL орбиты Uі получается из V2y удалением всех гиперребер, инцидентных вершине с номером k . Это подтверждает аналогию между задачами вершинного восстановления графов и слабого восстановления орбит.
Замечание 2.2.2. Выясним, как устроены гиперграфы орбит, входящих в разложение U.U— / Jf... Ь, с ненулевыми коэффи-циентами f. . Из определений следует, что гиперграф всякой ор-биты Up получается при наложении помеченного гиперграфа 9 f -на некоторый помеченный гиперграф Я , точно так же, как это ранее делалось в примере 1.3.3. Мы воспользуемся этим при доказательстве теоремы 2.3.1.
Как было замечено ранее, если орбита имеет по некоторому модулю изолированные вершины, то она слабо-восстановима по этому модулю. Настоящий параграф посвящен усилению этого утверждения. Напомним (см. конец 2.1), что далее k-восстановление означа-ет слабое восстановление по модулю k , а восстановление -сильное к -восстановление. Эта договоренность относится и ко всем остальным понятиям, связанным с восстановимостью.
Пусть и±(Ь;) - k-набор орбиты ь- . Каждой орбите кК поставим в соответствие число U -к , равное количеству вхождений " в U (k). Квадратная матрица Ц—С Л) , составленная из этих чисел, полностью определяет закон построения к- набора, а значит, и соответствующую задачу восстановления. Величины U;K можно выразить через кратности вложений орбит. Утверждение 2.3.1. Число орбит кк в k-наборе орбиты U. равно Доказательство. Из определения k-набора следует, что число UjK равно количеству элементов набора множеств лежащих в орбите h . Выражая операцию разности множеств через пересечение и дополнение, получим, что cf\Cf=:cy}f)Cgi Поэтому U:K есть "число элементов в (- , пересечения которых с произвольным фиксированным элементом орбиты lv. принадлежат орбите Согласно утверждению 1.2.4, это число равно Вторая часть формулы (2.3.1) вытекает из соотношений (1.4.12), (1.4.7) и стандартных преобразований:
