Алгебра инвариантов и восстановление к-орбит группы перестановок тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

ВВЕДЕНИЕ.

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

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

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

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

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

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

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

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

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

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

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

§ 4. Восстановление орбит большой арности.

§ 5. Восстановление орбит импримитивных групп.

Во многих разделах алгебры естественно появляется задача: определяется ли алгебраическая система своими подсистемами? Подобные проблемы в теории графов известны как гипотезы Улама-Келли и Хара-ри о вершинном и реберном восстановлении (формулировки приведены ниже). К настоящему времени их справедливость установлена в ряде частных слечаев, однако окончательного решения проблем не найдено (см. [I] и обзоры [2 - 6]). Изучаются также другие задачи восстановления графов, и распространения их на иные классы объектов (орграфы, гиперграфы, отношения, матроиды и др.). При этом, с одной стороны, ряд теорем о восстановлении графов оказывается справедливым и для орграфов, а с другой - гипотеза вершинного восстановления для последних была опровергнута в 1977 году П.Стокмейером [7, 8]. Возникает вопрос: нельзя ли продолжить задачи восстановления на достаточно широкий класс объектов так, чтобы дая них существовали аналоги возможно большего числа утверждений о графах?

В диссертации проблемы восстановления переносятся на симмет-ризованные к-орбиты произвольной конечной группы перестановок. При этом различным группам соответствуют случаи графов, орграфов, реберно-регулярных гиперграфов, ожерелий и т.д., а различным видам задач восстановления - проблемы Улама, Харари, и некоторые другие. Многие группы перестановок обладают невосстановимыми орбитами. В то же время в работе показано, что ряд результатов о графах (например, теоремы Гринуэлла, Ловаса, Мюллера, Татта, лемма Келли) справедлив для к-орбит любых групп. Это означает невозможность доказательства гипотез Улама и Харари на основе только подобных утверждений. Можно предположить, что для решения проблем восстановления необходимо использовать методы теории групп перестановок.

Предлагаемый подход к задачам восстановления позволяет рассматривать большинство из них с единой точки зрения и применять для их исследования единый метод, основанный на вложении множества к-орбит в алгебру над полем действительных чисел. Этим способом в работе получаются новые результаты как о графах, так и о группах перестановок. Рассмотрим содержание диссертации подробнее.

Одним из способов изучения групп перестановок является сопоставление им тех или иных алгебраических систем. К таким системам относятся «S"-кольца Шура групп перестановок [9], их V-кольца [10, II], ассоциативные схемы [12], универсальные алгебры Красне-ра [13 - 15], алгебры антирефяексивных отношений (ЙК -алгебры) [16] и некоторые другие. В диссертации вводится новый подобный объект - алгебра орбит, которая строится следующим образом.

Пусть Q=(G,W) - конечная группа перестановок на множестве W мощности п. Действие Q продолжается на бдеан по правилу: •• • » ГДе а ь)^ е W . Орбиты группы перестановок ( Q , 2W ) обозначим через h0» kj, . , h^ . Таким образом, есть множество, элементами которого служат некоторые подмножества W . Если мощность произвольного представителя орбиты равна к , то ее называют симметризованной к-орбитой группы G (см. [17]). Далее слово "симметризованная" будем опускать.

Обозначим через С^ множество всевозможных формальных линейных комбинаций he ° коэффициентами г, из поля 1К действительных чисел. Зададим на базисных элементах U. операцию умножения: „

К Ц = 12 К, К • (1)

J е=о У €

Здесь число равно деленному на мощность орбиты количеству пар подмножеств, первое из которых лежит в UL , а второе в Ц. , таких, что их объединение принадлежит орбите К». Произве

J Г^ дение произвольных элементов из L определим по линеиности. Не

PG трудно видеть, что тем самым и превращается в конечномерную ассоциативно-коммутативную алгебру над полем 1R . Обозначим через kjr орбиту, состоящую из дополнений к элементам орбиты h , и

Q G *" рассмотрим линейный оператор о/: С —С , переводящим каждую орбиту h- в d(h-) = h. Алгебру С вместе с фиксированным базисом -[Iv h-f » ••• »Ку} и °ператором ol t назовем алгеброй орбит группы Q . Независимо это понятие было введено в 1982 году

Симонсом [18]; подробнее об этой работе сказано ниже.

Отметим, что в определении чисел можно было бы заменить J объединение на любую другую операцию над подмножествами конечного множества, например, пересечение. Но так как всякая подобная операция выразима через объединение и дополнение, то ничего нового это не даст: структурные константы X. новой алгебры получаются У из ^ с помощью ос . Б частности, пересечению соответствует

• Этим и объясняется включение оператора с/ в определение алгебры орбит.

Назовем инвариантом орбит группы G^CG^W) действительнозначную функцию 2^-^JR , определенную на подмножествах W , и такую, что ее значению на элементах всякой орбиты к. совпадают. О

Множество всех инвариантов образует алгебру fl относительно операций поточечного сложения и умножения: № + . /г « (4А)(о) = , се

В §1.2 дается конструктивное построение алгебры и показывается ее изоморфность С^ . Как векторные пространства, и сопряжены: flG=(CG)*— Hom^CcflR)» Поэтому называется в jk работе также алгеброй коорбит. В ряде случаев она удобнее алгебры орбит С^ и их естественно рассматривать параллельно.

Изучению алгебр Л^ и С^ посвящена первая глава диссертации. В ее первом параграфе вводятся некоторые предварительные определения и рассматривается одна из возможных интерпретаций элементов алгебр орбит и коорбит единичной группы. В полном объеме Q pG алгебры Я и С вводятся в §1.2. Следующий параграф 1.3. посвящен примерам; наиболее важный из них - алгебра инвариантов графов. Напомним, что парной симметрической группой называется группа перестановок, индуцируемая действием симметрической группы W) на множестве W(!t) всех неупорядоченных пар различных элементов из W. Хорошо известно взаимно-однозначное соответствие между к-орбитами этой группы и п-вершинными графами с к ребрами (см. [19], с. 106 ). Тем самым образующие алгебры С * nSU) можно рассматривать как графы, а элементы алгебры коорбит И п -как инварианты графов, то есть действительнозначные функции, определенные на множестве всех п-вершинных графов и не зависящие rSU) nSa) от способа нумерации их вершин. Поэтому L п и п * естественно называть алгеброй графов и алгеброй инвариантов графов. Идея построения алгебры графов восходит, по-видимому, к статье А.А.Зыкова [20]. Позднее это понятие возникало в книге [21]; в работах [22 - 25] оно применялось для изучения задач теории графов. Близкая конструкция рассматривалась в статье Д.Ю.Григорьева [26].

Важным инструментом для работы с алгебрами орбит является матрица вложимостей группы перестановок, определяемая следующим образом. Пусть h. и h. - две орбиты группы

G ,2" ). Выберем в к. произвольный элемент; количество входящих в него как подмноже

J * ства элементов из К- обозначим через ^ и будем называть кратностью вложения орбиты к. в к. . Числа vj образуют квадратную ( N+i , N+i )-матрицу V(C )» называемую в диссертации матрицей вложимостей группы Q . Структурные константы fc. алгебры орбит v/ выражаются через кратности вложения:

J р — О где - мощность произвольного представителя орбиты кр . Тем самым изучение алгебры орбит во многом сводится к исследованию свойств матрицы V(C); этому посвящен §1.4. Устанавливаемые соотношения позволяют проводить вычисления в алгебрах fl^ и С^ .

Для парной симметрической группы кратность вложения ^J равна количеству подграфов графа Г. , изоморфных Г. (здесь и далее sj * под подграфом графа Г понимается граф, получаемый из Г удалением некоторых ребер; в литературе иногда в этом случае используется термин "суграф"). Матрицу ) назовем матрицей вложимости графов. Первоначально она возникла в работах физиков, посвященных модели Изинга ферромагнетиков [27, 28]. Позднее ее свойства (вне связи с какими-либо алгебрами) изучались в статьях Л.Бордзаккини и К.Пулито [29 - 31]. Полученные ими результаты обобщаются и улучшаются в диссертации.

В §1.5 на основе свойств алгебры орбит усиливается первая теорема Ливингстона-Вагнера; напомним ее формулировку и историю. Группа перестановок С называется ^-однородной, если она имеет единственную симметризованную ^ -орбиту (это определение равносильно обычно используемому в литературе, см. [32]). В своей книге [33] по теории игр фон Нейман и Моргенштерн поставили вопрос: верно ли, что всякая ^-однородная группа Q является и (£-1)-однородной? Ответ на него был найден в 1965 году Ливингстоном и Вагнером [34] в виде утверждения:

Пусть число равно количеству к-орбит группы перестановок С степени п . Тогда справедливы неравнества </V[n/a. (3)

Здесь ~ наименьшее целое, большее или равное ъ/Z , например, [3/2] =2.) Эти неравенства (точнее, эквивалентное им высказывание) обычно называется в литературе первой теоремой Ливинг-стона-Вагнера. Ее доказательство в [34] использует теорию характеров симметрических групп. В дальнейшем этот результат передоказывался Виландом [35] теоретико-числовым методом, Берковым и Гобби [36] для случая бесконечного или достаточно большого конечного п с помощью теоремы Рамсея, Кантором [37], Камероном [38, 39] и другими. В 1982 году появилась статья Симонса [18], в которой он улучшается следующим образом:

Множество всех к-орбит группы перестановок Q степени п однозначно определяет все ее ^-орбиты, если к и к+^Оч . (В качестве гипотезы эта теорема была сформулирована в [36].) Дяя доказательства Симоне использует алгебру орбит. Однако в [18] отсутствует понятие матрицы вложимостей Y( G); использование ее свойств позволяет усилить результат Симонса:

Теорема А. Пусть к. - произвольная к-орбита груп

V» пы перестановок Q . Назовем к подорбитой орбиты к. , ее

I* J о I ли по крайней мере один элемент из входит как подмножество в какой-нибудь элемент из к- (другими словами, если V/ >0 ). Тогда множество всех ^-подорбит орбиты к- однозначно определяет все ее р -под орбиты, если р^с и р + 6^ к.

В частности, если Nf>J - количество £-подорбит орбиты к. , то

A/Cj) < /V (j)< < /VCj'}

Если положить здесь , то получим результат Симонса, а неравенства (4) превратятся в теорему Ливингстона-Вагнера (3). Фактически в §1.5 доказано более общее утверждение, но чтобы не усложнять изложение, здесь приводится его просто формулируемое следствие. Из результатов §1.5 вытекают также некоторые неравенства для чисел граней заданной размерности симплициальных комплексов.

Перейдем к содержанию второй главы диссертации. Одной из основных проблем теории графов является гипотеза реберного восстановления, поставленная Ф.Харари [40] в 1964 году:

Пусть Г - непомеченный граф с ^ вершинами и m ребрами. Удаляя каждый раз по одному ребру, сопоставим Г набор Н(Г) из m графов с (j ) ребрами. Набор Н(Г) однозначно определяет исходный граф Г, если Несложно перенести ее на к-орбиты:

Пусть Кс - произвольная к-орбита группы перестановок ( С, , W ), а , . - какой-нибудь ее элемент. Удаляя из с/° по одной точке , построим набор множеств Cj^ -К] > eJ'4 (ЧЬ • • •, CJK К Л > • (5)

Каждый его элемент ^/"'^"Г2^} лежит в некоторой ( к--/ )-орбите U . . Тем самым h. соответствует набор орбит .

••» К-*0) (корректность этого определения легко проверяется). Назовем орбиту к. восстановимой, если она определяется набором Н(к); другими словами, если Н(Ц-) ~ Н(Ц)^* К. = . Требуется найти j 1 j необходимые и достаточные условия восстановимоети орбит группы Q , Несложно проверить, что для G -S^J3 эта задача совпадает с проблемой реберного восстановления графов. Многие группы имеют невосстановимые орбиты. Например, они есть у всякой циклической группы при h>6* (см. §2.1). Анализ примеров невосстановимых орбит позволяет лучше понять трудности, возникающие при попытках доказательства гипотезы Харари.

В 1972 году Л.Ловас заметил [413, что всякий h-вершинный граф с числом ребер По > , реберно-восстановим. Этот результат был несколько улучшен Шмайхелем в 1975 году [42], а в 1977 году В.Мюллер показал [43], что то же самое справедливо при m > • При г\оценка Мюллера улучшает границу Ловаса. Параграф 2.4. настоящей работы посвящен доказательству следующего достаточного условия восстановимости орбит:

Теорема В. Пусть в орбите Кг имеется хотя бы одна подорбита Ц. такая, что выполняется неравенство где Z. - количество элементов в орбите к- , j j toj - мощность произвольного представителя из kj , - номер орбиты, состоящей из дополнений к элементам hj . Тогда U. восстановима.

Следст вие. Если для орбиты справедливо хотя бы одно из неравенств:

7)

Iш. , (8) то она восстановима. В частности, все k-орбиты группы Q восстановимы при к > тйа {п/% } IG1} .

- II

Отметим, что задача восстановления орбит групп перестановок ранее независимо была поставлена Э.М.Лившицем (неопубликованная рукопись [44]), который доказал своими методами условие (7) и указал для каждого целого числа k > Z группу перестановок степени 2к» обладающую невосстановимыми к-орбитами. Тем самым неравенство (7), вообще говоря, неулучшаемо: равенство достигается, например, на невосстановимых орбитах групп S™, Cg, группы вращений 3-мерного куба и др. Неулучшаемо и (8); здесь равенство достигается на 3-орбитах циклической группы Cg.

В случае С, -S^ условия (7) и (8) совпадают соответственно с результатами Ловаса и Мюллера. Формула (6) существенно улучшает их. Например, для 5-вершинных графов неравенство Мюллера позволяет заключить, что реберно-восстановимы все графы с числом ребер т><8, а оценка Ловаса утверждает то же самое для 6*. Как показывают вычисления, теорема В позволяет распознать восстановимость всех графов с rn^S и трех графов с me «4 ; всего с ее помощью восстановимо 68% графов на 5 вершинах, причем доля восстановимых графов увеличивается с ростом числа вершин. Это представляет интерес в связи с тем, что восстановимость п-вершинных графов с m ребрами, где 4 ^ п 4 п , к настоящему времени установлена, и доказательства гипотезы Харари равносильно улучшению оценок типа Ловаса-Мншлера до m > п . Однако детальный анализ формулы (6) выходит за рамки этой работы. Из теоремы В вытекают и другие результаты о графах: например, показывается восстановимость соединения графов (следствие 2.4.6 ) и исследуется структура невосстановимых графов, не вложимых в свои дополнения (следствия 2.4.3" и 2.4.5" ).

Исторически проблеме реберного восстановления в теории графов предшествовал ее вершинный вариант - гипотеза Улама-Келли: || При всякий h-вершинный граф Г однозначно определяет

- 12 ся набором подграфов, получаемых поочередным удалением вершин вместе со всеми инцидентными им ребрами. Б §2.1 она обобщается на орбиты следующим образом (с этого момента условимся считать группу Q транзитивной):

Выберем и зафиксируем hrv-орбиту ^.-{е^/с^ ГРУПпы перестановок Q ; элементы этой орбиты обозначены через Сс£° {£=1,2, . ). Пусть к- - произвольная к-орбита той V же группы, и СУ* - один из ее элементов. Построим набор множеств р с,«\ с™ ., с/А С™ > . О)

Каждый его элемент лежит в некоторой орбите . Тем самым сопоставляется набор ~ К к*'1^., kC.t,Z'?), причем легко видеть, что он не зависит от выбора элемента с .

Как показано в §2.1, если G~S^t а к. соответствует графу » т0 задача восстановления орбит по набору совпадает с проблемой Улама-Келли. Взяв к. = приходим к восстановлению графа Г по подграфам, получаемым удалением сразу ^ различных вершин шесте с инцидентными им ребрами. Выбирая в качестве kL иные графы, будем получать задачи восстановления, не рассматривавшиеся, насколько это известно автору, ранее в литературе.

Согласно договоренности, группа G транзитивна, значит у нее единственная I-орбита ••• Д2^}}. Заметим, что

Ц< ку ) отличается от набора Н(ку) » определяемого формулой (5), только, быть может, вхождениями орбиты к; . Это наводит на мысль обозначить через Н*(к/) набор, получаемый из Ц-(К-) удалением всех hj . Задачи восстановления орбит по наборам Uc и назовем соответственно слабым и сильным восстановлением по модулю орбиты к. (или К.-восстановлением). Слабые задачи аналогичны проблеме Улама-Келли, а сильные - проблеме Харари. Выше уже рас

- 13 сматривалось сильное (^-восстановление.

Естественно возникает вопрос о переносе теоремы В на случай сильного восстановления по модулю орбиты k^la^. В общем это достаточно сложно. Однако для орбит , никакие два элемента которых не пересекаются (что возможно, если группа Q импримитивна), такое обобщение получено в § 2.5. Примером задач подобного типа служит восстановление смешанных графов; для него устанавливаются неравенства типа Ловаса-Мюдлера (следствие 2.5.6).

Параграф 2.3 посвящен слабому восстановлению. В нем используется следующее усиление понятия восстановимости. Назовем орбиту ковосстановимой по модулю к (или k-ковосстановимой), если кратности ее вложений в орбиты с одинаковыми наборами U- совпадают: : :

В частности, граф Г вершинно-ковосстановим, если во всяких двух графах с совпадающими наборами вершинно-исключенных подграфов число подграфов, изоморфных Г, одинаково. Доказано (см. утверждение 2.3.3), что k-ковосстановимая орбита к-восстановима.

Вершинная воостановимость графов с изолированными вершинами очевидна. Утверждение об их ковосстановимости называется в литературе леммой Келли; впервые оно было доказано в [45]. Там же была показана воостановимость несвязных графов; затем этот результат неоднократно передоказывался [46 - 49]. Ковосстановимость несвязных графов была впервые установлена Таттом [50, 51] в 1977 году, Его доказательство основано на свойствах дихроматического многочлена и довольно сложно; простые доказательства, использующие алгебру графов, были даны в 1982 году независимо Кокеем [24] и автором [74] . Аналоги всех перечисленных результатов справедливы и для к-орбит. Для их формулировки необходимо прежде всего ввести для орбит понятие связности. Этому посвящен параграф 2.2, где каждой паре орбит сопоставляется гиперграф. Напомним определения (см. [52]).

Гиперграфом называется пара ( V , Е ), где V - непустое конечное множество вершин, а £ - семейство непустых подмножеств

V , называемых гиперребрами. (Кроме того, обычно считается, что обединение всех гиперребер совпадает с множеством вершин. Здесь этого не требуется.) Когда мощность каждого гиперребра равна двум, гиперграф превращается в граф (возможно, с кратными ребрами). Два гиперграфа £) и £') изоморфны, если между множествами их вершин существует биекция • V-^V' такая, что образ всякого гиперребра из £ (при естественном продолжении на 2V ) является гиперребром в PEf'. Если V'^V , £^£ , то называется подгиперграфом гиперграфа Гиперграф связен, если всякие его две вершины можно соединить цепочкой пересекающихся гиперребер, и несвязен в противном случае. Максимальный связный подтиперграф в называется его компонентой связности. Будем называть г -полным такой гиперграф , у которого семейство гиперребер состоит из всех v -элементных подмножеств множества вершин

V , и любые два таких подмножества входят в £ одинаковое число раз. Если значение г несущественно, будем говорить просто о полном гиперграфе.

Как и при построении набора (9), зафиксируем орбиту k. группы Ct . Выберем в к-орбите к. той же группы какой-нибудь элеJ мент , 2*Xtz,., и с помощью 1а. сопоставим ему следующим образом гиперграф V5?ft}. В качестве его вершин возьмем все z-элементов орбиты Ц cz°> - - >Чтобы построить гиперребра, каждой из к точек € С£У сопоставим множество £1 — г У тех элементов из L , в которые эта точка входат. Набор F-(Ei>EZ) t,.f возьмем в качестве семейства гиперребер для . Можно показать (см. утверждение 2.2.1), что гиперграфы, отвечающие различным элементам из К. , изоморфны. Назовем \ рассматриваемый с точностью до изоморфизма, гиперграфом по модулю Ь. орйитн к, .

Если С, = S^ , то гиперграфы по модулю К^ ni оказываются обычными графами, соответствующими орбитам группы S^ . Существенное отличие графов от гиперграфов орбит состоит в том, что разным орбитам могут отвечать изоморфные гиперграфы; примеры этого приведены в §2.2.

Теперь основные результаты параграфа 2.3 (теоремы 2.3и 2.3.2 ) можно сформулировать так:

Теорема С. Пусть гиперграф несвязен, причем по крайней мере одна из его компонент связности - полный гиперграф. Тогда орбита ковосстановима по модулю J-ь . Если класс изоморфизма гиперграфа однозначно определяет орбиту К- , то для ее h.-ковосстановимости достаточно несвязности <fCj .

Отсюда немедленно следуют приведенные выше результаты Татта и Кел-ли. С помощью теоремы С получается также новое достаточное условие реберной восстановимости графов (утверждение 2.3.5 ), и простое доказательство вершинной восстановимости хроматического многочлена и числа графа (утверждение 2.3.? ). Из результатов §2.3 вытекает равносильность гипотезы Улама-Келли утверждению:

Алгебра L * п-вершинных графов при порождается как кольцо несвязными графами.

Основные результаты диссертации опубликованы в [74] -[79] .> Они докладывались на четвертом Одесском научно-исследовательском семинаре по графам, гиперграфам и алгебраическим системам (сентябрь 1980 г.), П Всесоюзной школе-семинаре по дискретной оптимизации в Вадул-луй-Водэ (сентябрь 1983 г.), на региональных циклах заседаний научно-исследовательского семинара по комбинаторной математике при Самаркандском госуниверситете им. А.Навои (октябрь 1983 и 1984 гг.), семинарах по теории графов в Институте проблем управления (Москва, март 1984 г.), в Белорусском госуниверситете (Минск, май 1984 г.), в Кишиневском госуниверситете игл. В.И.Ленина; семинарах по теории групп перестановок в Институте системных исследований (Москва, март 1984 г.), Киевском госуниверситете им. Т.Г.Шевченко (апрель 1984 г.); на алгебраическом семинаре Института математики с ВЦ АН MCGP.

Автор благодарен участникам перечисленных семинаров за замечания, способствовавшие улучшению работы. Он особенно признателен А.З.Зеликовскому, А.А.Иванову, кандидатам физико-математических наук А.К.Кельмансу и В.А.Уфнаровскому за проявленное внимание.

Диссертация выполнена под руководством д.ф.-м.н., профессора А.А.Зыкова; автор глубоко благодарен ему за постоянную поддержку.

1. Харари Ф. Теория графов. М.: Мир, 1973. - 369 с.

2. Harary P. A survey of the reconstruction conjecture. "Lect.Notes Math.", 1974, 406, pp. 18 28.

3. Holton D.A. Reconstruction. "Austral. Math. Soc. Gaz.", 1978, v. 5, n. 1, pp. 15 - 20.

4. Bondy J.A., Hemminger R.L. Reconstruction by enumeration-some application of a counting theorem to the graph reconstruction problem. "Probl. comb, et theor. graphes. Colloq., Orsay, 1976", Paris, 1978, pp. 51 - 55.

5. Bondy J.A., Hemminger R.L. Graph reconstruction a survey. -"J. Graph Theory", 1977, v. 1, n. 3, pp. 227 - 268.

6. Nash-Williams J.A. The reconstruction problem. "Selected Topics in Graph Theory", N.-Y., 1979.

7. Stochmeyer P.K. The falsity of the reconstruction conjecture for tournaments. "J. Graph Theory", 1977,v.1,n.1,pp. 19 - 25.

8. Stochmeyer P.K. A census of non-reconstructible digraphs, I:Six related families.-"J.Comb.Theory",1981,v.31B,n.2,pp.232-239.

9. Wielandt H. Finite Permutation Groups. L.-N.Y., 1964- II4c.

10. Калужнин Л.А., Сущанский В.И. О прикладных задачах теории .групп перестановок. Ч. I. В сб.:"Вычисления в алгебре, теории чисел и комбинаторике." Киев, 1980, с. 3 - 20.

11. Клин М.Х. V-кольца и их связь с группами автоморфизмов бинарных отношений. "Математические исследования", 1972, 7, № I, с. 204 - 205.

12. Камерон П., Дж. ван Линт. Теория графов, теория кодирования иблок-схемы. -М.: Наука, 1980.- 139 с.

13. Krasner М. Une generalisation de la notion de corps.-"J.Math. Pure et Appl.", 1938, n. 19, pp. 367 383.- 126

14. Калужнин I.А., Клин М.Х, 0 некоторых максимальных подгруппах симметрических и знакопеременных групп. "Матем, сборник", 1972, т. 87, № I, с. 91 - 121.

15. Сущанский В.И., Вайдеман А. А. Алгебры инвариантных отношений подстановочных конструкций. В сб.: "Вопросы теории групп и гомологической алгебры." Ярославль, 1983, с. 3 - 19.

16. Вцшенский В.А., Сущанский В.И. Соответствие Галуа между AR -алгебрами и группами подстановок на конечном множестве. "AR -алгебры групп подстановок". Препринт 84,3 ИМ АН УССР. Киев, 1984, с. 4 44.

17. Сущанский В.И., Устименко-Бакумовский В.А. Характеризация типов булевых функций. В сб.:"Вычисления в алгебре, теории чисел и комбинаторике." Киев, 1980, с. 47 - 59.

18. Siemons J. On partitions and permutation groups on unordered sets. "Arch. Math.", 1982, v. 38, n. 5, PP. 391 - 403.

19. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977г 324с.

20. Зыков А.А. Алгебры комплексов. "Матем. сборник", 1957, т. 41, № 2, с. 159 - 176.

21. Weisfeiler В. On construction and identification of graphs. -"Lect. Notes Math.", 1976, v. 558, XIY, 237 pp.

22. Kocay W.L. On reconstruction degree sequenses. "Util. Math.У 1980, v. 17, pp. 151 - 162.

23. Kocay W.L. On reconstructing spanning subgraphs. "Ars. Comb.", 1981, v. 11, pp. 301 - 313.

24. Kocay W.L. Some new methods in reconstruction theory. -"Lect. Notes Math.", 1982, v. 952, pp. 89 114.

25. Li Wei Xuan. Structure polynomials and subgraph identities of graphs.-"Acta Math.Sinica",1980,v.23, n. 5,pp. 641 -645.

26. Григорьев Д.Ю. Два сведения изоморфизма графов к задачам о по- 127 линомах. "Зап. научн. семинаров Ленингр. отд. Мат. ин-та АН СССР", 1979, т. 88, с. 56 - 61.

27. Domb С. Graph theory and imbeddings. "Phase Transition and Critical Phenomena", N.Y., 1974, pp. 1 - 96.

28. Sykes M.P., Essam J.W., Heap B.R., Hiley B.J. Lattice constant systems and graph theory.-"J.Math.Phys.",1966,v.7,pp.1557-1571.

29. Borzacchini L. Lattice constants matricial equations for conversion matrices.-"Calcolo", 1980,v.17, n. 4, pp. 379 384.

30. Borzacchini L., Pulito C; Graph-covering and Ramsey numbers by conversion matrices. -"Riv.math.Univ.Parma",1981,v.7,pp. 377 -382.

31. Borzacchini L., Pulito C. Some results on conversion matrices.-"Discrete Math.", 1982, v. 39, n. 3, pp. 255 261.

32. Камерон П.Дж. Группы подстановок на неупорядоченных множествах.-Б сб.:"Проблемы комбинаторного анализа".М.:Мир,1980,с.149-178.33. фон Нейман Дж., Моргенштерн 0. Теория игр и экономическое поведение. Пер. с англ. -М.: Наука, 1970.

33. Livingstone D., V/agner A. Transitivity of finite permutation groups on unordered sets.-"Math. Z.", v.90, 1965,pp.393-403.

34. Wielandt H. Endliche k-homogene permutationsgruppen.-"Math.Z. 1967, v. 101, pp. 142.

35. Bercov R.D., Hobby C.R. Permutation groups on unordered sets. -"Math. Zl', 1970, v. 115, pp. 165 168.

36. Kantor W.M. On incidence matrices of finite projective and af-fine spaces. "Math. Z.", 1976, v. 148, pp. 127 - 139.

37. Cameron P.J. Transitivity of permutation groups on unordered sets. "Math. Z. ", 1976, v. 148, pp. 127 - 139.

38. Cameron P.J. Orbits of permutation groups on unordered sets,I.-"J. London Math. Soc.", 1978, v. 17, pp. 410 414.

39. Harary P. On the reconstruction of a graph from a collection of- 128 subgraphs.-"Theory of Graphs and its Applications", 1964, pp. 47 52.

40. Lov&sz L. A note on the line reconstruction pro"blem.-"J. Combinatorial Theory", 1972, v. 13B, pp. 309 ЗЮ.

41. Schmeichel E.P. A note on the edge reconstruction conjecture? "Bull. Austral. Math. Soc.", 1975, v. 12, pp. 27 30.

42. Muller V. The edge reconstruction hypothesis is true for graphs with more than n log2n edges.-"J.Combinatorial Theory", 1977,v. 22B, n. 3, pp. 281 283.

43. Лившиц Э.М. 0 восстановлении орбит конфигураций по максимальным фрагментам. 1982, 4 м.п. с. (не опубликовало).

44. Kelly P.J. A congruence theorem for trees. "Pacific J. Math.',1 1957, v. 7, pp. 961 - 968.

45. Chartrand G., Kronk H.V. On reconstructing disconnected graphs. "Ann. N.Y. Acad. Sci.", 1970, v. 175, pp. 85 - 86.

46. Chartrand G., Kronk H.V., Schuster S. A technique for reconstructing disconnected graphs.-"Colloq.Math.','1973 ,v.27,pp.31-34.

47. Greenwell D.L., Hemminger R.L. Reconstructing the n-connected components of a graph.-"Aequat. Math.",1973,v.9,pp. 19-22.

48. Manvel B. On reconstructing graphs from their sets of subgraphs "J.Combinatorial Theory", 1976, v. 21B, pp. 156 -165.

49. Tutte W.T. All the King's horses. A guide to reconstruction.-"Graph Theory and Related Topics", N.Y., 1979, pp. 15 33.

50. Tutte W.T. The reconstruction problem in graph theory. "Brit. Polim. J.", 1977, v. 9, n. 3, PP. 180 - 183.

51. Зыков А.А. Гиперграфы. "успехи мат. наук", 1974, 29, № 6, с. 89 - 154.

52. Атья М., Макдональд И. Введение в коммутативную алгебру. М.:Мир, 1972, 160 с.

53. Супруненко Д.А. Группы матриц. М.: Наука, 1972.

54. Каргаполов М.И., Мерзляков Ю.И. Основы теории групп. М.: Наука, 1982, 288 с.

55. Кострикин А.И. Введение в алгебру. М.: Наука, 1977,- 495 с.

56. Stanley R.P. Invariants of finite groups and their applicati ons to combinatorics.-"Bull.Amer.Math.Soc.",1979, v.1, n. 3, PP. 457 511.

57. Айгнер M. Комбинаторная теория. M.: Мир, 1982, 556 с.

58. Холл М. Комбинаторика. М.: Мир, 1970. 424 с.

59. Риордан Дж. Комбинаторные тождества. М.: Наука, 1982,- 255 с.

60. Спеньер Э. Алгебраическая топология. М.: Мир, 1971,- 680 с.

61. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981, 341.

62. Brondsted A. An Introduction to Convex Polytopes. N.Y., Springer Verlag, 1983, - 160 p.

63. Bjorner A. The unimodality conjecture for convex polytopes. -"Bull. Amer. Math. Soc. (U.S.)", 1981,v.4, pp. 187 188.

64. Устименко-Бакумовский B.A. Решетка надгрупп индуцированной симметрической группы. "Докл. АН СССР", 1977, т. 237, $ 2, с. 276 - 279.

65. Skalba J. On the maximality of Sn in ~ Algebra", 1982, v. 75, n. 1, pp. 158 174.

66. Черняк Ж.А. Несколько дополнений к одной статье Манвела. -"Вестн. АН БССР. Сер.физ.нмат. н.", 1982,№ 6, с. 44 49.

67. Земляченко В.Н., Корнеенко Н.й., Тышкевич Р.И. Проблема.изоморфизма графов. "Зап. научн. семинаров ЖМИ АН СССР", 1982, т. 118, с. 83 - 158.

68. Biggs ff.L. Algebraic Graph Theory. L.-IJ.Y., 1974, 168 p.

69. Greenwell D.L. Reconstructing graphs. "Proc. Amer. Math. Soc.", 1971, v. 30, pp. 431 - 433.- 130

70. Burns D., Schuster S. Every (p, p+2)-grapg is contained in its complement.-"J.Graph Theory",1977, v.1, pp. 277 299.

71. Shuster S. Embedding (p, p-1)-graphs in their complements;-"Israel. J. Math.", 1978, v. 30, pp. 313 320.

72. Faudree R.J., Rousseau C.C., Schelp R.H., Schuster S. Embedding graphs in their complements. "0'z.ech. Math. J.1', 1981, v. 31, pp. 53 - 62.

73. Мнухин В.Б. О восстановлении многочленов графа.- В сб.: 27 Int.V/iss.Kolloq. Ilmenau, 25-29 Oct. 1982", Ilmenau, 1982, pp. 87 90.

74. Мнухин В.Б. Базис алгебры инвариантов графов. В сб.Математический анализ и его приложения", Ростов-на-Дону, РТУ, 1983, с. 55 - 60.

75. Мнухин В.Б. О восстановимости графоидов. Ин-т мат. с ВЦ АН МССР, Кишинев, 1983 , 32 с. (Рукопись депонирована в ВИНИТИ2 августа 1983 г., № 4281 83 Деп.).

76. Мнухин В.Б. О матрицах, ассоциированных с группами перестановок. "Изв. АН МССР: сер. физ.-техн. и мат. н.", 1984, № 3, с. 61 - 64.

77. Мнухин В.Б. Усиление теоремы Ливингстона-Вагнера о группах перестановок. В кн.:"Молодежь. Наука. Производство. Тезисы докл. конф. молодых ученых АН МССР". Кишинев, 1984, с. 178 -179.