close

Вход

Забыли?

вход по аккаунту

?

Ранги планарности многообразий коммутативных моноидов.

код для вставкиСкачать
МАТЕМАТИКА
Вестн. Ом. ун-та. 2012. № 4. С. 41–45.
УДК 512.572
Д.В. Соломатин
РАНГИ ПЛАНАРНОСТИ МНОГООБРАЗИЙ
КОММУТАТИВНЫХ МОНОИДОВ
Изучается предложенное Л.М. Мартыновым понятие ранга планарности многообразия полугрупп для многообразий моноидов. Доказано, что ранг планарности любого
многообразия коммутативных моноидов не превышает 3. Приведена классификация
многообразий коммутативных моноидов по рангам планарности.
Ключевые слова: ранги планарности, многообразие коммутативных моноидов, граф
Кэли полугруппы, планарный граф.
Данная статья открывает цикл работ, посвященных предложенной
Л.М. Мартыновым программе по изучению вопросов планарности графов
Кэли для многообразий полугрупп. Одним из центральных понятий в ней
является введенное им понятие ранга многообразия полугрупп. Приведем его определение применительно к многообразиям моноидов. Пусть V
– произвольное многообразие моноидов. Если существует такое натуральное число r, что все V-свободные полугруппы ранга ≤ r допускают
планарный граф Кэли, а V-свободная полугруппа ранга r + 1 уже не допускает планарный граф Кэли, то рангом планарности V называется это
число r. Если для многообразия V такого натурального числа не существует, то говорят, что многообразие V имеет бесконечный ранг планарности. Заметим, что согласно определению тривиальное многообразие одноэлементных моноидов имеет бесконечный ранг планарности.
Традиционно [1] графом Кэли полугруппы S относительно множества
образующих её элементов X называют помеченный ориентированный
мультиграф Cay ( S , X ), состоящий из множества вершин S и множества
помеченных дуг – всевозможных троек ( a, x, b) , где a, b ∈ S , , x ∈ X и
ax = b.
Упомянутое определение задает ориентированный мультиграф с помеченными ребрами. Основой помеченного ориентированного мультиграфа мы называем обыкновенный граф, полученный из данного графа
удалением меток, петель и заменой всех дуг, соединяющих две вершины
одним ребром, соединяющим эти вершины. Ориентированный же мультиграф естественно назвать планарным, если его основа является планарным графом, т. е. изоморфна некоторому обыкновенному графу (неориентированному и без петель), вершины которого являются точками
плоскости, а ребра – непрерывными плоскими линиями без самопересечений, соединяющими вершины так, что никакие два ребра не имеют
общих точек, кроме инцидентной им обоим вершины.
Таким образом, говорим, что полугруппа допускает планарный граф
Кэли, если относительно некоторого множества образующих основа её
графа Кэли является планарным графом.
В статье [2] описаны многообразия коммутативных моноидов, среди
основных результатов которой содержится следующий: каждое многообразие V коммутативных моноидов содержит циклический моноид C наибольшего порядка и V состоит из гомоморфных образов прямых степеней
C. В частности, любое многообразие моноидов порождается циклическим
моноидом. Напомним, что под циклическим моноидом понимается любой
гомоморфный образ свободного моноида с одним образующим. Очевидно,
что любой циклический моноид изоморфен либо циклической группе, либо
получен из циклической полугруппы внешним присоединением единицы.
© Д.В. Соломатин, 2012
Д.В. Соломатин
42
Пусть M – многообразие всех коммутативных моноидов. Множество всех подмногообразий многообразия M по отношению
включения образует решетку L(M). В работе
[2] конструируется решетка L, изоморфная
решетке L(M). Пусть L' – прямое произведение решеток G × I × P, где G – двухэлементное множество {1, 2} с естественным порядком на нём; I – пополненное элементом ∞
множество натуральных чисел с естественным порядком на нём; P – пополненное элементом ∞ множество натуральных чисел
упорядоченное отношением делимости (при
этом, каждое натуральное число делит ∞ ).
Каждому многообразию V ∈ L( M ) поставлен
в соответствие элемент ϕ (V) ∈ L ' следующим образом: выбирается циклический моноид C наибольшего порядка в V; если C –
бесконечен, то полагают ϕ (V)= (2, ∞, ∞ ); если
же C – конечен, то выбирают порождающий
его элемент g и полагают ϕ (V)= ( d , i, p ), где
d принимает значение 1 или 2 в зависимости от того, является ли C группой или нет,
а i и p – это индекс и период элемента g соответственно. По теореме 1 отображение ϕ
является взаимно-однозначным отображением L(M) в L'.
Пусть
L = ( x, y, z ) ∈ L ' ( y = ∞ ↔ z = ∞) ∧
{
∧( x = 1 → y = 1)}. Тогда L оказывается подрешеткой решетки L' и im(ϕ ) = L.
В работе
[2] доказано, что решетка L( M ) всех многообразий коммутативных моноидов изоморфна решетке L , так как существует
изоморфизм ϕ : L( M ) → L .
Схематично изобразим решетку L на
рис. 1.
Там же отмечается, что многообразия,
которым отображение ϕ ставит в соответствие тройки (1, 1, p ) , (2, i, p ) и (2, ∞, ∞) ,
являются многообразиями коммутативных
моноидов,
задаваемыми
тождествами
x p = 1 , x i = x i + p и x = x соответственно.
Условимся в дальнейшем для системы Σ
моноидных тождеств через var Σ обозначать многообразие коммутативных моноидов, заданное этой системой. Многообразие моноидов называется комбинаторным,
если оно не имеет неединичных подгрупп.
Рис. 1. Изображение решётки L
Ранги планарности многообразий коммутативных моноидов
Ниже будем использовать следующие
обозначения:
Am = var{xm = 1} – многообразие всех абелевых групп экспоненты m;
S1i , p = var{x i + p = x i } – комбинаторное многообразие коммутативных моноидов типа
(i, p).
Основным результатом статьи является
следующее.
Теорема. Пусть V – нетривиальное
многообразие коммутативных моноидов,
rπ(V) – его ранг планарности. Тогда rπ(V) ≤ 3.
Более того:
1) rπ(V) = 1 тогда и только тогда, когда V
= A m или V= S1i , p , где m ≠ 2 , (i ≥ 1 ∧ p > 2) ;
2) rπ(V) = 2 тогда и только тогда, когда V
= M , или V = S1i1 ,1 , или V = S1i2 ,2 , где
(i1 ≥ 2 ∧ i2 ≥ 1) ;
= A 2 или V = S11,1 .
Доказательству теоремы предпошлём
несколько доказанных автором ранее утверждений, которые мы сформулируем
здесь в виде лемм. В [3] были изучены конечные свободные коммутативные моноиды, допускающие планарный граф Кэли.
При рассмотрении графов Кэли моноидов необходимо помнить, что моноиды
рассматриваются в сигнатуре (⋅, 1) и поэтому единицу в образующие добавлять нет
необходимости, она автоматически обязана
присутствовать в любом подмоноиде.
Напомним, что конечный моноид называется свободным коммутативным, если он
является свободным коммутативным произведением циклических моноидов в классе
моноидов. Конечный свободный коммутативный моноид имеет в классе всех коммутативных моноидов копредставление вида:
a j j = 1, ai ri +mi = ai ri , i ∈ I , j ∈ J ,
m
где I ∪ J = 1, n , I ∩ J = ∅ , J ≠ ∅ . Заметим,
что соотношение вида a
mj
j
но соотношениям вида: a
=1
1+ m j
j
ральное число;
для натуральных чисел r , m , t выполнено
одно из следующих ограничений:
а) t ≤ 2 ;
б) m ≤ 2 , t > 2 ;
2.2)
S = a , b ab = ba, a m = 1, bt = 1 ,
где
m и t – натуральные числа, причем t ≤ 2 ;
3.1) S = a , b, c ab = ba, ac = ca, bc = cb,
a r + m a r , bh + t = bh , c k = 1 , где для натуральных
чисел r , m , h , t , k выполнено одно из следующих ограничений:
а) h = 1 , t = 1 , k = 1 ;
б) m ≤ 2 , t ≤ 2 , k = 1 ;
в) m ≤ 2 , h = 1 , t = 1 , k = 2 ;
S = a, b, c ab = ba, ac = ca, bc = cb,
3.2)
ральные числа, причем m ≤ 2 ;
= a j , ak a j j = ak
m
a m = 1 , где m – любое нату-
S = a, b, c ab = ba, ac = ca, bc = cb,
3.3)
a 2 = 1, b2 = 1, c 2 = 1 ;
4)
S = a, b, c, d ab = ba, ac = ca, ad = da,
bc = cb, bd = db, cd = dc, a r + m = a r , b2 = b, c 2 = c,
d = 1 , где r и m – натуральные числа, причем m ≤ 2 .
Опираясь на этот результат, получена
лемма 2.
Лемма 2. Бесконечный моноид S, являющийся коммутативно-свободным произведением циклических моноидов в классе всех
моноидов, имеет планарный граф Кэли относительно множества свободных образующих тогда и только тогда, когда S задан копредставлением одного из следующих видов:
1) S = a , b ab = ba , bt = 1 , где t – любое
натуральное число;
2.1) S = a , b, c ab = ba, ac = ca, bc = cb,
b2 = b, c k = 1
эквивалент-
для любого индекса k ∈1, n . Граф Кэли будем рассматривать относительно множества
образующих, указанных в копредставлении;
понятно, что это множество является множеством свободных образующих моноида S.
Лемма 1 ([3], теорема 1). Граф Кэли конечного свободного коммутативного моноида S относительно множества свободных
образующих планарен тогда и только тогда, когда S задан копредставлением одного
из следующих видов:
1) S = a
2.1) S = a , b ab = ba , a r + m = a r , bt = 1 , где
a r + m = a r , b2 = 1, c 2 = 1 , где r и m – нату-
3) rπ(V) = 3 тогда и только тогда, когда V
S = a1 , a2 , K, an
43
при k ≤ 2 ;
2.2) S = a , b, c ab = ba, ac = ca, bc = cb,
c =1 ;
2.3) S = a , b, c ab = ba, ac = ca, bc = cb,
b = 1, c 2 = 1 ;
2
3) S = a , b, c, d ab = ba, ac = ca, ad = da,
bc = cb, bd = db, cd = dc, b2 = b, c 2 = c, d = 1 .
Доказательство леммы 2. Рассмотрим каждую из возможных ситуаций. Для
первого случая плоская укладка графа Кэли
бесконечного моноида S получается аналогично изображенной на рис. 2, располагая
i +1 j
бесконечное число элементов вида a b ,
Д.В. Соломатин
44
получаемых умножением на элемент a , левее
элементов вида a b , где i – любое натуральное число, и 1 ≤ j ≤ t . В частности, при
i
j
t = 1 плоская укладка изображена на рис. 3.
Каждый из пунктов второго случая естественным образом обобщает возможные конечные плоские укладки из леммы 1, изображенные на рис. 4, 5. Действительно, условие 2.1 леммы 2 обобщает ограничения
3.1.а, 3.1.в леммы 1, условие 2.2 обобщает
3.1.б и условие 2.3 обобщает 3.2 соответственно. В последнем случае полугруппа представляет
собой
коммутативно-свободное
произведение бесконечной циклической полугруппы и двух циклических групп второго
порядка с последующим внешним присоединением единицы. Планарная укладка соответствующего ей графа Кэли может быть получена продлением укладки, аналогичной
изображенной на рис. 4 с точностью до обозначения d = c . При невыполнении полученных ограничений, обнаруживаются подграфы соответствующих графов Кэли гомеоморфные графу K5 или K 3,3 . Причем совпадающие с подграфами, обнаруживаемыми в
случае конечных моноидов из леммы 1.
Доказательство теоремы. В классе
коммутативных моноидов, многообразия
Am ,
S1i , p
и
M , задаются тождествами
x m = 1 , x i = x i + p и x = x соответственно.
Граф Кэли свободного моноида многообразия коммутативных моноидов, зада-
ваемого тождеством x m = 1 , допускает плоскую укладку тогда и только тогда, когда
порождается единственным элементом, т. е.
имеет указанное в лемме 1 копредставление
вида 1, либо максимум тремя образующими
при m = 2 , т. е. имеет указанное в лемме 1
копредставление вида 3.3. Аналогично, граф
Кэли свободного моноида многообразия коммутативных моноидов, задаваемого тождестi+ p
i
вом x = x , допускает плоскую укладку тогда и только тогда, когда порождается единственным элементом в классе коммутативных моноидов, т. е. имеет указанное в лемме
1 копредставление вида 2.1.а при t = 1 , либо
порождается максимум двумя элементами,
т. е. имеет указанное в лемме 1 копредставление вида 3.1.б, либо порождается максимум тремя элементами, т. е. имеет указанное
в лемме 1 копредставление вида 4 при
r = m = 1 . И наконец, граф Кэли абсолютно
свободного моноида многообразия коммутативных моноидов, задаваемого тождеством
x = x , допускает плоскую укладку тогда и
только тогда, когда он порождается не более
чем двумя элементами в классе коммутативных моноидов, т. е. имеет указанное в лемме 2 копредставление вида 2.2.
Теорема доказана.
В заключение заметим, что вопрос о
рангах планарности других многообразий
моноидов (в частности, групп) пока остаётся открытым.
ar+m-1
ar+1
ar
a
bt
ar+m-1b
ar+1b
arb
ab
b
ar+m-1b2
ar+1b2
arb2
ab2
b2
ar+m-1bt-1
ar+1bt-1
arbt-1
abt-1
bt-1
Рис. 2. Граф Кэли коммутативного моноида S = a , b a r + m = a r , bt = 1
1
a
a2
an
Рис. 3. Граф Кэли бесконечного циклического моноида
Ранги планарности многообразий коммутативных моноидов
45
ar+m-1
ar
a
ar+m-1b
arb
ab
b
ar+m-1c
ar+m-1bc
a rc
arbc
c2
ac
abc
c
bc
Рис. 4. Граф Кэли коммутативного моноида S = a , b, c ab = ba, ac = ca, bc = cb, a r + m = a r , b 2 = b, c 2 = 1
ar+m-1b
ar+m-1
ar+1
ar+1b
ar
arb
ab
a
b
b2
bc
c
abc
arbc
ar+1bc
ar+m-1bc
ac
arc
ar+1c
ar+m-1c
Рис. 5. Основа графа Кэли коммутативного моноида S = a , b, c ab = ba, ac = ca, bc = cb, a r + m = a r , b 2 = 1, c 2 = 1
Автор выражает глубокую признательность профессору Л.М. Мартынову за постановку задачи, внимание к работе и обсуждение результатов.
ЛИТЕРАТУРА
[1] Zelinka B. Graphs of Semigroups // Casopis.
Pest. Mat. 1981. Vol. 106. P. 407–408.
[2] Head T. J. The varieties of commutative monoids
// Nieuw Archief voor Wiskunde (3). 1968.
Vol. XVI. P. 203–206.
[3] Соломатин Д. В. Конечные свободные коммутативные моноиды, допускающие планарный
граф Кэли // Вестник Омского университета.
Омск : Изд-во ОмГУ. 2005. Вып. 4. С. 36–38
Документ
Категория
Без категории
Просмотров
5
Размер файла
496 Кб
Теги
моноидов, ранга, коммутативной, многообразие, планарность
1/--страниц
Пожаловаться на содержимое документа