авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |

«Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Казанский (Приволжский) федеральный университет» ...»

-- [ Страница 6 ] --

a1,..., an1 ), то получится семейство отображений вида (5) (где роль V играет U ), обладающее набором свойств, анало гичных свойствам 1) – 4) из определения 5.5.2. Отсюда следует, что су ществует гомоморфизм, обратный к гомоморфизму h, что и требовалось доказать.

Следующее утверждение является аналогом [119, предложение 1.6.6].

Теорема 5.5.4. Категория модулей над супералгеброй A SAlg(R) эквивалентна (и даже рационально эквивалентна) категории Z2 градуированных левых модулей над ассоциативной Z2 -градуированной ассоциативной алгеброй UR (A).

Доказательство. Пусть M есть A-модуль. Тогда структура левого UR (A)-модуля определяется по правилу:

X(;

a1,..., an1 )v = a1... an1 v.

Здесь R(n), a1,..., an1 A, v M — однородные элементы. Со поставление A-модулю M модуля над UR (A), совпадающего с M как K -модуль, есть функтор из категории A-модулей в категорию левых Z2 градуированных UR (A)-модулей.

Обратный к нему функтор строится еще легче. Если M есть Z2 градуированный UR (A)-модуль, то это значит, что определены все вы ражения вида X(;

a1,..., an1 )v M, где R(n), a1,..., an1 A, v M — одно родные элементы. Но тогда можно определить однородные отображения:

R(n) A (n1) M M, сопоставляющие элементам a1 · · ·an1 v элементы a1 · · · an1 v = X(;

a1,..., an1 )v. Из свойств 1) – 4) определения 5.5.2 легко выводятся все свойства модуля над супералгеброй над операдой. Ясно также, что таким образом получается функтор, обратный к построенному выше, и что эти взаимно обратные функторы реализуют рациональную эквива лентность рассматриваемых категорий.

Глава 6. Некоторые приложения В этой главе собраны некоторые приложения общей теории операд.

Общим для многих рассматриваемых ситуаций является использование некоторых матричных конструкций (§§6.1, 6.2, 6.3, 6.6). В §§6.4 и 6. изучаются операды, имеющие наглядное геометрическое представление (симплексы, многомерные сферы, кубы и т.п.), которые можно считать подоперадой операды R, в которой R(n) = Rn для всех n, а R есть по ле действительных чисел. Для структуры операды, впрочем, требуется только чтобы это была полугруппа с единицей. Отметим, что конструк ция операды G исходя из полугруппы с единицей, обозначаемой также через G (где G(n) = Gn ) является частным (одномерным) случаем одной из конструкций операд многомерных кубических матриц, которая изла гается в начале § 6.1. Двумерный случай приводит (в виде подоперад) к операдам, элементы которых можно истолковать как разнообразные графы (ориентированные и неориентированные). Более высокие размер ности можно интерпретировать как некоторые гиперграфы.

В § 6.2 вводится другой тип многомерных матриц. Операды таких матриц линейны, и их можно рассматривать как многомерные обобщения колец матриц над ассоциативными кольцами с единицей. В простейшем частном случае получается операда, элементы которой можно интерпре тировать как тензоры, причем операдная композиция превращается в свертку тензоров.

Напомним одну подробность. В первых главах рассматривались операды, определенные над вербальными категориями, причем если R — операда, определенная над вербальной категорией V, то R мож но считать контравариантным функтором, определенным на категории, двойственной к V. В случае, если V = (а именно этот случай будет преобладающим в данной главе) переход к двойственной категории со ответствует взятию обратной подстановки, поэтому можно считать, что если m, R(m), i R(ni ), 1 i m, то ()1... m = 1 (1)... 1 (m), и аналогично, если A есть R-алшебра, и a1,..., am A, то ()a1... am = a1 (1)... a1 (m).

§ 6.1. Операды графов Операды многомерных нелинейных кубических матриц Пусть G — некоторое множество с выделенным элементом. За фиксируем натуральное число n 1. Пусть [k] = {1,..., k} (это отличие от соглашения, принятого в предыдущих главах, не приводит к какой либо путанице). Обозначим через GMn (k) множество отображений вида A : [k]n G. При k = 0 положим GMn (0) = {}, множество из од ного элемента. Пусть GMn = {GM (k)|k = 0, 1,... }. Введем на этом семействе структуру операды двумя способами. Определяется семейство отображений вида:

GMn (m) GMn (k1 ) · · · GMn (km ) GMn (k1 + · · · + km ), сопоставляющих последовательности элемент (A, B1,..., Bm ) AB1... Bm. Здесь A GMn (m), Bi GMn (ki ), 1 i m,.

Разобъем множество [k1 + · · · + km ] на m непересекающихся под множеств bi = {k1 + · · · + ki1 + 1,..., k1 + · · · + ki1 + ki }, 1 i m.

Если j bi, то j = k1 + · · · + ki1 + j, где j [1, ki ]. Соответствие j j есть сохраняющая порядок биекция между bi и [1, ki ].

Первая операция композиции (будем называть ее композицией 1) определяется так:

Bi (j1,..., jn ) при j1,..., jn bi A(i,..., i ), если j1 bi1,..., jn bin, 1 n AB1... Bm (j1,..., jn ) = и среди i1,..., in есть хотя бы два различных.

(6.1.1) При этом естественно предполагать, что для всех m и для всех A GMn (m) имеет место равенство A(i,..., i) = для всех i, 1 i m.

Определим еще отображение E : [1] K, полагая E(1) =.

Пусть теперь G — моноид с единицей. Операция композиции, которую будем называть композицией 2, определяется так:

A(i,..., i)Bi (j1,..., jn ) при j1,..., jn bi A(i,..., i ), если j1 bi1,..., 1 n jn bin, и среди AB1... Bm (j1,..., jn ) = i1,..., in есть хотя бы два различных.

(6.1.2) Обозначения здесь те же самые, что и для композиции 1. Никаких усло вий на элементы GMn в этом случае не налагается. Отображение E определяется так же, как и выше.

Определим действие m на GMn (m) следующим образом:

A(j1,..., jm ) = A( 1 (j1 ),..., 1 (jm )) (6.1.3) Здесь m. Эквивалентное требование:

A GMn (m), A(j1,..., jm ). Легко убедиться, что если A((j1 ),..., (jm )) = n, то A( ) = (A ). Но если рассматривать подстановки как элементы категории, двойственной к, то превращается в, и это означает, что (6.1.3) соответствует требованиям, которые были сформулированы в начале главы 2.

Теорема 6.1.1. 1) Семейство GMn с операцией композиции 1 (6.1.1) и действием симметрических групп (6.1.3) является -операдой с единицей E.

2) Семейство GMn с операцией композиции 2 (6.1.2) и действием симметрических групп (6.1.3) также является -операдой с еди ницей E.

Доказательство. Доказательство примерно одинаково для обе их композиций, поэтому достаточно привести подробное изложение лишь для случая композиции 1.

Проверим ассоциативность (6.1.1). Пусть A GMn (m), Bi GMn (ki ), 1 i m, B = B1... Bm, Ci,j GMn (li,j ), 1 j ki, C i = Ci,1... Ci,ki.

Введем следующие обозначения. Положим ai = [k1 + · · · + ki1 + 1, k1 + · · · + ki1 + ki ], 1 i m, и пусть k = k1 + · · · + km. Если x ai, i то x = ks + x, где x [1, ki ]. Ясно, что [1, k] = a1 · · · am.

s= Пусть далее li = li,1 + · · · + li,ki для всех i, 1 i m, и bi = i ks [l1 + · · · + li1 + 1, l1 + · · · + li1 + li ]. Если y bi, то y = ls,t + y, s=1 t= где y [1, li ]. Если l = l1 + · · · + lm, то [1, l] = b1 · · · bm.

Теперь пусть j1 j i1 ks i1 ks ci,j = [ ls,t + li,t + 1, ls,t + li,t ], s=1 t=1 t=1 s=1 t=1 t= где 1 i m, 1 j ki. Очевидно, что bi = ci,1 · · · ci,ki. Если i ks j z ci,j, то z = li,t + z, где z [1, li,j ].

ls,t + s=1 t=1 t= j1 j Наконец, положим di,j = [ li,t ]. Тогда [1, li ] = di, li,t + 1, t=1 t= · · · di,k, di,j [1, li,j ] ci,j, где под изоморфизмами подразумеваются = = i однозначно определенные сохраняющие порядок биекции. Биекция di,j = j [1, li,j ] — это отображение w w, где w = li,t + w, биекция ci,j = t= [1, li,j ] — это отображение z z. Отметим, что если y ci,j bi, то определены y [1, li,j ] и y [1, li ], причем фактически y di,j, так что определено число y [1, li,j ]. Легко заметить, что y = y.

Если даны i, j, причем 1 i m, 1 j ki, то положим i ks + j ai. Отображение r осуществляет биекцию между r(i, j) = s= множествами {(i, 1),..., (i, ki )} и ai. При этом, очевидно, r(i, j) = j.

Будем вычислять значения (AB)C 1... C m и A(B1 C 1 )... (Bm C m ) на произвольных аргументах вида = (1,..., n ), где все i берутся из m ks отрезка [1, ls,t ] = [1, l].

s=1 t= По определению композиции 1 (6.1.1) будем иметь следующее:

Ci,j (1,..., n ) при 1,..., n ci,j AB(r,..., r ), если 1 n 1 ci1,j1, r1 = r(i1, j1 ), (AB)C 1... C m () =............

n cin,jn, rn = r(in, jn ), и среди r1,..., rn есть хотя бы два различных.

Заметим, что r1,..., rn [1, k]. Следовательно, согласно (6.1.1), получим Bs (r1,..., rn ) если r1,..., rn as A(v,..., v ), если r a,..., r a, 1 n 1 v1 n vn AB1... Bm (r1,..., rn ) = и среди v1,..., vn есть хотя бы два различных.

В конечном итоге, Ci,j (1,..., n ) при 1,..., n ci,j, иначе, если 1 ci1,j1, r1 = r(i1, j1 ),............

n cin,jn, rn = r(in, jn ), и среди r1,..., rn есть (AB)C 1... C m () = хотя бы два различных, то Bs (r1,..., rn ) если r1,..., rn as A(v,..., v ), если r1 av1,..., rn avn, 1 n и среди v1,..., vn есть хотя бы два различных.

(6.1.4) Вычисляя аналогичным образом другую часть предполагаенмого равен ства, получим:

Ci,j (1,..., n ), если 1,..., n bi и 1,..., n di,j, Bi (u1,..., un ), если 1,..., n bi и 1 di,u1,............

n di,un, и среди u1,..., un A(B1 C 1 )... (Bm C m )() = есть по крайней мере два различных, A(v,..., v ), если 1 n 1 bv1,..., n bvn, и среди чисел v1,..., vn есть по крайней мере два различных (6.1.5) Покажем, что (6.1.4) и (6.1.5) — это одно и то же отображение. Зафик сируем [1, l], и будем расматривать различные возможности.

Пусть сначала 1 ci1,j1,..., n cin,jn, r1 = r(i1, j1 ) av1,..., rn = r(in, jn ) avn. Во всех случаях, когда идет перечисление нескольких однотипных индексов, будет предполагаться (здесь и да лее), что по крайней мере два из них различны. Из сделанного только что предположения, согласно (6.1.4), следует, что (AB)C 1... C m () = A(v1,..., vm ). Рассмотрим произвольное число u, 1 u n. Из того, i u что по определению ru = ks + ju aiu, а по условию ru avu, следу s= ет, что iu = vu. Но тогда u ciu,ju = cvu,ju bvu. Согласно (6.1.5), это значит, что A(B1 C 1 )... (Bm C m )() = A(v1,..., vm ).

Обратно, пусть 1 bv1,..., n bvn, то есть, согласно (6.1.5), A(B1 C 1 )... (Bm C m )() = A(v1,..., vm ). Поскольку отрезок [1, l] покры вается непересекающимися отрезками ci,j, то для произвольного u име ется включение u ciu,ju. Так как ciu,ju biu, и u bvu, то iu = vu. Из u cvu,ju следует, что ru = r(vu, ju ) avu. Согласно (6.1.4), получаем отсюда (AB)C 1... C m () = A(v1,..., vm ).

Рассмотрим теперь случай, когда для 1 u n выполняются включения u ciu,ju, и если ru = r(iu, ju ), то существует s такой, что r1,..., rn as. Согласно (6.1.4), (AB)C 1... C() = Bs (r1,..., rn ). От метим сначала, что из сделанных предположений следует, что ru = ju, а из r1,..., rn as следует, что i1 = · · · = in = s, то есть j u u cs,ju bs. Далее, u = ls,ju + u ds,ju. Отсюда, по (6.1.5), t= A(B1 C 1 )... (Bm C m )() = Bs (j1,..., jn ) = Bs (r1,..., rn ).

Обратно, пусть 1,..., n bi, 1 di,u1,..., n di,un, то есть это случай, когда A(B1 C 1 )... (Bm C m )() = Bi (u1,..., un ). Из q di,uq следует, что q ci,uq (1 q n). Отсюда, если rq = r(i, uq ), то rq = uq.

В результате по (6.1.4) получаем (AB)C 1... C m () = Bi (u1,..., um ).

Рассмотрим последний оставшийся случай. Пусть 1,..., n ci,j, и (AB)C 1... C m () = Ci,j (1,..., n ). Очевидно, что для произвольного u, 1 u n имется включение u ci,j bi. Из u ci,j следует также u di,j. Уже было отмечено, что u = u. Следовательно, по (6.1.5) получим A(B1 C 1 )... (Bm C m )() = Ci,j (1,..., n ).

Обратно, пусть 1,..., n bi, и 1,..., n di,j, что означает A(B1 C 1 )... (Bm C m )() = Ci,j (1,..., n ) = Ci,j (1,..., n ). Отсюда легко следует, что 1,..., n ci,j, и, таким образом, (AB)C 1... C m () = Ci,j (1,..., n ).

Свойства связанные с единицей E, проверяются очень легко, и эту проверку мы опустим. Проверим свойства -операды, связанные с дей ствием подстановок.

Проверка свойства A(B1 )... (Bm ) = (AB1... Bm )(1 · · · m ) не связана с какими-либо сложностями, как, впрочем, и в большинстве случаев, когда необходимо производить такую проверку. Сосредоточимся на тождестве (A)B1... Bm = (AB(1)... B(m) )( ), где A GMn (m), Bi GMn (ki ), 1 i m, n, = (k1,..., km ).

Пусть k = k1 +· · ·+km, [1, k] = b1 · · ·bm, где bi = [k1 +· · ·+ki1 + 1, k1 +· · ·+ki ]. Пусть также bi = [k(1) +· · ·+k(i1) +1, k(1) +· · ·+k(i) ] для всех i, так что [1, k] = b1 · · · bm. Напомним, что есть биекция [1, k] [1, k], которая биективно и с сохранением порядка отображает каждый bi на b(i). Положим = ( )1. В главе 1 было показано, что ( )1 = ( 1 ) (), где = (k(1),..., k(m) ). Отображение биективно отображает [1, k] на [1, k], причем для каждлого i биективно и с сохранением порядка отображает bi на b1 (i). Таким образом, b(i) равносильно тому, что () bi.

Пусть = (1,..., n ), 1,..., n [1, k]. Тогда Bi (1,..., n ) при 1,..., n bi, A( 1 (j ),..., 1 (j )), если 1 n 1 bj1,..., n bjn, (A)B1... Bm () = и среди j1,..., jn есть хотя бы два различных.

(6.1.6) Заметим теперь, что (AB(1)... B(m) )( )() = AB(1)... B(m) ( (1 ),..., (n )).

По (6.1.1) этот элемент можно описать следующим образом:

B ( ( ),..., ( )) при ( ),..., ( ) b, (s) 1 n 1 n s что равносильно 1,..., n b(s), A(t,..., t ), если (1 ) bt1,..., (n ) btn, 1 n (6.1.7) (что равносильно 1 b(t1 ),..., n b(tn ) ), и среди t1,..., tn есть хотя бы два различных.

Покажем, что (6.1.6) и (6.1.7) определяют одно и то же отображение.

(s) Прежде всего, заметим, что если b(s), то = kp +, и по p= (s1) определению получаем () = k(q) +, а это означает, что () = q=.

Зафиксируем теперь = (1,..., m ) [1, k1 + · · · + km ]. Допустим, что 1,..., i bi. Это значит, что (A)B1... Bm () = Bi (1,..., n ).

Но теперь (1 ),..., (i ) b1 (i). Согласно (6.1.7) получаем (AB(1)... B(m) )( )() = B(1 (i)) ( (1 ),..., (n )).

Но это значение равно Bi (1,..., n ).

Обратно, если (1 ),..., (i ) bs, то 1,..., i b(s). Это зна чит, что (A)B1... Bm () = B(s) (1,..., n ) = (AB(1)... B(m) )( )().

Наконец, условие 1 bj1,..., n bjn равносильно тому, что (1 ) bs1 (j1 ),..., (n ) b1 (jn ). Отсюда следует, что и в этом случае (A)B1... Bm () = (AB(1)... B(m) )( )().

Случай композиции 2 рассматривается практически точно так же.

Пример 6.1.1. Рассмотрим случай n = 1. Легко увидеть, что для того, чтобы была определена композиция 1, компоненты операды GM1 должны быть одноэлементными. Поэтому рассмотрим случай ком позиции 2. Отображение A : [m] G можно интерпретировать как упорядоченную последовательность (a1,..., an ), где ai = A(i). Если Bi GM1 (ki ) записать как (bi,1,..., bi,ki ), то легко убедиться, что опе рация (6.1.2) выглядит так:

AB1... Bm = (a1 b1,1,..., a1 b1,k1,..., am bm,1,..., am bm,km ).

Таким образом, GM1 с композицией 2 — это хорошо известная операда, которая строится по произвольной полугруппе с единицей.

Пример 6.1.2. Рассмотрим случай n = 2. Тогда GM2 (k) есть множество всех квадратных k k -матриц с элементами из G. Положим 0 =. Явный вид композиции 1 в этой операде таков. Пусть A GM2 (n), B1 GM2 (k1 ),..., Bm GM2 (km ). В рассматриваемом случае компози ции 1 на главной диагонали каждой из матриц расположены нули. Тогда B a1,2... a1,m 1 a 2,1 B2... a2,m AB1... Bm =... (6.1.8).

..

...

.

...

am,1 am,2... Bm Здесь AB1... Bm — блочная k k -матрица, i, j -й блок которой есть мат рица размером ki kj. Диагональные блоки — квадратные матрицы Bi, 1 i m. Если i = j, и ai,j — i, j -й элемент матрицы A, то ai,j обо значает матрицу размером ki kj, целиком заполненную одним и тем же элементом ai,j.

Кроме того, если m и A M (n), то правое действие n на GM2 (m) определяется так: A есть матрица, i, j -й элемент которой равен a1 (i),1 (j).

В случае композиции 2 явный вид этой композиции при n = 2 таков:

aB a1,2... a1,m 1,1 1 a a2,m 2,1 a2,2 B2... AB1... Bm =.. (6.1.9)..

....

..

... am,1 am,2... am,m Bm Обозначим через HGn (m) множество тех A GMn (m), которые обладают свойством:

{i1,..., in } = {j1,..., jn } влечет A(i1,..., in ) = A(j1,..., jn ) (6.1.10) для любых j1,..., jn, и i1,..., in из {1,..., m}. Отметим, что частным случаем (6.1.10) является следующее условие: для каждого m и для каждого A HGn (m) имеется равенство:

A(i1,..., in ) = A((i1 ),..., (in )) для всех i1,..., in [1, m].

Теорема 6.1.2. Семейство HGn = {HGn (k)|k = 0, 1,... } есть подоперада -операды GMn. В случае, когда рассматривается ком позиция 1, необходимо предполагать, что в HGn (k) входят только отображения со свойством A(i,..., i) = для всех i и k.

Доказательство. Достаточно показать, что если A HGn (m), B1 HGn (k1 ),..., Bm HGn (km ), то AB1... Bm HGn (k1 + · · · + km ).

Как и в предыдущей теореме, достаточно разобрать случай композиции 1.

Пусть {1,..., n } = {1,..., n }. Тогда включения 1,..., n bi равносильны включениям 1,..., n bi. При этом {1,..., n } = {1,..., n }. А если 1 bj1,..., n bjn и 1 bt1,..., n btn, то {j1,..., jn } = {t1,..., tn }. Из этого следует (согласно (6.1.1)), что AB1... Bm (1,..., n ) = AB1... Bm (1,..., n ).

Разложимость и неразложимость в операде неориентированных графов Пусть Gr(n) — множество всех неориентированных конечных гра фов с n вершинами, помеченными символами 1, 2,..., n. Графы рассмат риваются с точностью до изоморфизма следующего вида: если, Gr(n), то эти графы считаются равными, если между множествами ре бер, соединяющих любые две вершины с метками i и j (в дальнейшем будем отождествлять вершины и их метки) в графе, и множеством ре бер, соединяющих вершины i и j в графе, можно установить взаимно однозначное соответствие.

Определим на семействе множеств Gr = {Gr(n)|n 1} структуру операды. Как обычно, для графа Gr(n) через V () обозначается множество его вершин, а через E() — множество его ребер. Зададим композицию Gr(m) Gr(n1 ) · · · Gr(nm ) Gr(m) Gr(n1 + · · · + nm ), (0, 1,..., m ) 0 1... m.

Пусть i Gr(ni ), 1 i m, 0 Gr( m). Граф = 0 1... m устроен следующим образом. V () = {1,..., n1, n1 + 1,..., n1 + n2, n1 + n2 + 1,..., n1 + · · · + nm }. Каждое подножество множества V () ви да {n1 + · · · + ni1 + 1,..., n1 + · · · + ni1 + ni } будем отождествлять с множеством {1,..., ni } = V (i ) вершин V (i ), сопоставляя вершине n1 + · · · + ni1 + j вершину j, 1 j ni. Таким образом, можно считать, m что V () = V (i ), причем V (i ) V (j ) =.

i= Ребра E() описываются так. Пусть ребро e E(i ) соединяет вершины u и v, где 1 u, v ni. Тогда в графе определено ребро с тем же именем e, соединяющее вершины n1 + · · · + ni1 + u и n1 + · · · + ni1 + v. Относительно сделанного выше отождествления вершин i с подмножеством вершин это означает, что соответственным образом E(i ) вкладывается в E(), так что граф i — это подграф графа при 1 i m.

Кроме того, если e E(0 ) соединяет вершины i и j (1 i, j m) графа 0, то для любых вершин u E(i ), v E(j ) определено ребро euv = evu E() графа, соединяющее вершину n1 + · · · + ni1 + u с вершиной n1 + · · · + nj1 + v.

Определим действие n на Gr(n). Пусть n, Gr(n). Поло жим равным графу с вершинами 1,..., n, причем i и j соединены ребром e в тогда и только тогда, когда вершины (i) и (j) соединены ребром с тем же именем e в графе.

Через E обозначим граф с одной вершиной и пустым множеством ребер (E Gr(1)).

Теорема 6.1.3. 1) Семейство множеств Gr = {Gr(n)|n 1} c опре деленной на них выше операцией композиции и действием симмет рических групп является операдой. Единица операды — граф E.

2) Подоперада операды Gr состоящая из графов без петель, изоморф на подопераде GH2 операды GM2, (где G = N = {0, 1, 2,... } и = 0), состоящей из симметрических матриц c целочисленными неоторицательными компонентами и с нулями на главной диаго нали, рассматриваемой как операда с композицией 1.

Доказательство. Докажем пункт 1). Проверим свойства еди ницы. Пусть 1 =... = m = E, = 0 E... E. В графе имеется m вершин, столько же, сколько и в 0. Поскольку i = E (1 i m) не имеет ребер, то все ребра по определению получаются из ребер 0.

Пусть k, l – вершины 0, e — соединяющее их ребро в 0. Вершины k и l можно выбрать единственным способом, и они имеют метки (в ) k и l. Таким образом, по определению композиции, в определено лишь одно ребро ekl. Теперь очевидно, что имеется взаимно-однознчное соответствие между ребрами и 0. Следовательно, это один и тот же элемент Gr(m). Если m = 1, 0 = E, = 0 1 = E1, то прямо из определения композиции ясно, что вершины и ребра те же, что и у 1.

Докажем, что композиция ассоциативна. Пусть i = i,1... i,ni, 1 i m, i,j Gr(ki,j ), i Gr(ni ), 0 Gr(m). Покажем, что графы = 0 (1 1 )... (m m ) и = (0 1... m )1... m представляют один m ni и тот же элемент из Gr( ki,j ).

i=1 j= Ясно, что множество вершин у этих графов одно и то же:

m ni ki,j }. При этом вложения графов i,j i i,1... i,ni, {1,..., i=1 j= i,j отображают вершины i,j в V ( ) = V ( ) одинаковым обра i ns ni зом: l ks,t + ki,t + l.

s=1 t=1 t= Отождествляя i,j с подграфами и, а i — с подграфами 0 1... m, рассмотрим ребра и. Множество ребер можно раз бить на три непересекающихся подмножества:

m ni 1) E(i,j );

i=1 j= 2) множество ребер, определяемых так: для каждого ребра e E(i ), инцидентного вершинам k, l V (i ), для любых вершин u V (ki ), v V (li ) определено ребро euv = evu, cоединяющее u и v, 1 i m;

3) множество ребер, определяемых так: для каждого ребра e E(0 ), соединяющего вершины k, l графа 0, произвольных p, q, 1 p nk, 1 q nl, и для любых u V (k,p ), v V (l,q ) определено ребро epq,uv, cоединяющее u и v (здесь epq,uv = eqp,uv = epq,vu и т.д.).

Аналогичным образом, используя определение композиции, множес тво ребер можно разбить на три непересекающихся подмножества, ко торые (с точностью до обозначений) совпадают с множествами из пунк тов 1), 2), 3) выше. Поэтому = как элементы операды Gr.

Проверим свойства операды, связанные с подстановками. Пусть i ni, i Gr(ni ), 1 i m, 0 Gr(m);

= 0 (1 1 )... (m m ), = (0 1... m )(1 · · · m ). Покажем, что это один и тот же эле мент Gr(n1 + · · · + nm ). Совпадение множеств вершин очевидно. Постро им взаимно-однозначное соответствие между множествами ребер. Пусть e — ребро, соединяющее две вершины подграфа i i, напри мер, n1 + · · · + ni1 + i (k) и n1 + · · · + ni1 + i (l), 1 k, l ni. Оно соответствует ребру e, соединяющему вершины n1 + · · · + ni1 + k и n1 + · · · + ni1 + l подграфа i графа 0 1... m. Но по определению 1 · · · m, этому ребру соответствует ребро, соединяющее верши ны (1 · · · m )(n1 + · · · + ni1 + k) = n1 + · · · + ni1 + i (k) и (1 · · · m )(n1 + · · · + ni1 + l) = n1 + · · · + ni1 + i (l) графа = (0 1... m )(1 · · · m ). Если же e — ребро 0, соединяющее вершины k и l, 1 k, l m, то любые вершины в k k и l l можно представить в виде k (u) и l (v), 1 u nk, 1 v nl, так что в определено ребро ek (u),l (v), соединяющее вершины n1 +· · ·+nk1 +k (u) и n1 +... + nl1 + l (v). Для того же ребра e в графе 0 1... m определено ребро eu,v, соединяющее вершины n1 +· · ·+nk1 +u и n1 +· · ·+nl1 +v. Это му ребру соответствует в графе = (0 1... m )(1 · · ·m ) ребро, со единяющее вершины (1 · · ·m )(n1 +· · ·+nk1 +u) = n1 +· · ·+nk1 +k (u) и (1 · · · m )(n1 + · · · + nl1 + v) = n1 + · · · + nl1 + l (v).

Пусть теперь m, = (0 )(1... m ), = (n1,..., nm ), = (0 (1)... (m) )( ). Построим взаимно-однозначное соответ ствие между ребрами и.

Пусть e — ребро графа (j), соединяющее вершины k и l, k, l n(j), 1 j m. При вложении (j) в ему соответствует ребро (с тем же именем), соединяющее вершины n1 + · · · + n(j)1 + k и n1 + · · · + n(j)1 + l.

Рассмотрим вложение графа (j) в граф 0 (1)... (m). Ребру e графа (j) будет соответствовать ребро с тем же именем, соединяю щее вершины n(1) + · · · + n(j1) + k и n(1) + · · · + n(j1) + l. Тогда в графе (0 (1)... (m) )( ) ребро с именем e должно соединять вер шины ( )(n(1) + · · · + n(j1) + k) и ( )(n(1) + · · · + n(j1) + l).

Но из определения ( ) следует, что эти числа равны соответствен но n1 + · · · + n(j)1 + k и n1 + · · · + n(j)1 + l.

Пусть e — ребро графа 0, соединяющее вершины k и l, 1 k, l m. Ему соответствует ребро e графа, соединяющее k и l. Тогда для любых вершин u V ((k) ), 1 u n(k), v V ((l) ), 1 v n(l), определено ребро eu,v в, соединяющее n1 + · · · + n(k)1 + u и n1 + · · · + n(l)1 + v. С другой стороны, по ребру e E(0 ) и вершинам u V ((k) ), v V ((l) ) строится ребро eu,v в графе 0 1... m, соединяющее вершины n(1) + · · · + n(k1) + u и n(1) + · · · + n(l1) + v. В графе (0 (1)... (m) )( ) этому ребру соответствует ребро с тем же именем, соединяющее вершины ( )(n(1) + · · · + n(k1) + u) = n1 + · · · + n(k)1 + u и ( )(n(1) + · · · + n(l1) + v) = n1 + · · · + n(l)1 + v.

Тем самым проверены все свойства операды для Gr.

Докажем утверждение 2). Легко убедиться, что графы без петель образуют подопераду -операды Gr. Обозначим ее через Gr0. Пусть G — множество целых неотрицательных чисел. Каждому графу Gr0 (n) можно сопоставить матрицу смежности A = A(), компоненты которой — элементы G. Напомним, что это nn-матрица, номера строк и столб цов которой соответствуют номерам (меткам) вершин графа, причем ес ли вершину i с вершиной j соединяет k 0 ребер, то i, j -я компонента матрицы A() равна k (и точно также равна k и j, i-я компонента, т.к.

рассматриваются неориентированные графы). Отсутствие петель равно сильно тому, что на главной диагонали этой матрицы стоят нули. Оче видно, что матрицу A() можно интерпретировать как элемент HG2 (n), и обратно, любой элемент из HG2 (n) можно интерпретировать как мат рицу смежности некоторого графа из Gr0 (n). Очевидно, что перед нами взаимно-однозначное соответствие. Необходимо убедиться, что это — го моморфизм операд.

Это легко проверяется с использованием примера 6.1.2: справед ливы равенства A(0 1... m ) = A(G0 )A(1 )... A(m ), и A() = A().

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

Определение 6.1.1. Граф будем называть операдно разло жимым (или просто разложимым), если существует такая нумерация его вершин, что изоморфен операдной композиции 0 1... m где 1,..., m, 0, — помеченные графы (элементы операды Gr ), такие, что 0 = E и, по крайней мере, один из графов i нетривиален при i 1.

Иными словами, граф G разложим, если = (0 1... m ) для некото рого n1 +···+nm.

Граф будем называть операдно неразложимым (или просто не разложимым), если он не является операдно разложимым. Иными сло вами, для неразложимого графа из (0 1... m ) следует, что либо = 1 =... = m = E, 0, либо m = 1, 0 = E, 1.

= = Лемма 6.1.1. Пусть = 0 1... m. Тогда в существует под граф, изоморфный 0.

Доказательство. Строим этот подграф следующим обрзом.

Выбираем для каждого i V (0 ) по одной вершине vi V (i ), i m, и для каждого ребра e, соединяющего в 0 вершины i и j — реб ро evi vj, соединяющее vi V (i ) V () и vj V (j ) V (). Очевидно, что подграф графа c множеством вершин {v1,..., vm } и множеством ребер {evi vj |e E(0 )} изоморфен 0.

Определение 6.1.2. Фрагментом графа с ядром будем на зывать пару графов (, ), где, причем выполнены условия 1) Если вершины v1, v2 V ( ) инцидентны ребру e E(), то e E( ).

2) Если v V ( ) соединено ребром e c v V (), то v V ( ) и e E( ).

Фрагмент (, ) будем называть нетривиальным, если ядро не равно тривиальному графу с одной вершиной без ребер, и V ( ) = V ( ).

Нетривиальный фрагмент (, ) графа будем называть разла гающим, если выполняется еще одно условие:

3) Если вершины v V ( ) и v V ( ), v V ( ) соединяет (в графе ) k ребер (k 0, согласно условию 2) все эти ребра принадлежат графу ), то для любой другой вершины w V ( ), вершина w соединена в графе c v в точности k ребрами.

Замечание 6.1.1. Заметим, что если (, ) — фрагмент, то для пара (, ) также будет фрагментом, разлагающим, если разлагающим был фрагмент (, ).

6.1.2. Фрагмент (, ) является разлагающим тогда и Лемма только тогда, если после некоторой перенумерации вершин = 0 E... E для некоторого графа 0, в котором нет петель, инци дентных вершине 1.

Доказательство. Пусть = 0 E... E и 1,..., m — вер шины 0. Положим 1 =, 2 = E,..., m = E, так что = 0 1 2... m. Тогда 1 = — подграф. Пусть 1,..., n1 — верши ны 1, тогда остальными вершинами будут n1 + 1,..., n1 + m 1.

Эти вершины соответствуют тривиальным подграфам E в разложении = 0 E... E. По определению операдной композиции, каждому ребру e графа 0, соединяющему вершины 1 и j 1, соответствует семейство ребер вида ei,n1 +j, соединяющих все вершины 1 = (то есть вер шины i, i = 1,..., n1 ) с вершиной n1 + j. Если в 0 имеется k ребер, инцидентных 1 и j, то для это будет означать, что каждая вершина соединена с вершиной n1 +j одним и тем же количеством k ребер. Таким образом, условие 3) из определения разлагающего фрагмента выполнено.

Обратно, пусть (, ) — разлагающий фрагмент, n1 = |V ( )|.

Снабдим вершины метками, начав нумерацию с вершин, так что V ( ) = {1,..., n1, n1 + 1,..., n1 + m 1}, и V ( ) = {1,..., n1 }. Пусть 0 — граф, полученный “стягиванием” всех ребер и вершин в одну точку. Множеством его вершин будет {1, 2,..., m}, причем вершина cоответствует всем вершинам, вершины j — вершинам n1 + j при 2 j m 1. Множество ребер 0 устроено следующим образом. Ес ли e — ребро, соединяющее вершины j и t, где j, t n1, то ему соответствует ребро 0, соединяющее вершины j n1 и t n1. Для любого j n1 либо не существует ребер, cоединяющих j с верши нами 1,..., n1, либо каждая вершина 1,..., n1 соединена с j одним и тем же количеством (например, k ) ребер. В этом случае в 0 вершина 1 должна быть соединена с вершиной j n1 ровно k ребрами. Пусть 1 =, 2 =... = m = E. Тогда, сравнивая c 0 1... m, прямо из определения делаем вывод об изоморфности этих графов.

6.1.3. Пусть = 0 1 E... E для некоторого графа 0. Тог Лемма да существуют графы 0 и, такие что = 0 E... E, и в 0 нет петель, инцидентных вершине 1.

Доказательство. Если в 0 нет петель, инцидентных вершине 1, то 0 = 0, = 1, и все доказано. В противном случае, пусть — подграф 0 с единственной вершиной 1, ребра которого — всевозможные петли, инцидентные этой вершине.

Пусть 0 — граф, получаемый из 0 стягиванием (т.е. фактически удалением) всех ребер. Множество вершин у 0 то же, что и у 0, но в 0 уже нет петель, инцидентных вершине 1. Кроме того, очевидно, что 0 = 0 E... E (где тривиальные графы E соответствуют вершинам 0, не входящим в ). Отсюда 0 1 E... E = (0 E... E)1 E... E = 0 (1 )(EE)... (EE) = 0 (1 )E... E, и можно взять = 1.

Лемма 6.1.4. Пусть = 0 1... n1 n1 +1... m и выполнены следую щие условия:

a) 1,..., n1 — дискретные графы (т.е. в них отсутствуют ребра);

b) В 0 имеется фрагмент (0, ), такой что V ( ) = {1,..., n1 }.

0 Тогда в можно выбрать фрагмент (, ), такой что.

= Если к тому же (0, ) — разлагающий фрагмент, то и (, ) можно выбрать разлагающим.

Доказательство. Воспользуемся приведенной выше леммой, в которой строится подграф, изоморфный 0. Пусть — подграф, являющийся образом при этом изоморфизме, а строится следующим образом. Положим V ( ) = V (j ), и если v1 V (j1 ), v2 V (j2 ), jV ( ) то ребра V ( ), cоединяющие v1 и v2, имеют вид ev1,v2, где e V ( ) и соединяет j1 и j2. Проверим условия 1) и 2) из определения фрагмента.

Пусть v1, v2 V ( ). Это значит, что v1 V (i1 ), v2 V (i2 ), i1, i2 — вершины 0 и вершины, так что 1 i1, i2 n1. Пусть e — ребро, инцидентное v1 и v2. Допустим, что v1 = v2 = v. Тогда по построению должно быть i1 = i2 = i. Так как в i нет петель, то e = uv,v, где u — петля в 0, инцидентная вершине i. Так как i V ( ), то из условия 1) определения фрагмента, получаем для фрагмента (0, ), что u E( ).

0 Отсюда, по определению будем иметь uv,v E( ). Если же v1 = v2, то в этом случае i1 = i2, и ребро e автоматически имеет вид uv1,v2 для некоторого ребра u V (0 ), инцидентного i1 и i2. Но это ребро обязано принадлежать E( ), и по построению uv1 v2 E( ).

Пусть теперь даны вершины v V ( ), v V () и соединяющее их ребро e E(). Условие a) исключает случай, когда v и v принадле жат одному и тому же i, 1 i m. Пусть v V (i ), v V (j ), i = j.

Тогда e = uv,v, где u — ребро 0, cоединяющее вершины i V ( ) и j. По определению фрагмента должно быть j V (0 ) и u E(0 ). Это означает, что v V ( ) и e = uv,v E( ).

Пусть фрагмент (0, ) — разлагающий. Проверим условие 3) для фрагмента (, ). Пусть v V ( ), v V (i ), 1 i n1, v V ( ), v V (j ), j n1, и имеется ровно k ребер e(1),..., e(k), соединяющих в вершины v и v. Так как j = i, то все эти ребра имеют вид e(t) = (t) ui,j, где u(1),..., u(k) — ребра 0, cоединяющие вершины i и j. Пусть дана другая вершина u V ( ), u V (p ), 1 p n1. В 0 имеется ровно k ребер, соединяющих вершину j с вершиной p. Если w(1),..., w(k) (1) (k) — эти ребра, то им соответствуют в ровно k ребер wi,p,..., wi,p, соединяющих вершины u и v. По определению операдной композиции графов других ребер, соединяющих u и v, быть не может.

Теорема 6.1.4. Граф Gr(n) разложим тогда и только тогда, ког да он содержит нетривиальный разлагающий фрагмент.

Доказательство. Пусть = 0 1... m — нетривиальное раз ложение. Можно считать, что 1 = E, и пусть n1 = |V (1 )|. Тогда = 0 1... m = (0 1 E... E )(E... E 2... m ).

n m По доказанному выше можно считать, что 0 = 0 1 E... E = E... E, где — граф без петель, инцидентных вершине 1, и тогда 00 (0, ) — разлагающий фрагмент в 0. Из леммы 6.1.4 теперь следует, что разлагающий фрагмент существует и в.

Обратно, пусть в существует нетривиальный разлагающий фраг мент (, ). Согласно замечанию 6.1.1, можно считать, что =. Тог да из леммы 6.1.4 следует, что 0 E... E то есть разложим.

= Аналогично тому, как это сделано выше, определяется операда простых помеченных графов без петель Gr0 = {Gr0 (n)|n 1}. Опре деление разлагающего фрагмента, его свойства, формулировка и доказа тельство теоремы 6.1.4. для случая простых графов остаются теми же самыми.

Теорема 6.1.5. Простой граф без петель с не менее чем тремя вер шинами операдно неразложим тогда и только тогда, когда он удовле творяет следующему свойству: для любого 2 n |V ()| и любых n вершин v1,..., vn найдется вершина v {v1,..., vn }, и вершины vi и vj, i = j, такие, что v соединена ребром с vi, но не соединена ребром с vj.

Доказательство. Утверждение теоремы логически равносиль но утверждению аналога теоремы 6.1.4 для простых графов. Точ нее, утверждение “ разложим существует разлагающий фрагмент (, )” логически равносильно утверждению “ неразложим для лю бого фрагмент (, ) не является разлагающим”, что сводится к тому, что для любого нарушено свойство 3) из определения разла гающего фрагмента. В формулировке этого свойства участвуют толь ко вершины v1,..., vn подграфа, и его невыполнение означает, что найдется вершина v V ( ), которая соединена ребрами не со всеми вершинами (с некоторыми соединена, с некоторыми — нет).

Теорема 6.1.6. Пусть — простой связный граф без петель. Допус тим, что не содержит подграфов, изоморфных K3 (треугольников), а также подграфов, изоморфных Kn,m (n 2), устроенных следующим образом. Это подграфы с вершинами v1,..., vn, u1,..., um, причем каж дая вершина vi соединена ребром с каждой вершиной uj, а вершины vi могут быть соединены в ребрами, кроме вершин вида uj, только с вершинами вида vk. Тогда граф операдно неразложим.

Доказательство. Рассмотрим разложимый граф (простой, связный, без петель), и пусть — ядро разлагающего фрагмента, v1,..., vn (n 2) — вершины. Пусть u1,..., um — все вершины, соединенные ребрами с вершинами. Ввиду связности имеем m 0.

Если не дискретен, то две его вершины vi и vk, соединенные ребром, вместе с вершиной uj образуют подграф, изоморфный K3. Если даже дискретен, то подграф с множеством вершин v1,..., vn, u1,..., um, и множеством ребер, соединяющих вершины vi с вершинами uj, изоморфен Kn,m, и устроен так, как это описано в формулировке теоремы. Если же в нет таких подграфов, то не существует и нетривиальных разлагающих фрагментов.

Применим теорему 6.1.6. для решения вопроса о неразложимости двух семейств графов.

Пример 6.1.3. Рассмотрим семейство графов — многомерных ку бов Qn. Вершины Qn — последовательности нулей и единиц длины n, x = (x1,..., xn ), xi = 0 или xi = 1, |V (Qn )| = 2n. Две верши ны x и y считаются соединенными ребром, если расстояние Хэмминга d(x, y) = |{i|xi = yi }| между ними равно единице. Покажем, что при n граф Qn операдно неразложим. Q2 разложим: Q2 = 1 2 K2, где 1 = — дискретные графы с двумя вершинами. Покажем, что при n 2 в Qn нет ни треугольников, ни подграфов Kn,m такого вида, который опи сан в теореме 6.1.6. Пусть в Qn существует треугольник с вершинами x = (x1,..., xn ), y = (y1,..., yn ), z = (z1,..., zn ), d(x, y) = d(y, z) = d(x, z) = 1. Допустим, что x1 = y1, x2 = y2,..., xn = yn. Для z рас смотрим два случая. Если z1 = x1, то из d(x, z) = 1 следует, z2 = x2 = y2,..., zn = xn = yn. Но из x1 = y1, x1 = z1 следует y1 = z1 и y = z. Если же z1 = x1, и например, z2 = x2 = y2, z3 = x3 = y3,..., zn = xn = yn. то получается, что z1 = x1 = y1, и z2 = y2, d(z, y) = 2, что невозможно. Сте пень каждой вершины Qn равна n. Пусть x, z — две различные верши ны, имеющие один и тот же набор смежных вершин y 1,..., y n. Покажем, что этого не может быть. Можно считать, что y i = (x1,..., xi,..., xn ), где xi = 0, если xi = 1, и xi = 1, если xi = 0. Тогда существует нееди ничная подстановка n такая, что y (i) = (z1,..., zi,..., zn ). Выберем i так, чтобы (i) = i. Тогда x и y (i) отличаются только в (i)-й ком поненте (и только в ней), y (i) и z отличаются только в i-й компоненте.

Так как (i) = i, x и z отличаются друг от друга и в i-й, и в (i)-й ком понентах. Допустим, что существует j = i, j = (i), такой, что j = (j).

Тогда, рассуждая аналогичным образом, приходим к выводу, что x и z различаются в j -й и (j)-й компонентах. Не исключается, что (j) = j, но, по крайней мере, d(x, z) 3. Однако из d(x, yi ) + d(yi, z) d(x, z) следует, что одно из чисел d(x, yi ), d(yi, z) строго больше единицы — про тиворечие. Допустим теперь, что — транспозиция, (i) = k, (k) = i, и (j) = j при j = i, k. При n 3 такой j существует. Сравнивая x, y i = y (k), y k = y (i), y j = y (j) с z, заключаем, что z и y j различаются сразу в трех компонентах: в i-й, j -й и k -й. Полученное противоречие показывает, что в Qn при n 3 не существует подграфа, изоморфного Kp,q, удовлетворяющего условию из теоремы 6.1.6.

Пример 6.1.4. Опишем разлагающие фрагменты в деревьях. Бу дем называть вершину дерева T внешней, если ее степень равна единице, и внутренней в противном случае. Гроздью в дереве T назовем поддере во T c вершинами v1,..., vk, v0, k 2, где v1,..., vk — внешние для T вершины, а v0 — внутренняя для T вершина.

Утверждается, что наличие гроздьев в дереве равносильно наличию разлагающих фрагментов. Точнее, если T — гроздь, T — дискретный подграф с вершинами {v1,..., vk }, то (T, T ) — это разлагающий фраг мент дерева T. Это сразу следует из определений.

Обратно, пусть (T, T ) — разлагающий фрагмент T. Пусть v1,..., vk — вершины T. Должна существовать вершина v0 V (T ), v0 V (T ), cоединенная ребром с одной из вершин T (а значит, по определению, и со всеми). Иначе, так как все вершины T, cоединенные ребрами с вершинами из T, содержатся в T, нарушилось бы условие связности T. Итак, v0 cуществует, но тогда не существует другой та кой вершины u0 V (T ), u0 V (T ), cоединенной ребрами со всеми v1,..., vk. В противном случае в графе T были бы циклы (здесь важно то, что k 2). По той же причине не существует ребер, соединяющих различные vi и vj при i = j, i, j 1. Итак, подграф T является гроздью, и T — множество его внешних вершин.

Некоторые операды ориентированных простых графов Точно так же, как и для неориентированных графов, можно опре делить операду, элементами компонент которой будут ориентированные графы. Достаточно определение операды Gr дополнить так, чтобы учи тывалось направление ребер (которые в случае ориентированных графов, называенмых также орграфами, именуются дугами или стрелками). Та ким образом, операдная композиция Dir(m) Dir(n1 ) · · · Dir(nm ) Dir(n1 + · · · + nm ), (0, 1,..., m ) 0 1... m.

устроена следующим образом. Пусть 0 — ориентированный граф с вершинами 1,..., m, и пусть для каждого i, 1 i m дан ориенти рованный граф i с вершинами 1,..., ni. Тогда = 0 1... m есть ориентированный граф с вершинами 1,..., n = n1 + · · · + nm, причем вершина n1 + · · · + ni1 + j, 1 j ni, соответствует вершине j графа i, и если в i вершина i соединена дугой с вершиной k, то в вершина n1 + · · · + ni1 + j соединена дугой с n1 + · · · + ni1 + k. Таким образом, для всех i в имеются подграфы с вершинами n1 +· · ·+ni1 +1,..., n1 +· · ·+ ni1 + ni, изоморфные i, которые часто бывает удобно отождествлять с i. Кроме того, если в 0 имеется дуга, направленная из вершины i в вершину t, то в определены дуги, выходящие из всех вершин подграфа i и входящие в каждую вершину подграфа t.

В дальнейшем мы будем рассматривать только простые ориенти рованные графы (без петель), то есть такие графы, в которых из одной вершины в другую проведена не более чем одна дуга.

Простому ориентированному графу, вершины которого снабже ны метками 1,..., n сопоставляется его матрица смежности A(), i, j -й элемент которой равен единице, если в графе существует дуга (стрел ка) из вершины i в вершину j. Если такой дуги нет, то элемент равен нулю. Отсутствие петель означает, что на диагонали матрицы смежнос ти стоят нули. Очевидно, что таким образом устанавливается взаимно однозначное соответствие между множеством Dir(n) и некоторым под множеством множества GM2 (n).

Практически так же, как и аналогичная теорема для неориентиро ванных графов, доказывается следующая Теорема 6.1.7. Семейство множеств Dir = {Dir(n)|n 0} c опреде ленной на них выше операцией композиции и действием симметрических групп является операдой. Единица операды — граф E, состоящий из одной вершины и пустого множества дуг. Нулевую компоненту можно предполагать либо пустой, либо одноэлементной.

Соответстввие A() является инъективным гомоморфиз мом -операд Dir GM2, где GM2 рассматривается с композицией 1, а G = {0, 1}.

Далее будет описано несколько интересных подоперад операды Dir.

Все графы предполагаются конечными.

Круговые турниры (далее — просто турниры), по определению яв ляются ориентированными простыми графами, обладающими тем свой ством, что в них для любых двух различных вершин i, j всегда сущест вует либо дуга, направленная из i в j, либо дуга из j в i. Некоторую информацию о турнирах можно найти в большинстве учебников по те ории графов (см., например, [93], [23]). Обозначим через T our(n) мно жество всех помеченных турниров с n вершинами. Если T our(n) и A = A(), то для любых i = j верно ровно одно из двух: либо ai,j = 1, aj,i = 0, либо aj,i = 1, ai,j = 0. Будем называть такие матри цы матрицами турниров. Положим T our = {T our(n)|n 1}.

Теорема 6.1.8. T our есть подоперада операды Dir.

Доказательство. Необходимо убедиться, что если A, B1,..., Bn — матрицы турниров, то AB1... Bn — также матрица турнира, и если A T our(n), n, то A T our(n). Это делается непосредственной проверкой, исходя из приведенных выше определений.

В книге [94] на с. 16 описано взаимно-однозначное соответствие между компонентами T our(n) и Gr0 (n) операд T our и Gr0, при кото ром турниру T с вершинами 1,..., n сопоставляется неориентирован ный граф n T с теми же вершинами, такой, что вершины i и j в нем смежны в том и только в том случае, если при i j в турнире T имеется дуга (i, j), т.е. стрелка вида i j.

Теорема 6.1.9. Семейство биекций = {n |T our(n) Gr0 (n)|n 1} яваляется изоморфизмом несимметрических операд T our и Gr0 (т.е.

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

Доказательство. Необходимо убедиться, что если T0 T our(m), Ti T our(ni ), 1 i m, n = n1 + · · · + nm, то n (T0 T1... Tm ) = (m T0 )(n1 T1 )... (nm Tm ). Речь идет о совпадении двух помеченных графов с одним и тем же множеством вершин, снабженных метками 1, 2,..., n. Следовательно, надо показать, что смежные вершины одного графа смежны и в другом, и наоборот.

Можно считать Ti подтурниром турнира T0 T1... Tm с вершинами n1 + · · · + ni1 + 1,..., n1 + · · · + ni1 + ni, и граф ni Ti — подгра фом (m T0 )(n1 T1 )... (nm Tm ) с такими же вершинами. Если j, k — вершины Ti, j k, и в Ti существует дуга j k, то дуга j k определена и в T0 T1... Tm, а значит, j и k смежны в n (T0 T1... Tm ).

С другой стороны, j и k будут смежными в ni Ti, а следовательно, и в (m T0 )(n1 T1 )... (nm Tm ). Если в турнире T0 существует дуга i l, причем i l, то для каждой вершины j подтурнира Ti турнира T0 T1... Tm и любой вершины k подтурнира Tl определена дуга j k, причем i l. Это значит, что вершины j и k смежны в n (T0 T1... Tm ).

С другой стороны, i и l будут смежными в m T0, и потому в графе (m T0 )(n1 T1 )... (nm Tm ) любая вершина n1 Ti должна быть смежной с каждой вершиной nl Tl. Исходя из определения операдных композиций в T our и G, легко заметить, что проведенное рассуждение охватывает все возможные ребра рассматриваемых графов, которые, таким образом, совпадают.

Рассмотрим цикл C длины три, т.е. турнир вида: 1 2 3 1.

Отображение 3 переводит его в граф 3 C с вершинами 1, 2, 3, в котором вершины 1 и 2, а также 2 и 3 являются смежными. В то же время турнир 1 3 2 1 отображается в граф с вершинами 1, 2, 3, в котором вершины 1 и 3 смежны, а вершина 2 является изолированной.

Этот граф нельзя получить из 3 C перестановкой меток вершин, и это означает, что не является гомоморфизмом симметрических операд.

Чтобы убедиться в том, что изоморфизма между T our и Gr как симметрическими операдами вообще быть не может, достаточно сравнить количество операдно неразложимых элементов в компонентах T our(n) и G(n) для небольших значений n. Уже при n = 3 равенство отсутствует.

Рассмотрим семейство P OS = {P OS(n)|n 1}, где P OS(n) есть подмножество Dir(n), состоящее из всех матриц A, элементы кото рых удовлетворяют следующему свойству: если ai,j = 1 и aj,k = 1, то ai,k = 1. Отождествляя матрицы с графами, легко заметить, что элемен ты P OS(n) — это в точности трпанзитивные ориентированные графы с вершинами 1,..., n. Матрицы из P OS(n) находятся также во взаимно однозначном соответствии с конечными частично упорядоченными мно жествами, элементы которых помечены числами 1,..., n. В самом деле, если A P OS(n) и En — единичная n n-матрица, то матрица En + A задает на множестве {1,..., n} частичный порядок: i меньше или равно j тогда и только тогда, если i, j -й элемент En + A равен единице. Об ратно, любой частичный порядок на {1,..., n} полностью определяется матрицей B из нулей и единиц, обладающей аналогичным свойством. В этом случае, как легко заметить, B En P OS(n).

Теорема 6.1.10. Семейство P OS = {P OS(n)|n 1} является подо перадой операды Dir.

Доказательство. Достаточно показать, что если 0, 1,..., m — транзитивные графы, то граф = 0 1... m также будет транзитив ным. Рассмотрим три вершины a, b, c графа, и предположим, что в определены дуги a b и b c. Как и выше, будем при i 1 отож дествлять i с подграфом. Если все три вершины a, b, c принадлежат одному и тому же i, то дуга a c существует ввиду транзитивности i. Если, например, a, b i, c j, где i = j, то, по определению опе радной композиции в Dir, в графе 0 должна существовать дуга i j.

Но тогда все вершины i должны быть соединены дугами со всеми вер шинами j, а значит, существует и дуга a c. Если же a i, b j, c k, где i, j, k попарно различны, то это значит, что в 0 существуют дуги i j и j k. Так как граф 0 транзитивен, то существует и дуга i k, и тогда по определению = 0 1... m каждая вершина i должна быть соединена дугой с каждой вершиной k. Случай a, c i, b j невозможен, так как в 0 не может быть одновременно дуг i j и j i.


Рассмотрим пересечение P OS T our подоперад операды Dir. По определению, n-я компонента этой операды есть множество P OS(n) T our(n).

Лемма 6.1.5. Элементы P OS(n) T our(n), рассматриваемые как частично упорядоченные множества, суть в точности все линейно упорядоченные помеченные множества из n элементов.

Доказательство. Если частично упорядоченное множество (как элемент P OS(n)) принадлежит T our(n), то это означает, что любые два его элемента сравнимы. Обратно, если A P OS(n) интерпретируется как линейно упорядоченное множество, то в A, интерпретируемом как ориентированный граф, для любых двух различных вершин существует дуга, соединяющая одну из вершин с другой.

Ввиду этой леммы операду P OS T our естественно обозначить через LOS (подразумевая очевидную аббревиатуру). Имеет место сле дующая диаграмма операд и их гомоморфизмов, в которой все стрелки являются естественными вложениями.

Dir T our P OS LOS Теорема 6.1.11. Имеет место изоморфизм операд: LOS O.

= Доказательство. Напомним, что O есть -операда, строяща яся исходя из вербальной категории (§ 3.4). Опишем более подробно операцию композиции в LOS. Элемент 0 LOS(m) можно представить в виде i1 i2 · · · im, где {i1,..., im } = {1,..., m}, и подразуме вается, что остальные дуги этого графа — это последовательности дуг вида ik ik+1 · · · ik+d. Рассмотрим для каждого i, 1 i m, эле мент i LOS(ni ). Его также можно представить в виде j1 · · · jni.

Из приведенного выше описания 0 1... m следует, что для элементов операды LOS все сводится к подстановке вместо вершины i 0 выра жения j1 · · · jni с последующей перенумерацией: вместо js должна стоять метка n1 + · · · + ni1 + js. При этом, если в 0 вершины i = ir и i = ir+1 располагаются по соседству, т.е. имеется дуга i i, и i пред ставляется в виде j1 · · · jni, то в 0 1... m будет присутствовать фрагмент j1 · · · jni j1 · · · jni, причем вершины должны быть перенумерованы так, как было описано выше.

Взаимно-однозначное соответствие между множествами LOS(m) и (m) = n таково. Частично упорядоченному множеству, записывае ( ) мому в виде i1 i2 · · · im, сопоставляется подстановка 1i12 2... m.

i... im Результат действия элемента m на — частично упорядоченное множество (i1 ) (i2 ) · · · (im ), и это соответствует умножению ( ) слева на 1i12 2... m. Покажем, что если элементу 0 LOS(m) соот i... im ветствует m, а элементам i LOS(ni ) для всех i, 1 i m, соответствуют подстановки i, то элементу 0 1... m соответствует подстановка 1... m n1 +···+nm.

Напомним (см. § 3.4), как устроена операдная композиция в O.

Пусть = (n1,..., nm ). Тогда 1... m = ( )((1) · · · (m) ). На помним, как устроены компоненты этого произведения. Пусть 1 i m, 1 j n(i). Подстановка n, n = n1 + · · · + nm, отображает сим вол n(1) + · · · + n(i1) + j в n1 + · · · + n(i)1 + j. Предполагается, что n0 = n(0) = 0. Будем рассматривать подстановки из n как таблицы из двух строк символов, расположенных друг над другом, где верхняя стро ка имеет вид 1... n. Пусть bi — подстрока этой строки следующего вида:

(n1 + · · · + ni1 + 1)... (n1 + · · · + ni1 + ni ), 1 i m. Из определения следует, что верхняя строка этой таблицы — это b1... bm, а нижняя — b(1)... b(m). Таким образом, можно формально получить, подстав ( ) ляя в = 1i12 2... m вместо символов i строки bi. С другой стороны, опре i... im делим ci как строку (n(1) + · · · + n(i1) + 1)... (n(1) + · · · + n(i1) + n(i) ).

Длина строки ci равна n(i), как и длина строки b(i), и подстановку ( c1... m ) можно записать следующим образом: = b(1)... bc(m).

Рассмотрим теперь подстановку = (1) · · · (m). По определе нию, (n(1) + · · · + n(i1) + j) = n(1) + · · · + n(i1) + (i) (j) для всех i, ( ) 1 i m, и 1 j n(i). Таким образом, = c1...cm, где ci — строки,...c c m которые получаются из строк ci перестановками символов по правилам, определяемым подстановками (i). Рассматривая произведение ( ), ( ) теперь легко убедиться, что оно имеет следующий вид: bc1... bcm. Здесь...

(1) (m) b(i) есть результат перестановки символов строки b(i) по правилу, опре деляемому подстановкой (i). Остается заметить, что это именно та под становка, которая соответствует графу 0 1... m при описанном выше соответствии. В самом деле, нижнюю строку ( ) можно описать как результат подстановки в нижнюю строку подстановки вместо каждого символа i нижней строки подстановки i, с последующей перенумераци ей, точно такой же, какая происходит при построении 0 1... m.

Подоперады операды турниров, порожденные простыми турнирами Определение простого турнира (см., например, [44]) на операдном языке сводится к тому, что простым является турнир, который нельзя представить в виде нетривиальной операдной композиции (0 1... m ).

Нетривиальность означает, что m 1 и не все i при i 1 равны одновершинному графу без дуг, который выше был обозначен через E.

Разумеется, когда используется операдная композиция, то речь должна идти о помеченных турнирах, т.е. о турнирах, множество вершин кото рых есть {1,..., n}. Таким образом, простой турнир — это то же самое, что операдно неразложимый (в операде T ourn) турнир.

Примером простого турнира является турнир C, уже появлявший ся в предыдущем разделе. Если расматривать непомеченные турниры, то это единственный простой турнир с тремя вершинами. Простых тур ниров с четырьмя вершинами не существует. Дальнейшую информацию можно найти в [44] и [105]. Зафиксируем некоторый простой турнир с m 2 вершинами. и рассмотрим подопераду операды T our, порож денную турниром. Обозначим эту подопераду через T our. Турниры, принадлежащие T our, можно описать следующим образом. Компонента T our (1) состоит из тривиального одновершинного турнира E, Компо нента T our (m) состоит из всех турниров вида, где m. Если уже определены Ti T our (ni ), 1 i m, то T our (n1 +· · ·+nm ) содер жит все турниры вида (T1... Tm ), где n1 +···+nm. Других турниров в T our не содержится.

В дальнейших рассуждениях будут встречаться выражения вроде “Турниры T1 и T2 равны с точностью до перенумерации вершин”. Это будет означать, что если V (T1 ) и V (T2 ) — множества вершин в T1 и T2 соответственно, то существует биективное отображение из V (T1 ) в V (T2 ), индуцирующее изоморфизм ориентированных графов T1 и T2.

Например, если V (T1 ) = V (T2 ) = {1,..., n}, то это означает, что су ществует подстановка n со свойством T2 = T1.

Будет также использоваться следующее обозначение. Если 1 и — некоторые орграфы, то через 1 2 обозначается граф, состоящий из непересекающихся подграфов 1 и 2, причем из каждой вершины проведена единственная дуга (стрелка) в каждую вершину 2.

Лемма 6.1.6. Пусть T our (n), и 1 k m. Тогда нельзя предствить в виде (0 1... k ), где 0 T our(k), j при 1 j k — некоторые турниры (не обязательно из T our ), и n.

Доказательство. Проведем индукцию по n = |V ()|. При n = m должно быть =, и утверждение следует из простоты турнира. В общем случае предположим, что с точностью до перенумерации вершин турнир имеет вид 0 1... m, где 0 =, и все i принадлежат опе раде T our, и для них должно выполняться предположение индукции.

Допустим, что = 0 1... k, и k m. Нумерация вершин в дальней ших рассуждениях не играет существенной роли, поэтому можно отож дествить все i и j при i, j 1 с подграфами турнира. Для всех i 1 имеют место равенства:

k (i j ) i = (6.1.11) j= Самой существенной особенностью разложения (6.1.11) является то, что для любых двух индексов j, l, таких что i j = и i l =, если в имеется дуга j l, то в i содежится подграф i j i l, а если в имеется дуга l j, то в i содержится подграф i l i j.

Допустим сначала, что для некоторого i, 1 i m, такого, что турнир i нетривиален, хотя бы одно пересечение i j есть турнир с не менее чем двумя вершинами, причем i j. Тогда из соотношения (6.1.11) следует, что существует нетривиальное операдное разложение вида i =..., где l k m, и турниры — это непустые пересечения 01 t l i j. Разумеется, такое представление рассматривается с точностью до перенумерации вершин. Но тогда по предположению индукции для i отсюда получается противоречие.

Случай, когда для некоторого i турнир i нетривиален, но во всех пересечениях i j имеется не более одной вершины, невозможен, так как в нетривиальном i не менее m вершин, и m k.

Остается разобрать случай, когда для каждого i существует j та кой, что i j. Так как m k, то отсюда следует, что по крайней мере один турнир j есть объединение более чем одного i. Это приводит к противоречию с простотой турнира.

Лемма 6.1.7. Любой турнир из T our однозначно представляется в виде (1... m ), где i — турниры из T our. Более конкретно, если = 1... m = (1... m ), то существует подстановка m такая, что для всех i 1 имеют место равенства i = (i). Более того, если 1... m = 1... m, то i = i для всех i.

Доказательство. Вновь используем соотношение (6.1.11), пола гая в нем k = m. Если для какого-либо i 1, для которого турнир i нетривиален, и i = l ни для какого l, существует j такой, что i j =, то i можно (с точностью до некоторой перенумерации вершин) представить в виде нетривиальной операдной композиции ви да..., где s m. По лемме 6.1.6 получаем противоречие.

01 s Пусть для каждой пары неравных i, j имеет место i j =.

Рассмотрим дугу i j в турнире. Тогда в существуют подграфы i j и i j. Рассмматривая подграфы i j и j i, полу чим противоречие, так как зможно, чтобы в турнире одновременно существовали подграфы i j j i и j i i j.

Таким образом, единственной непротиворечивой возможностью остается случай, когда каждый i равен некоторому (однозначно опре деленному) j. Искомая подстановка определяется равенством j = (i).


Допустим, что = 1... m = 1... m. Положим ni = |V (i )|, nj = |V (j )|. Пусть 1 = 1,..., s = s, как подграфы (здесь s 0).

Вспоминая, каким образом должны быть перенумерованы вершины тур ниров i и j, когда эти турниры рассматриваются как подтурниры, заключаем, что если, например, ns+1 ns+1, то s+1 s+1. Но по доказанному выше должна существовать подстановка со свойст вом i = (i) для всех i. При i = s + 1 получаем, что (s+1) s+1.

Однако, если (s + 1) = s + 1, то (s+1) и s+1 не могут пересекаться по определению операдной композиции. Отсюда следует, что (s + 1) = s + и s+1 = s+1. Поскольку это верно для всех s 0, заключаем, что есть тождественная подстановка, и последнее утверждение леммы дока зано.

Замечание 6.1.2. Лемма 6.1.7 неверна для простого турнира 1 2. Обозначая этот турнир через T, будем иметь легко проверяе мое равенство: T T E = T ET.

Теорема 6.1.12. Операда T our изоморфна факторопераде свободной -операды F O с базисом, состоящим из одного элемента F O (m), по конгруэнции, порожденной элементами (, ) F O (m) F O (m), где Aut() — группе автоморфизмов турнира.

Доказательство. Рассмотрим сюръективный на всех компонен тах гомоморфизм -операд : F O T our, отображающий базисный элемент в турнир. Так как = при Aut(), то конгруэн ция C, порожденная всеми парами (, ), где Aut(), содержится в ядре гомоморфизма. Напомним, что Ker() = {Ker()(n)|n 1}, где Ker()(n) = {(w1, w2 ) F O (n) F O (n)|n (w1 ) = n (w2 )} — это подоперада прямого произведения операд F O F O.

Для того, чтобы установить, что Ker() C, рассмотрим произ вольный элемент из Ker()(n). Ввиду данного выше описания T our, можно считать, что этот элемент имеет вид ((1... m ), 1... m ).

Будем показывать, что этот элемент принадлежит C(n) индукцией по n и по максимальному числу вхождений символа в слова ((1... m ) и 1... m ). Обозначим это число через r. В случае n = 1 все очевидно.

Предположим, что наше предположение выполнено для чисел, меньших n и r.

Покажем, что из ((1... m ), 1... m ) Ker() следует, что = (p )(1 · · · m ), где p Aut(), и если i T our (ni ), то = (np1 (1),..., np1 (m) ), и i np1 (i) для всех i.

Пусть Ti = (i ), Ti = (i ) — турниры из T our, 1 i m, тогда из ((1... m ), 1... m ) Ker() следует равенство (T1... Tm ) = T1... Tm.

Пусть = (T1... Tm ) = T1... Tm. Можно считать, что подста новка не является единичной. Через ni обозначим количество вершин в Ti, а через ni — количество вершин в Ti, 1 i m. Будем считать, что Ti — подграф турнира с вершинами n1 + · · · + ni1 + 1,..., n1 + · · · + ni, где 1 i m и n0 = 0, а Ti — подграф T1... Tm с вершинами n1 +· · ·+ni1 +1,..., n1 +· · ·+ni, где 1 i m и n0 = 0. Через Ti обозна чим подграф с вершинами (n1 + · · · + ni1 + 1),..., (n1 + · · · + ni1 + ni ), где вершина (a) соединена с вершиной (b) дугой в том и только в том случае, если вершина a соединена дугой с b.

Из леммы 6.1.7 следует, что существует подстановка m такая, что T(i) = Ti, 1 i m. Таким образом, по определению операдной композиции ориентированных графов, дуга i j присутствует в в тур нире тогда и только тогда, если в турнире присутствует подграф Ti Tj, или же в том и только в том случае, если в имеется подграф Ti Tj. Если Aut(), то в найдется дуга i j такая, что дуги (i) (j) в уже не будет. В этом случае, однако, в должен присутствовать подграф Ti Tj. Но так как Ti = T(i) и Tj = T(j), то в присутствует подграф T(i) T(j). Но отсюда следует, что в турнире должна присутствовать дуга (i) (j). Полученное противоречие показывает, что подстановка принадлежит группе автоморфизмов тур нира.

Заметим, далее, что из T(i) = Ti, 1 i m, следует, что для каждого i существует подстановка i n (i) = ni такая, что T (i) i = Ti. Положим p = 1 и = (n (1),..., n (m) ). Тогда T (1)... T (m) = (p)T (1)... T (m) = (T1... Tm )(p ).

Следовательно, (T1... Tm )(p )(1 · · · m ) = T (1)... T (m) (1 · · · m ) = = (T (1) 1 )... (T (m) m ) = T1... Tm.

Итак, подстановки и = (p )(1 · · · m ) действуют на турнире T1... Tm одинаковым образом. По определению этого действия, биектив ные отображения и должны принимать одни и те же значения на мет ках всех вершин данного турнира. Следовательно, = (p )(1...m ).

Кроме того, из установленных выше равенств T (i) i = Ti следу ет, что ( (i) i, i ) Ker()(ni ), причем к этим элементам применимо предположение индукции, то есть они принадлежат C(ni ) для всех i.

Теперь можно проделать следующие вычисления:

((1... m ), 1... m ) = ((1... m )(p )(1 · · · m ), 1... m ) = ((p)( (1) 1 )... ( (m) m ), 1... m ) = (p, )( (1) 1, 1 )... ( (m) m, m ).

Очевидно, что правая часть этого равенства принадлежит конгруэнции C.

Замечание 6.1.3. Теорема 6.1.12 неверна для простого турнира 1 2. В замечании 6.1.2 уже отмечено, что для такого турнира неверна лемма 6.1.7, а следовательно, и основанное на ней доказательство тео ремы 6.1.12. С другой стороны, группа автоморфизмов турнира 1 тривиальна. Если бы утверждение теоремы 6.1.12 выполнялось для это го турнира, то порожденная им операда LOS должна быть свободной.

Но, как показано в теореме 6.1.11, эта операда не является свободной.

Таким образом, теорема 6.1.12 справедлива лишь для простых турниров с не менее чем тремя вершинами.

Замечание 6.1.4. Теоремы 6.1.11 и 6.1.12 дают полное описание подоперад операды T our, порожденных простыми турнирами. Имеется предположение, что операда T our может быть описана как копроизве дение (в категории -операд) всех этих подоперад. Для доказательст ва (или опровержения) этого предположения необходимо более глубокое знание свойств разложения турниров в операдную композицию простых турниров.

§ 6.2. Линейные операды многомерных матриц В данном параграфе будут рассматриваться правые K -линейные операды, где K — коммутативное ассоциативное кольцо или полукольцо с единицей. Это объясняется тем, что именно в таком виде данный мате риал первоначально был опубликован в работе [59]. Очевидным образом существуют левые аналоги всех содержащихся в этом параграфе опре делений и утверждений. Напомним, что если R — правая K -линейная симметрическая операда (т.е. -операда), то это означает, что каждая компонента R(n) (при n 0) является левым Kn -модулем (или полу модулем, если K полукольцо), и определены операции композиции вида R(n1 )· · ·R(nm )R(m) R(n1 +· · ·+nm ), (1,..., m, ) 1... m, K -линейные по каждому аргументу (исключая, может быть, компоненты R(0)). Должны также выполняться правые аналоги тождеств операды, сформулированные в главе 2.

Причиной того, что в [59] были выбраны в качестве исходных пра вые, а не левые операды, является еще и то, что в теории эквивалент ности Мориты для колец и модулей чаще всего изложение происходит в терминах правых модулей. В будущую теорию эквивалентности Мори ты для операд правые и левые операды должны входить на равноправной основе.

Отметим еще, что результат, аналогичный части утверждений на шей теоремы 6.2.3 (эквивалентность категорий Alg(R) и категории ал гебр над операдой матриц над R), был получен совершенно другим спо собом в работе [131], опубликованной позднее нашей работы [59].

Пусть R — некоторая правая K -линейная операда, X — про извольное множество. Построим правую матричную операду M = M (X, R), являющуюся операдным обобщением кольца (или полуколь ца) |X| |X|-матриц над ассоциативным кольцом (или полукольцом).

(В дальнейшем в этом параграфе слово “правая”, когда речь идет об операдах, будет подразумеваться.) Положим M(n) равным множеству всех отображений из X n X в R(n), таких, что для каждого y X имеет место (x, y) = 0 для почти всех x X n. (Сразу же отметим, что можно было бы определить другую матричную операду, предполагая, что для каждого x X n y X имеет место (x, y) = 0 для почти всех y X.

В случае конечного X, который и будет в основном рассматриваться в этом параграфе, обе этих операды совпадают.) Определим левое действие n на M(n), полагая ()(x1,..., xn, y) = ((x(1),..., x(n), y)) Введем теперь операдную композицию. Пусть i M(ni ), M(m), 1 i m, xi X ni. Полагаем (1... m )(x1... xm, z) = 1 (x1, y1, )... m (xm, ym )(y1... ym, z).

y1,...,ym X Непосредственная проверка показывает, что таким образом определя ется полилинейная операция композиции, которая вместе с действием групп подстановок превращает M в правую K -линейную -операду.

В случае, когда R(n) = K для всех n, получаем классический объект — многомерные матрицы [56]. Введенная нами композиция превраща ется по сути в умножение многомерных матриц, определенное в [11].

Фактически мы приходим к координатной записи композиции в следу ющих двух хорошо известных операдах. Пусть V есть некоторый K модуль (напомним, что кольцо или полукольцо K коммутативно). Пра вая операда R ([54]) состоит из компонент Hom(V, V n ) и композиции 1 2... m = (1 2... m ).

Левая операда R состоит из компонент Hom(V n, V ), а композиция определяется следующим образом: 1 2... m = (1 2 · · · m ).

Как уже упоминалось выше, этот пример (под названием “клона полилинейных операций”) впервые появился в работе [2].

Положим M (n, R) = M ({1,..., n}, R). Ясно, что M (1, R) R. Сле = дующая теорема является операдным (многомерным) аналогом известно го в теории колец факта (см. [20, глава III, § 7, предложение 6]).

Теорема 6.2.1. Операда O изоморфна матричной операде M (n, R) для некоторой операды R тогда и только тогда, если в O(1) существует семейство матричных единиц { ei,j | i, j = 1,..., n }. При этом операду R можно выбрать как подопераду в операде O.

Доказательство. Пусть матричные единицы ei,j O(1), i, j n, существуют. Будем действовать по аналогии с [20]. Опреде лим операду R так: R = {R(m) | m = 0, 1, 2... }, где R(m) = { O(m) | для всех i, j ei,j... ei,j = ei,j }.

Легко проверяется, что R — подоперада операды O. Для всех O(m) определяем элементы j1,...,jm,i = ej,j1... ej,jm ei,j. Легко j убедиться, что эти элементы принадлежат R(m). Из свойств матрич ных единиц непосредственно следует, что = ej1 i... ejm i j1...jm,i.

j1,...,jm,i Обратно, по любому набору элементов µj1,...,jm,i R(m) по аналогичной формуле строится элемент µ O(m), причем это соответствие взаимно однозначно. Утверждается, что R — искомая операда, т.е. O M (n, R).

= Построим K -линейное отображение = (), O M (n, R), определяя его так: : X n X R(m), (j1,..., jm, i) = j1,...,jm,i.

Здесь X = {1,..., n}. Взаимная однозначность этого отображения сле дует из однозначности представления через j1,...,jm,i. Ясно, что =. (, i) = ()j1...jm,i (, i) = (j1...jm,i (, i)) = (, i) для всех (, i) X m X. Пусть i O(ni ), O(m). Проверка показыва ет, что (1... m ) = 1... m. Итак, имеет место изоморфизм O = M (n, R).

В случае, когда R(n) = K для всех n, операдная композиция явля ется умножением элементов K, а действие n на R(n) тривиально, будем обозначать такую операду также через K, и, соответственно, операду M (X, R) через M (X, K). Базисные элементы в K -модуле M (X, K)(m) (многомерные аналоги матричных единиц) определим так: ex,y (x, y ) = при x = x X m, y = y X, в противном случае это нуль. Легко проверить, что ex1,y1... exm,ym ey1...ym,z = ex1...xm,z и в остальных случаях такая композиция равна нулю, как и в случае обычных матричных еди ниц. Доказательства следующих утверждений несложны (напомним, что тензорное произведение линейных операд было определено в § 5.2).

6.2.1. Имеет место изоморфизм операд M (X, R) R Лемма = M (X, K).

Напомним, что если G — любая полугруппа с единицей, то тем же символом G мы обозначаем операду (нелинейную), в которой G(n) = Gn. Кроме того, через KG мы обозначаем линеаризацию этой операды:

KG(n) = K[G(n)] = K[Gn ]. Легкая проверка показывает справедливость следующего утверждения:

Лемма 6.2.2. Существует гомоморфизм операд K[n ] M (n, K), который на базисных элементах определяется так: если = (1... m ), n то образ этого элемента есть = e1 (j),...,m (j),j.

j= Напомним, что для любых двух K -линейных операд R и O можно определить произведение операд RO, (RO)(n) = R(n)O(n), где все операции (композиция и действие групп подстановок) определены поком понентно. Напомним, что конгруэнцией на операде R называется такая подоперада E R R, что каждая компонента E(n) есть отношение эквивалентности.

Будем использовать обозначение: 1 E 2 (1, 2 ) E(n).

Если K — коммутативное кольцо, и R есть K -линейная опера да, то конгруэнции на R взаимно однозначно соответствуют идеалам, как и в случае колец. Но поскольку мы не предполагаем, что K обяза тельно кольцо, а предполагаем, что в общем случае это полукольцо, а компоненты операд — полумодули над этим полукольцом, то возникает необходимость рассматриавать конгруэнции произвольного вида.

Теорема 6.2.2. Имеет место изоморфизм решеток конгруэнций опе рад R и M = M (n, R). Если рассматриваются операды над кольцом, то имеет место изоморфизм решеток идеалов операд.

Доказательство. Пусть дана некоторая конгруэнция U RR в операде R. По ней строится конгруэнция M (n, U) M (n, R)M (n, R).

Положим [n] = {1,..., n}, и пусть (1, 2 ) M (n, U)(k) для всех (i1,..., ik, i) [n]k [n] 1 (i1,..., ik, i) U 2 (i1,..., ik, i) (или (1 (i1,..., ik, i), 2 (i1... ik, i)) U(k)).

Нетрудно проверить, что таким образом действительно определяется конгруэнция.

Покажем, что соответствие U M (n, U) инъективно. Пусть M (n, U1 ) = M (n, U2 ). Возьмем любые x, x R(m),такие, что x U x, тогда существуют, M(m), такие, что (1... 1, 1) = x, (1... 1, 1) = x, (i1... im, i) = 0, (i1... im, i) = 0 для любого набора (i1,..., im, i) = (1,..., 1, 1). Отсюда следует M (n,U1 ), а зна чит, M (n,U2 ), откуда, ввиду выбора,, получим x U2 x. По симметрии, U1 = U2.

Положим = (i1,..., ik ) [n]k. Из 1 M (n,U1 U2 ) 2 следует, что для всех индексов (, i) имеет место 1 (, i) U1 U2 2 (, i), а это вле чет 1 (, i) U1 2 (, i) и 1 (, i) U2 2 (, i), откуда заключаем, что M (n, U1 U2 ) M (n, U1 ) M (n, U2 ). Обратное очевидно. Итак, соот ветствие U M (n, U) сохраняет пересечения. Оно сохраняет также и включения, т.е. U1 U2 влечет M (n, U1 ) M (n, U2 ), что проверяется очевидным образом. Следовательно, соответствие U M (n, U) сохра няет и точные верхние грани, так как U1 U2 = U.

U1,U2 U Осталось показать, что любая конгруэнция E на M (n, R) имеет вид M (n, U) для некоторой (однозначно определенной) конгруэнции U на R.

Пусть дана конгруэнция E на M (n, R), тогда конгруэнция U на R, для которой E = M (n, U), определяется так. Пусть x, y R(k). Тогда x U y существуют, µ R(k), такие что (1... 1, 1) = x, µ(1... 1, 1) = y, E µ.

Проверим, что это действительно конгруэнция. Большая часть проверок не вызывает затруднений. Пусть x1 U x,..., xm U x, x U x.

1 m Тогда существуют 1 E 1,..., m E m, E, такие, что i (1,..., 1, 1) = xi, i (1,..., 1, 1) = x, (1,..., 1, 1) = x (1,... 1, 1) = i x. Заменим элементы i, i,,, 1 i m, на соответствующие элементы вида µ = e1,1... e1,1 e1,1, (добавляя соответственные штрихи и индексы). Тогда µ(1,..., 1, 1) = (1,..., 1, 1), и µ(i1,..., im, i) = 0 при (i1,..., im, i) = (1,..., 1, 1). При этом сохранятся эквивалентности µ1 E µ,..., µm E µ, µ E µ, Отсюда µ1... µm µ (1... 1, 1) = x1... xm x, 1 m µ... µ µ (1... 1, 1) = x... x x, т.е. x1... xm x U x... x x.

1 m 1 m 1 m Имеют место тождества:

ei1,1... eim,1 e1,i (i1,..., im, i) = (1,... 1, 1), ei1,1... eim,1 e1,i (i1,..., im, i ) на остальных наборах = (i1,..., im, i ), и e1,i1... e1 im ei,1 (1,..., 1, 1) = (i1,..., im, i).

Используя их, легко убедиться, что набор (1,..., 1, 1) [n]m [n] в опре делении конгруэнции U можно заменить на любую фиксированную ком бинацию (i1,..., im, i) [n]m [n].

Теперь покажем, что E = M (n, U), где U построена по E. Пусть 1 E 2. Утверждается,что 1 M (n,U) 2, т.е., для всех (, j) [n]m [n] верно 1 (, j) U 2 (, j). Это эквивалентно тому, что для любого фик сированного (, j), как показано выше, существуют 1, 2 такие что 1 (, j) = 1 (, j), 2 (, j) = 2 (, j) и 1 E 2. Но по условию в качестве 1 и 2 можно взять сами 1 и 2, причем сразу для всех (, j).

Обратно, пусть 1 M (n,U) 2. Рассмотрим представление l при l = 1, 2 в виде l = l(,k), где l(,k) = ek1 k1... ekm km l ek k k1,...,km,k при = (k1,..., km ). Проверка показывает, что l(,k) (, k) = l (, k), а в остальных случаях l(,k) (, j) = 0. Так как достаточно устано вить, что 1(,k) E 2(,k) для всех (, k), то можно считать, что 1 (, j) = 2 (, j) = 0 для всех (, j) = (, k). Но по определению U существуют 1, 2 такие что 1 (, k) = 1 (, k), 2 (, k) = 2 (, k) и 1 E 2. Замена l на ek1,k1... ekm,km l ek,k не повлияет на эквивалент ность по модулю E, но после этого окажется, что l = l, l = 1, 2. Значит, M (n, U) E.

Пусть R — линейная операда над K, и A Alg(R). Напомним, что модулем над алгеброй A ([119], [136], [154]) называется правый K (полу)модуль M, вместе с семейством K -линейных отображений компо зиции, заданных для всех n = 1, 2,... :

M A(n1) R(n) M, x a1... an1 xa1... an1.

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

1) В случае n = 1 отображение M R(1) M задает на M структуру правого унитарного R(1)-модуля. В частности, x = x, где — единица опреады R.

2) (Ассоциативность) Пусть x M, a1 An1 1, ai Ani при 2 i m, i R(ni ) при 1 i m, R(m). Тогда (xa1 1 )(a2 2 )... (am m ) = x(a1 a2... am )(1 2... m ).

3) Если n,(1) = 1, то x(a2... an )() = x(a(2)... a(n) ).

Мы приводим здесь определение, соответствующее случаю правых операд. В § 5.5 рассматривались левые операды.

Гомоморфизм модулей над алгеброй A Alg(R) — это K -линейное отображение h : M1 M2, такое, что h(xa) = h(x)a. Обозначим че рез ModR (A) категорию модулей над A и их гомоморфизмов. Опреде лим категорию Mod(R), объекты которой — пары (M, A), где A есть R-алгебра, а M — A-модуль. Морфизм этой категории из (M1, A1 ) в (M2, A2 ) состоит из пары (h, f ), где f : A1 A2 есть гомоморфизм R алгебр, а h : M1 M2 есть гомоморфизм K -модулей, такой, что для любого натурального n, и всевозможных x M1,a1,..., an1 A1, R(n) имеет место равенство h(xa1... an1 ) = h(x)f (a1 )... f (an1 ). Ес тественным образом определен функтор S = SR : Mod(R) Alg(R), отображающий объект (M, A) в A, а морфизм (h, f ) в f. Ясно, что ка тегория ModR (A) изоморфна подкатегории Mod(R), состоящей из всех объектов вида (M, A) при данном фиксированном A и всех морфизмов вида (h, 1A ).

Теорема 6.2.3. Пусть M = M (n, R). Существуют функторы F :

Alg(R) Alg(M), G : Alg(M) Alg(R), F : Mod(R) Mod(M), G : Mod(M) Mod(R), такие, что следующая диаграмма коммута тивна с точностью до естественных эквивалентностей:

F G Alg(R) Alg(M) Alg(R) SR SM SR F G Mod(R) Mod(M) Mod(R) При этом F G IdAlg(M), GF IdAlg(R), F G IdMod(M) и G F = = = = IdMod(R). В частности, для любой R-алгебры A имеет место эквива лентность категорий ModR (A) и ModM (F (A)).

Доказательство. Пусть A является R-алгеброй, тогда поло жим F (A) = Map([n], A) = {| : [n] A}.

(Напомним, что Map(X, Y ) есть множество всех отображений из X в Y.) Покажем, что F (A) является M-алгеброй. При этом, если M(m), : [n]m [n] R(m), то 1... m Map([n], A) определяется так :

(1... m )(j) = 1 (k1 )... m (km ) (k1... km, j).



Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.