Диаметры графов коммутативности сплетений групп подстановок
Нехай G — група, а Z(G) — її центр. Граф комутативності групи G — це неорiєнтований граф Γ(G) з множиною вершин G Z(G), де вершини x та y з'єднуються ребром тоді і тільки тоді, коли xy=yx. У статті вивчаються графи комутативності вінцевих добутків HςG, де G — група підстановок, що транзитивно д...
Gespeichert in:
| Datum: | 2014 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут математики НАН України
2014
|
| Schriftenreihe: | Український математичний журнал |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/166065 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Диаметры графов коммутативности сплетений групп подстановок / Ю.Ю. Лещенко // Український математичний журнал. — 2014. — Т. 66, № 5. — С. 656–665. — Бібліогр.: 16 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-166065 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1660652020-02-19T23:13:44Z Диаметры графов коммутативности сплетений групп подстановок Лещенко, Ю.Ю. Статті Нехай G — група, а Z(G) — її центр. Граф комутативності групи G — це неорiєнтований граф Γ(G) з множиною вершин G Z(G), де вершини x та y з'єднуються ребром тоді і тільки тоді, коли xy=yx. У статті вивчаються графи комутативності вінцевих добутків HςG, де G — група підстановок, що транзитивно діє на X („активна" група вінцевого добутку), а (H,Y) — абелева група підстановок на Y. Let G be a group and let Z(G) be the center of G. The commuting graph of the group G is an undirected graph Γ(G) with the vertex set G \ Z(G) such that two vertices x, y are adjacent if and only if xy = yx. We study the commuting graphs of permutational wreath products H G, where G is a transitive permutation group acting on X (the top group of the wreath product) and (H, Y) is an Abelian permutation group acting on Y. 2014 Article Диаметры графов коммутативности сплетений групп подстановок / Ю.Ю. Лещенко // Український математичний журнал. — 2014. — Т. 66, № 5. — С. 656–665. — Бібліогр.: 16 назв. — рос. 1027-3190 http://dspace.nbuv.gov.ua/handle/123456789/166065 512.54 ru Український математичний журнал Інститут математики НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Статті Статті |
| spellingShingle |
Статті Статті Лещенко, Ю.Ю. Диаметры графов коммутативности сплетений групп подстановок Український математичний журнал |
| description |
Нехай G — група, а Z(G) — її центр. Граф комутативності групи G — це неорiєнтований граф Γ(G) з множиною вершин G Z(G), де вершини x та y з'єднуються ребром тоді і тільки тоді, коли xy=yx. У статті вивчаються графи комутативності вінцевих добутків HςG, де G — група підстановок, що транзитивно діє на X („активна" група вінцевого добутку), а (H,Y) — абелева група підстановок на Y. |
| format |
Article |
| author |
Лещенко, Ю.Ю. |
| author_facet |
Лещенко, Ю.Ю. |
| author_sort |
Лещенко, Ю.Ю. |
| title |
Диаметры графов коммутативности сплетений групп подстановок |
| title_short |
Диаметры графов коммутативности сплетений групп подстановок |
| title_full |
Диаметры графов коммутативности сплетений групп подстановок |
| title_fullStr |
Диаметры графов коммутативности сплетений групп подстановок |
| title_full_unstemmed |
Диаметры графов коммутативности сплетений групп подстановок |
| title_sort |
диаметры графов коммутативности сплетений групп подстановок |
| publisher |
Інститут математики НАН України |
| publishDate |
2014 |
| topic_facet |
Статті |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/166065 |
| citation_txt |
Диаметры графов коммутативности сплетений групп подстановок / Ю.Ю. Лещенко // Український математичний журнал. — 2014. — Т. 66, № 5. — С. 656–665. — Бібліогр.: 16 назв. — рос. |
| series |
Український математичний журнал |
| work_keys_str_mv |
AT leŝenkoûû diametrygrafovkommutativnostispletenijgrupppodstanovok |
| first_indexed |
2025-07-14T20:41:54Z |
| last_indexed |
2025-07-14T20:41:54Z |
| _version_ |
1837656404484161536 |
| fulltext |
УДК 512.54
Ю. Ю. Лещенко
(Черкас. нац. ун-т им. Б. Хмельницкого, Ин-т физики, математики и компьютерно-информ. систем)
ДИАМЕТРЫ ГРАФОВ КОММУТАТИВНОСТИ
СПЛЕТЕНИЙ ГРУПП ПОДСТАНОВОК
Let G be a group and let Z(G) be the center of G. The commuting graph of the group G is an undirected graph Γ(G)
with the set of vertices G \ Z(G) such that two vertices x and y are adjacent if and only if xy = yx. In the paper, we
study the commuting graphs of permutation wreath products H oG, where G is a transitive permutation group acting upon
X (the top group of the wreath product) and (H,Y ) is an Abelian permutation group acting on Y.
Нехай G — група, а Z(G) — її центр. Граф комутативностi групи G — це неорiєнтований граф Γ(G) з множиною
вершин G \ Z(G), де вершини x та y з’єднуються ребром тодi i тiльки тодi, коли xy = yx. У статтi вивчаються
графи комутативностi вiнцевих добуткiв H o G, де G — група пiдстановок, що транзитивно дiє на X („активна”
група вiнцевого добутку), а (H,Y ) — абелева група пiдстановок на Y.
1. Введение. Графом коммутативности неабелевой группыG называется неориентированный
граф (без петель и кратных ребер) Γ(G), вершинами которого являются нецентральные элемен-
ты группы G и две вершины соединяются ребром тогда и только тогда, когда они коммутируют
в G. В статье [1] исследованы соответствующие графы симметрических и знакопеременных
групп, а также сформулирован ряд гипотез. Наиболее известная из них, — гипотеза об огра-
ниченности сверху множества диаметров связных графов коммутативности конечных групп —
была опровергнута в 2012 г. [2]. Графы коммутативности (а также их дополнения) изучались,
например, в работах [3 – 5]. Достаточно полный обзор результатов по данной теме можно най-
ти в препринте [6], где также приводится доказательство ослабленной гипотезы о диаметрах:
диаметры компонент связности графа коммутативности произвольной конечной неабелевой
группы с тривиальным центром не превышают 10.
В [7] доказано утверждение, позволяющее судить о строении графов коммутативности
прямых произведений конечных групп по свойствам соответствующих графов сомножителей.
В связи с этим возникает естественный интерес к исследованию подобных связей касательно
других классических теоретико-групповых конструкций, например сплетений групп подста-
новок.
Цель данной статьи — изучение графов коммутативности сплетений конечных групп под-
становок, где одна из групп (активная группа сплетения) является транзитивной, а вторая —
абелевой. Такие сплетения имеют нетривиальный центр.
Введем следующие обозначения. Пусть x, y — вершины графа Γ, тогда x ∼ y означает, что
x и y соединены в Γ ребром. Символом ρ(x, y) обозначим длину кратчайшего пути от x к y;
если такого пути не существует, то ρ(x, y) =∞. Тогда d(Γ) = sup{ρ(x, y)}, где x, y пробегают
множество вершин графа Γ, называется диаметром Γ.
Для произвольной группы подстановок (G,X) циклом максимальной длины на X будем
называть любой элемент из G, действующий на X транзитивно.
Теорема 1. Пусть (G,X), (H,Y ) — группы подстановок, причем (G,X) транзитивна,
(H,Y ) абелева, а Γ — граф коммутативности сплетения H oG.
1. Если |X| — простое число, то граф Γ несвязный.
c©Ю. Ю. ЛЕЩЕНКО, 2014
656 ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 5
ДИАМЕТРЫ ГРАФОВ КОММУТАТИВНОСТИ СПЛЕТЕНИЙ ГРУПП ПОДСТАНОВОК 657
2. Если |X| не является простым числом, то граф Γ связный и d(Γ) ≤ 5. Дополнительно,
если G импримитивна, то d(Γ) ≤ 4, а если G не содержит циклов максимальной длины, то
d(Γ) ≤ 3.
Теорема 2. Пусть (G,X), (H,Y ) — группы подстановок с циклами максимальной длины,
при этом |X| не является простым числом, группа (G,X) импримитивна, а группа (H,Y )
абелева. Тогда граф Γ(H oG) связный с диаметром равным 4.
В качестве примеров в последнем пункте приведены диаметры графов коммутативности
для некоторых серий классических p-групп (силовских p-подгрупп полной линейной группы
над конечным полем, а также силовских p-подгрупп симметрических групп).
2. Сплетения групп подстановок. Пусть (G,X) и (H,Y ) — группы подстановок, дей-
ствующие на множествах X и Y соответственно, Fun(X,H) — множество функций из X в H.
Обозначим символом xg образ x под действием подстановки g. Тогда можно построить новую
группу H oG, действующую на декартовом произведении Y ×X, как описано ниже. Пусть
H oG = {[f, g] | f ∈ Fun(X,H) и g ∈ G}
и если (b, a) ∈ Y × X, u = [f, g] ∈ H o G, то (b, a)[f,g] = (bf(a), ag). Группа подстановок
(H oG, Y ×X) называется сплетением групп (H,Y ) и (G,X). Если v = [f1, g1] ∈ H oG, то
u · v = [ffg1 , gg1],
где fg1 (x) = f1(x
g) и (ffg1 )(x) = f(x) · fg1 (x) = f(x) · f1(xg) для всех x ∈ X.
Нормальная подгруппа H = {[f, 1G] |f ∈ Fun(X,H)}, где 1G — единица группы G, называ-
ется базой сплетения. Пусть G = {[eH , g] | g ∈ G}, где eH — функция, возвращающая единицу
группы H при всех x ∈ X. Тогда H oG ∼= H oG.
Операция сплетения ассоциативна в классе групп подстановок, т. е. (G3 o G2) o G1
∼= G3 o
(G2 o G1) ∼= G3 o G2 o G1. Это свойство позволяет естественным образом обобщить понятие
сплетения на произвольное конечное число сомножителей.
Предположим, что (G,X) < SX и (H,Y ) < SY , где SX и SY — симметрические груп-
пы множеств X и Y соответственно. Зафиксируем g ∈ G и x0 ∈ X. Тогда Cycg(x0) =
= (x0, x1, . . . , xt−1), где xgi = xi+1 для i ∈ {0, 1, . . . , t − 2} и xgt−1 = x0, называется циклом
подстановки g с представителем x0.
Рассмотрим сплетение H o G, некоторый фиксированный элемент g ∈ G и два вида функ-
циональных уравнений:
f−1 · fg = eH , (1а)
f−1 · fg = r, (1б)
где f — неизвестная функция, r — некоторая фиксированная функция из Fun(X,H), а eH(x) =
= 1H при всех x ∈ X. Символ f−1 обозначает такую функцию, что f−1(x) = (f(x))−1 для
всех x ∈ X.
Уравнения вида (1а), (1б) встречаются в работе Л. Калужнина, посвященной изучению си-
ловских p-подгрупп симметрических групп (см. [8], леммы 5 и 6 — случай кратного сплетения
циклических групп простого порядка). Похожие уравнения также часто возникают при изуче-
нии других обобщений конструкции сплетения (см., например, [9], лемма 14 — случай кратного
сплетения копий аддитивной группы целых чисел). Следующие две леммы справедливы для
произвольных групп подстановок.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 5
658 Ю. Ю. ЛЕЩЕНКО
Лемма 1. Функция f является решением уравнения (1a) тогда и только тогда, когда на
каждом цикле подстановки g функция f постоянна. В частности, g действует транзитивно
на X тогда и только тогда, когда единственным решением будет f ≡ const — постоянная
функция.
Доказательство. Пусть C — некоторый цикл подстановки g и f(x) = h для всех x ∈ C, где
h — некоторый фиксированный элемент группы H. Тогда f−1(x) ·f(xg) = h−1 ·h = 1H для всех
x ∈ C и уравнение (1аa) имеет место. С другой стороны, если существуют x, y ∈ C такие, что
xg = y и f(x) 6= f(y), то f−1(x) · f(xg) = f−1(x) · f(y) 6= 1H , т. е. f не удовлетворяет уравне-
нию (1а).
Лемма 2. Уравнение (1б) имеет решения тогда и только тогда, когда на каждом конечном
цикле Cycg(x0) = (x0, x1, . . . , xt−1) подстановки g выполняется равенство
t−1∏
i=0
r(xi) = 1H . (2)
Доказательство. Подстановка g может иметь бесконечные циклы. Пусть C = (. . . , x−1,
x0, x1, . . .) — один из них. Положим f(x0) = 1H , f(xi) = f(xi−1)r(xi−1) и f(x−i) = f(x−i+1)×
×r−1(x−i), где i > 0. Тогда при i = 0, 1, 2, . . . получаем
f−1(xi) f(xgi ) = f−1(xi) f(xi+1) = f−1(xi) f(xi)r(xi) = r(xi),
f−1(x−i) f(xg−i) = f−1(x−i) f(x−i+1) = (f(x−i+1)r
−1(x−i))
−1 f(x−i+1) = r(x−i).
Другими словами, на бесконечном цикле C функция f, построенная выше, удовлетворяет
уравнению (1б).
Пусть теперь C = Cycg(x0) = (x0, x1, . . . , xt−1) — некоторый конечный цикл подстановки
g. Если f удовлетворяет уравнению (1б), то
t−1∏
i=0
r(xi) =
t−1∏
i=0
(
f−1(xi) f(xgi )
)
=
t−1∏
i=0
(
f−1(xi) f(xi+1)
)
= 1H , где xt = x0.
Покажем, что если равенство (2) выполняется, то уравнение (1б) имеет решение. Положим
f(x0) = 1H и f(xi) = r(x0)r(x1) . . . r(xi−1), если i ∈ {1, 2, . . . , t− 1}. Рассмотрим произволь-
ный элемент xi ∈ C, i ∈ {0, 1, . . . , t− 1}. Если i < t− 1, то
f−1(xi) f(xgi ) = f−1(xi) f(xi+1) =
= (r(x0)r(x1) . . . r(xi−1))
−1 r(x0)r(x1) . . . r(xi−1)r(xi) = r(xi).
Из (2) следует, что (r(x0)r(x1) . . . r(xt−2))
−1 = r(xt−1). Поэтому
f−1(xt−1) f(xgt−1) = f−1(xt−1) f(x0) =
= (r(x0)r(x1) . . . r(xt−2))
−1 · 1H = r(xt−1),
т. е. равенство (1б) выполняется для любого символа цикла. Повторим такую же процедуру для
всех циклов. Тогда f — искомое решение.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 5
ДИАМЕТРЫ ГРАФОВ КОММУТАТИВНОСТИ СПЛЕТЕНИЙ ГРУПП ПОДСТАНОВОК 659
При фиксированном h ∈ H символом ch обозначим функцию из Fun(X,H), принимающую
значение h при всех x ∈ X. Множество всех пар вида [ch, 1G], где h пробегает H, называ-
ется диагональю базы сплетения H o G. Следующее утверждение является частным случаем
следствия 3.4 из [10].
Лемма 3. Пусть (G,X), (H,Y ) — группы подстановок, причем (G,X) является транзи-
тивной, а (H,Y ) — абелевой. Тогда
Z(H oG) = {[ch, 1G] | h ∈ H и ch(x) = h для всех x ∈ X}
— центр сплетения H oG.
3. Диаметры графов коммутативности сплетений групп подстановок. Далее будем
считать, что 2 ≤ |X|, |Y | <∞.
Лемма 4. Пусть (G,X), (H,Y ) — группы подстановок, |X| = p — простое число, (G,X)
транзитивна, а (H,Y ) абелева. Тогда граф Γ(H oG) является несвязным.
Доказательство. Поскольку G транзитивна, то |X| — делитель |G| и, следовательно, G
содержит элемент порядка p, который будет циклом максимальной длины на X.
Зафиксируем h ∈ H и положим u = [ch, g] ∈ H o G \ Z(H o G), где g — цикл длины
p и ch(x) = h для всех x ∈ X. Рассмотрим таблицу v = [f, g′] ∈ H o G и допустим, что
uv = vu. Тогда, так как g — цикл максимальной длины, он коммутирует в SX (а значит, и в
(G,X)) только со своими степенями (см. например, [11, с. 246], лемма 8.24). Другими словами,
g′ = gα, α = 1, 2, . . . , p, и должно выполняться равенство первых координат таблиц uv и vu,
т. е.
ch(x)f(xg) = f(x)ch(xg
′
) для всех x ∈ X.
Поскольку функция ch постоянна при всех x ∈ X, а группа H абелева, из последнего равенства
следует fg = f, где g действует на X транзитивно. Тогда по лемме 1 получаем f ≡ const.
Таким образом, v = [ch′ , g
α], где ch′(x) = h′ при всех x ∈ X, а h′ — некоторый фиксирован-
ный элемент группы H. С другой стороны, gα = 1G тогда и только тогда, когда α = p (в этом
случае v ∈ Z(H o G)). Если же α = 1, 2, . . . , p − 1, то gα — цикл длины p и действует на X
транзитивно. Следовательно, пары, не содержащиеся в Z(H oG), имеющие в качестве второго
элемента p-цикл и постоянную функцию в качестве первого своего элемента, коммутируют
только с парами такого же вида. При этом они образуют отдельную компоненту связности
графа Γ(H oG).
Пример 1 ([12], теорема 2). Граф коммутативности группы ZpoZp (считаем, что Zp действует
на себе регулярно) несвязный.
3.1. Оценка диаметров сверху .
Лемма 5. Пусть (G,X), (H,Y ) — группы подстановок, где |X| = m не является простым
числом, группа (G,X) транзитивна, а группа (H,Y ) абелева. Тогда граф Γ(H o G) является
связным и d(Γ(H oG)) ≤ 5.
Доказательство. Пусть u = [f, g] ∈ H oG \ Z(H oG).
Случай 1: g действует на X не транзитивно, т. е. g имеет по крайней мере два независимых
цикла. Пусть S — множество символов в одном из циклов подстановки g. Положим z = [f1, 1G],
где f1 — такая функция из Fun(X,H), что f1(x) 6= 1H при x ∈ S и f1(x) = 1H при x ∈ X \ S.
Тогда f1(xg) = f1(x) для всех x ∈ X. Более того, так как H абелева, то
uz = [ffg1 , g] = [ff1, g] = [f1f, g] = zu.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 5
660 Ю. Ю. ЛЕЩЕНКО
Согласно лемме 3 получаем z = [f1, 1G] 6∈ Z(H oG). Следовательно, u соединена с z ребром в
Γ(H oG).
Случай 2: g действует на X транзитивно, т. е. g — цикл длины |X| = m. Поскольку m не
является простым, существует простое p такое, что m = p · n, где n ≥ 2. Тогда gp имеет по
крайней мере два цикла и
up = [ffg . . . fg
p−1
, gp]
удовлетворяет условиям случая 1. Следовательно, найдется такое z ∈ H \ Z(H o G), что u ∼
∼ up ∼ z является путем длины 2 в Γ(H oG).
Наконец, так как элементы множества H перестановочны между собой, между двумя про-
извольными вершинами графа Γ(H oG) всегда существует путь, длина которого не больше 5.
Оценка, содержащаяся в предыдущей лемме, является точной.
Пример 2. Пусть S9 — симметрическая группа, а группа Z2 действует на себе регулярно.
Тогда d(Γ(Z2 o S9)) = 5.
Доказательство. По лемме 5 диаметр графа Γ(Z2 o S9) не превышает 5. Докажем, что
найдутся такие две таблицы, расстояние между которыми в Γ(Z2 o S9) равно 5.
Пусть g1 = (1, 2, 3, 4, 5, 6, 7, 8, 9) и g2 = (1, 4, 3, 5, 6, 7, 8, 9, 2) — два цикла из S9. Тогда
ρ(g1, g2) = 5 в Γ(S9) (это можно показать путем непосредственных вычислений, например,
используя GAP [13]). Рассмотрим таблицы u = [c0, g1] и v = [c0, g2] из Z2 o S9, где c0(x) = 0
при всех x ∈ X.
Допустим, что u′ = [f, g] 6∈ Z(Z2 o S9) и коммутирует с u. Тогда g1 ∼ g и c0(x)f(xg1) =
= f(x)c0(x
g) для всех x ∈ X. Поскольку c0 — постоянная функция, из последнего равенства
следует, что f−1(x)f(xg1) = 1H при всех x ∈ X. По лемме 1, так как g1 действует на X
транзитивно, функция f также должна быть постоянной. С другой стороны, поскольку g1 —
цикл длины |X| (и, таким образом, g1 коммутирует только со своими собственными степенями),
g = gα1 для некоторого α ∈ {0, 1, . . . , 8}. При этом если α = 0, то u′ ∈ Z(Z2 o S9). Значит, u′ =
[ch1 , g
α
1 ], где ch1(x) = h1 при всех x ∈ X, α ∈ {1, 2, . . . , 8}, h1 — некоторый фиксированный
элемент группы H.
Аналогично, если v′ ∼ v, то v′ = [ch2 , g
β
2 ], где ch2(x) = h2 при всех x ∈ X, β ∈ {1, 2, . . . , 8},
h2 — некоторый фиксированный элемент группы H.
Предположим, что существует таблица w = [f3, g3], соединяющая u′ и v′ в Γ(Z2 o S9), т. е.
u′w = wu′ и v′w = wv′. Сравнивая первые компоненты таблиц из последних двух равенств и
учитывая, что ch1 и ch2 постоянны, получаем равенства
f−13 (x)f3(x
gα1 ) = 1G и f−13 (x)f3(x
gβ2 ) = 1G, x ∈ X.
Если gα1 и/или gβ2 — циклы максимальной длины, то по лемме 1 функция f3 постоянна на X.
Осталось рассмотреть случаи, когда α ∈ {3, 6} и β ∈ {3, 6}. Получаем
g31 = (1, 4, 7)(2, 5, 8)(3, 6, 9), g61 = (1, 7, 4)(2, 8, 5)(3, 9, 6),
g32 = (1, 5, 8)(4, 6, 9)(3, 7, 2), g62 = (1, 8, 5)(4, 9, 6)(3, 2, 7).
При любом из четырех возможных случаев выбора α и β орбиты соответствующих подстановок
gα1 и gβ2 перекрываются. Таким образом, f3 постоянна при всех значениях аргументов.
С другой стороны, так как расстояние между g1 и g2 в Γ(S9) равно 5 и S9 имеет тривиальный
центр, g3 = id — тождественная подстановка.
Следовательно, w ∈ Z(Z2 o S9) и ρ(u, v) ≥ 5.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 5
ДИАМЕТРЫ ГРАФОВ КОММУТАТИВНОСТИ СПЛЕТЕНИЙ ГРУПП ПОДСТАНОВОК 661
Лемма 6. Пусть (G,X), (H,Y ) — группы подстановок, |X| = m не является простым
числом, группа (G,X) транзитивна и не содержит циклов максимальной длины, а группа
(H,Y ) абелева. Тогда граф Γ(H oG) является связным и d(Γ(H oG)) ≤ 3.
Доказательство. Пусть u = [f1, g1] и v = [f2, g2] — произвольные элементы группы H oG.
Поскольку G не содержит ни одного цикла максимальной длины, g1 имеет по крайней мере
два цикла (орбиты) на X. Пусть Cg1 — один из этих циклов.
Рассмотрим таблицу u′ = [f3, 1G], где f3 ∈ Fun(X,H), f3(x) = h 6= 1H (h — некоторый
фиксированный элемент группы H) при x ∈ Cg1 и f3(x) = 1H при x 6∈ Cg1 . Тогда путем
непосредственных вычислений можно показать, что uu′ = u′u и u′ 6∈ Z(H o G) (лемма 3).
Аналогично, найдется таблица v′ ∈ H oG \ Z(H oG) такая, что v′ = [f4, 1G] и v ∼ v′.
Наконец, поскольку u′ ∼ v′, расстояние между любыми таблицами u и v в Γ(H o G) не
превышает 3.
Пример 3. Рассмотрим группу V4 = 〈(1, 2)(3, 4), (1, 4)(2, 3)〉 (четверная группа Клейна),
которая транзитивна на {1, 2, 3, 4} и не содержит циклов длины 4. Тогда d(Γ(Z2 o V4)) = 3.
Лемма 7. Пусть (G,X), (H,Y ) — группы подстановок, |X| = m не является простым чис-
лом, группа (G,X) импримитивна, а группа (H,Y ) абелева. Тогда граф Γ(H o G) является
связным и d(Γ(H oG)) ≤ 4.
Доказательство. Пусть u = [f1, g1], v = [f2, g2] — произвольные нецентральные элементы
группы H o G. Учитывая лемму 6, достаточно рассмотреть случаи, когда один из элементов
g1, g2 (или оба одновременно) — циклы максимальной длины.
Случай 1: g1 — цикл максимальной длины, а g2 нет. Тогда up = [f ′1, g
p
1 ], где p |m, p 6= 1 и
p 6= m, является нецентральным (так как gp1 6= 1G) элементом группы H oG и при этом g1 уже
не будет циклом максимальной длины. Поскольку u ∼ up, по лемме 6 получаем ρ(u, v) ≤ 4.
Если g2 — цикл максимальной длины, а g1 нет, то ситуация будет аналогичной.
Случай 2: g1, g2 — циклы максимальной длины. Пусть S = {S1, S2, . . . , Sn} — блоки системы
импримитивности группы G. Тогда n |m и n < m. Рассмотрим блок S1. Поскольку g1 — цикл
максимальной длины, g1 действует на S транзитивно (т. е. циклом). Тогда S
gn1
1 = S1, при этом,
очевидно, gn1 6= 1G. Аналогично, S
gn2
1 = S1 и gn2 6= 1G.
Таким образом, un = [f ′1, g
n
1 ] и vn = [f ′2, g
n
2 ] — нецентральные элементы группы H o G.
Осталось доказать, что в H oG существует нецентральный элемент w такой, что un ∼ w ∼ vn.
Для этого положим w = [f, 1G], где f(x) = h 6= 1H (h — некоторый фиксированный элемент
группыH) при x ∈ S1 и f(x) = 1H при x ∈ X\S1. Непосредственные вычисления показывают,
что un ∼ w и vn ∼ w.
Следовательно, u ∼ un ∼ w ∼ vn ∼ v — путь длины 4 в Γ(H oG).
Объединяя леммы 4 – 7, получаем теорему 1.
Итак, для того чтобы диаметр графа коммутативности сплетения не превышал 4, достаточ-
но, чтобы (G,X) была импримитивной, но это условие не является необходимым. Например,
diam(Γ(Z2 o S6)) = 4.
Вопрос. Пусть (G,X), (H,Y ) — группы подстановок, причем группа (G,X) транзитивна,
а группа (H,Y ) абелева. При каких условиях диаметр графа коммутативности группы H o G
равен 5 ?
3.2. Оценки диаметров снизу. Оценка диаметра графа Γ(H o G) снизу предполагает зна-
ние дополнительной информации о строении групп (G,X) и (H,Y ). Для групп с циклами
максимальной длины имеет место следующее утверждение.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 5
662 Ю. Ю. ЛЕЩЕНКО
Лемма 8. Пусть (G,X), (H,Y ) — группы подстановок с циклами максимальной длины,
X = {x1, x2, . . . , xn}, Y = {y1, y2, . . . , ym},
u = [fn, g] (3)
— таблица из H o G такая, что g — цикл максимальной длины в (G,X), fn(xn) = h, где h —
цикл максимальной длины в (H,Y ), и fn(x) = 1H при x 6= xn. Тогда u — цикл максимальной
длины в (H oG, Y ×X).
Доказательство. Будем считать, что g = (x1, x2, . . . , xn), h = (y1, y2, . . . , ym). Покажем,
что u действует на Y ×X транзитивно, т. е. для любых yj ∈ Y и xi ∈ X, 1 ≤ j ≤ m, 1 ≤ i ≤ n,
существует такое α, что (y1, x1)
uα = (yj , xi).
Для произвольного α путем непосредственных вычислений имеем
uα = [fnf
g
n . . . f
gα−1
n , gα].
При этом если α = n, то для любого xi ∈ X
fn(xi)fn(xgi ) . . . fn(xg
n−1
i ) = fn(xi)fn(xi+1) . . . fn(xn)fn(x1) . . . fn(xi−1) = h,
т. е. un = [ch, 1G], ch(x) = h при всех x ∈ X. Более того, (un)k = [chk , 1G], где chk(x) = hk при
всех x ∈ X. При этом если i ∈ {1, 2, . . . , n}, то
(y1, x1)
ui−1
= (y
fn(x1)fn(x
g
1)...fn(x
gi−2
1 )
1 , xg
i−1
1 ) = (y
fn(x1)fn(x2)...fn(xi−1)
1 , xi) = (y1, xi).
Пусть α = (i− 1) + n(j − 1), где i, j ∈ {1, 2, . . . , n}. Тогда
(y1, x1)
uα = (y1, x1)
ui−1·(un)j−1
= (y1, xi)
(un)j−1
= (yh
j−1
1 , xi) = (yj , xi),
что и требовалось доказать.
Лемма 9. Пусть (G,X), (H,Y ) — группы подстановок с циклами максимальной длины,
группа (G,X) транзитивна, а группа (H,Y ) абелева. Тогда d(Γ(H oG)) ≥ 4.
Доказательство. Пусть |X| = n и W = H o G. Рассмотрим таблицы u = [f1, g] и v =
= [eH , g], где g = (x1, x2, . . . , xn) — цикл длины n в (G,X), u — таблица вида (3), т. е.
f1(x1) = h, где h — цикл максимальной длины в (H,Y ), и f1(x) = 1H при x 6= x1, а
eH(x) = 1H при всех x ∈ X. Докажем, что ρ(u, v) ≥ 4. Для этого достаточно показать,
что пересечение централизаторов любых элементов u1 и v1 таких, что u1 ∼ u и v1 ∼ v, лежит
в центре группы W.
Согласно лемме 8 таблица u — это цикл максимальной длины в W. Тогда u перестановочна
в W только со своими степенями, т. е. если u ∼ u1, то
u1 =
[
α−1∏
i=0
fg
i
1 , g
α
]
,
где α = γ + nδ, γ = 1, 2, . . . , n − 1 и δ = 0, 1, . . . ,m − 1. Другими словами, α — это число от
1 до nm− 1, которое не делится нацело на n, так как в противном случае (если n | α) таблица
u1 принадлежит центру сплетения (вторая компонента равна 1G, а первая — это функция,
принимающая одинаковые значения при всех x ∈ X (см. доказательство предыдущей леммы)).
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 5
ДИАМЕТРЫ ГРАФОВ КОММУТАТИВНОСТИ СПЛЕТЕНИЙ ГРУПП ПОДСТАНОВОК 663
Аналогично, поскольку g — цикл максимальной длины в (G,X) и при умножении таблиц
из W умножаются их соответствующие вторые компоненты, из условия v ∼ v1 следует, что
v1 = [f2, g
β], где β = 1, 2, . . . , n− 1. Более того, из равенства первых компонент таблиц vv1 и
v1v следует, что f2 = fg2 . Последнее, согласно лемме 1, означает, что f2 ≡ const — постоянная
функция. Итак,
v1 = [const, gβ],
где β = 1, 2, . . . , n− 1.
Предположим теперь, что u1 ∼ v1. Тогда из равенства первых компонент таблиц u1v1 и
v1u1 получаем
α−1∏
i=0
fg
i
1 =
α−1∏
i=0
fg
βgi
1 или
α−1∏
i=0
fg
i
1 =
α+β−1∏
i=β
fg
i
1 .
Последнее равносильно равенству
γ−1∏
i=0
f1(x
gi) =
β+γ−1∏
i=β
f1(x
gi), (4)
которое должно выполняться при всех x ∈ X. Возможны два случая.
1. Если β < γ, то выберем xi, удовлетворяющее условию xg
β
i = x2. Тогда в равенстве (4)
слева в произведении будет один сомножитель, равный h (а именно, f1(x1); все остальные
сомножители, которых не больше чем n − 1, равны 1H ). При этом произведение справа мож-
но представить как f1(x2)f1(x3) . . . f1(xγ+1), γ + 1 ≤ n, которое равно 1H . Таким образом,
получаем противоречие h = 1H .
2. Если β ≥ γ, то выберем xi, удовлетворяющее условию xg
γ
i = x2. Тогда xg
γ−1
i = x1 и
в равенстве (4) произведение слева равно h, а произведение справа снова не содержит f1(x1).
Действительно, xg
β
i = xj , где j ≥ 2 и j 6= i, а xg
β+γ−1
i = xg
β
1 = xβ+1, где β + 1 ≤ n.
Полученные противоречия показывают, что u1 и/или v1 должны принадлежать центру спле-
тения.
В качестве непосредственного следствия леммы 7 и леммы 9 получаем теорему 2.
4. Примеры оценок диаметров графов коммутативности для некоторых p-групп. Нам
понадобится следующее утверждение, которое может быть легко обобщено на любое конечное
число сомножителей.
Лемма 10 ([7], теорема 1.2). Пусть G = A×B. Тогда:
1) если A и B неабелевы, то d(Γ(G)) ≤ min{3,d(Γ(A)),d(Γ(B))}; при этом если граф
коммутативности каждой из групп имеет диаметр не меньше 3, то d(Γ(G)) = 3;
2) если одна из групп, например B, абелева, то d(Γ(G)) = d(Γ(A)).
4.1. Силовские p-подгруппы симметрических групп. Пусть Spm — симметрическая группа
степени pm, m ∈ N. Тогда ее силовская p-подгруппа Pp,m может быть описана в терминах
сплетений циклических групп простого порядка: Pp,m ∼= Zp oZp o . . . oZp (m множителей). Если
n = a0 + a1p + a2p
2 + . . . + atp
t, где 0 ≤ ai < p для всех i ∈ {0, 1, . . . , t}, то силовскую
p-подгруппу Sylp(Sn) группы Sn можно представить в виде прямого произведения базовых
подгрупп:
Sylp(Sn) ∼= Pa1p,1 × P
a2
p,2 × . . .× P
at
p,t.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 5
664 Ю. Ю. ЛЕЩЕНКО
Силовскую p-подгруппу группы Spm при m ≥ 3 можно представить как Pp,m = Zp o Pp,m−1,
где группа Pp,m−1 импримитивна с циклом максимальной длины (см., например, [14], теоре-
ма 2.4.2, и [15], лемма 6). Следовательно, по теореме 2 получаем d(Γ(Pp,m)) = 4. Отсюда
непосредственно следует один из результатов [12].
Пример 4 ([12], теорема 4). Пусть P — силовская p-подгруппа симметрической группы Sn.
Тогда:
1) если n < p2, то группа P абелева;
2) если p2 ≤ n < 2p2, то граф Γ(P ) несвязный;
3) если n = a0 +a1p+pk, где 0 ≤ a0, a1 < p, а k ≥ 3, то граф Γ(P ) связный с диаметром 4;
4) в остальных случаях граф Γ(P ) связный с диаметром 3.
4.2. Силовские p-подгруппы полной линейной группы над конечным полем из q элемен-
тов, p > 2. Пусть p — нечетное простое число и GLn(q) — полная линейная группа степени
n над конечным полем Fq из q элементов. Если p | q, то силовская p-подгруппа группы GLn(q)
изоморфна унитреугольной (специальной треугольной) группе матриц. Другими словами,
Sylp(GLn(q)) ∼= UTn(q) при p | q.
Граф коммутативности Γ(UT3(q)) несвязный и имеет q + 1 компоненту связности, каждая из
которых — полный подграф на q2 − q вершинах (см. [12], пример 2.2). Если же n ≥ 4, то граф
Γ(UTn(q)) связный и имеет диаметр равный 3 (см. [7], утверждение 4.1).
Если (p, q) = 1, p > 2, то силовская p-подгруппа группы GLn(q) конструируется сле-
дующим образом (подробнее см. в [16]). Пусть r определяется из уравнения qe − 1 = prm,
где (p,m) = 1 и qe — наименьшая степень числа q такая, что qe ≡ 1( mod p). Тогда силов-
ская p-подгруппа группы GLe(q) изоморфна Zpr (циклической группе порядка pr). Обозначим
Qp,0 = Zpr и Qp,i = Zpr o Pp,i при i > 0 (здесь Pp,i обозначает силовскую p-подгруппу симмет-
рической группы Spi — i-кратное сплетение циклических групп порядка p). Предположим, что
n = b+ea, где 0 ≤ b < e, и a = a0+a1p+a2p
2+ . . .+atp
t, 0 ≤ ai < p для всех i ∈ {0, 1, . . . , t}.
Тогда
Sylp(GLn(q)) ∼= Qa0p,0 ×Q
a1
p,1 ×Q
a2
p,2 × . . .×Q
at
p,t
— силовская p-подгруппа группы GLn(q).
В случае (p, q) = 1 ключевую роль играют группы Qp,i. Если i > 1, то по теореме 2 граф
Γ(Qp,i) связный и имеет диаметр 4. При этом граф коммутативности группы Qp,1 = Zpr o Zp
является несвязным (лемма 4).
Пример 5. Пусть (p, q) = 1, параметры r, b, a определены так, как описано выше, и P =
= Sylp(GLn(q)). Тогда:
1) если a < p, то группа P абелева;
2) если a = a0 + p, где 0 ≤ a0 < p, то граф Γ(P ) несвязный;
3) если a = a0 + pk, где 0 ≤ a0 < p, k ≥ 2, то граф Γ(P ) связный с диаметром 4;
4) в остальных случаях граф Γ(P ) связный с диаметром 3.
Доказательство. 1. Если a < p, то P ∼= Qa0p,0 — абелева группа.
2. Если a = a0 + p, где 0 ≤ a0 < p, то P ∼= Qa0p,0 × Qp,1. Тогда по лемме 10 получаем
d(Γ(P )) = d(Γ(Qa0p,0 ×Qp,1)) = d(Γ(Qp,1)) =∞ — граф не связный.
3. Если a = a0 +pk, где 0 ≤ a0 < p, k ≥ 2, то P ∼= Qa0p,0×Qp,k и, аналогично предыдущему
пункту, d(Γ(P )) = d(Γ(Qp,k)) = 4.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 5
ДИАМЕТРЫ ГРАФОВ КОММУТАТИВНОСТИ СПЛЕТЕНИЙ ГРУПП ПОДСТАНОВОК 665
4. В остальных случаях в разложении P на прямое произведение хотя бы два сомножи-
теля будут неабелевыми с диаметром соответствующего графа коммутативности не меньше 4.
Применяя лемму 10, получаем нужный результат.
Аналогичную классификацию касательно диаметров графов коммутативности можно по-
лучить и в случае, когда p = 2.
1. Iranmanesh A., Jafarzadeh A. On the commuting graph associated with the symmetric and alternating groups // J.
Algebra and Appl. – 2008. – 7, № 1. – P. 129 – 146.
2. Giudici M., Parker C. There is no upper bound for the diameter of the commuting graph of a finite group [электронный
ресурс] / http://arxiv.org/abs/1210.0348v1.
3. Akbari S., Mohammadian A., Radjavi H., Raja P. On the diameters of commuting graphs // Linear Algebra and Appl. –
2006. – 418, № 1. – P. 161 – 176.
4. Могхаддамфар А. Р. О графах некоммутативности // Сиб. мат. журн. – 2006. – 47, № 5. – С. 1112 – 1116.
5. Abdollahi A., Akbari S., Dorbidi H., Shahverdi H. Commutativity pattern of finite non-abelian p-groups determine
their orders // Communs Algebra. – 2013. – 41, № 2. – P. 451 – 461.
6. Morgan G. L., Parker C. W. The diameter of the commuting graph of a finite group with trivial centre [электронный
ресурс] / Режим доступа: http://arxiv.org/abs/1301.2341v1.
7. Guidici M., Pope A. On bounding the diameter of the commuting graph of a group [электронный ресурс] /
http://arxiv.org/abs/1206.3731.
8. Kaloujnine L. La structure des p-groupes de Sylow des groupes symetriques finis // Ann. sci. Ecole norm. supér. –
1948. – 65. – P. 239 – 276.
9. Олийнык А. С., Сущанский В. И. Группы ZC-автоматных преобразований // Сиб. мат. журн. – 2010. – 51, № 5. –
С. 1102 – 1119.
10. Neumann P. M. On the structure of standard wreath products of groups // Math. Z. – 1964. – 84. – S. 343 – 373.
11. Isaacs I. M. Finite group theory // Grad. Stud. Math. – Providence, Rhode Island: Amer. Math. Soc., 2008. – 92. –
350 p.
12. Лещенко Ю. Ю., Зоря Л. В. Оценки диаметров графов коммутативности силовских p-подгрупп симметрических
групп // Карпат. мат. публ. – 2013. – 5, № 1. – С. 70 – 78.
13. The GAP group, GAP — groups, algorithms, and programming, Version 4.6.3; 2013 / http://www.gap-system.org.
14. Сущанський В. I., Сiкора В. С. Операцiї на групах пiдстановок. Теорiя та застосування. – Чернiвцi: Рута, 2003. –
256 с.
15. Slupik A. J., Sushchansky V. I. Minimal generating sets and Cayley graphs of Sylow p-subgroups of finite symmetric
groups // Algebra and Discrete Math. – 2009. – 4. – P. 167 – 184.
16. Weir A. J. Sylow p-subgroups of the classical groups over finite fields with characteristic prime to p // Proc. Amer.
Math. Soc. – 1955. – 6, № 4. – P. 529 – 533.
Получено 25.06.13,
после доработки — 14.11.13
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 5
|