Реферат на тему:

Розкладність графів. Морфізми кульових структур груп і графів

Позначимо через I граф з множиною вершин N={1,2…} і множиною ребер
E={(1,2),(2,3),…}. В цьому параграфі охарактеризовано кульові B
структури графів і груп, для яких справедливе одне з таких
співвідношень.

B.

-відображенням кульової структури B(Gr1) на кульову структуру B(Gr2)
тоді і тільки тоді, коли f ? домінантне відображення для деякого k(N.

Лема 1. Нехай Gr1(V1,E1), Gr2(V2,E2) ? графи, k(N, f ? k-домінантне
відображення V1 на V2 . Тоді B(f(x),m)( f(B(x,km)) для всіх x(V1, m ((.

Доведення. Зафіксуємо довільні x(V1, m ((. Для елемента y(B(f(x),m)
виберемо елементи y1, y2, …, yn, ni+1.

-відображення f: N( V. Виберемо натуральне число k так, що B(f(y),1) (
f(B(y,k)) для всіх y(N. Покладемо m=2k+1 і розіб’ємо множину натуральних
чисел N на послідовні відрізки A0, A1,… довжини m. Покладемо

V0 =f(A0), V1 =f(A1)\V0 , V2=f(A2)\(V1(V2), ….

Ясно, що |Vi|( m і V=(i(( Vi. Зафіксуємо i(( і візьмемо довільний
елемент x(Vi. Виберемо a(Ai, для якого f(a)=x. Тоді

B(x,1) =B(f(a),1)( f(B(a,k))( f(Ai-1(Ai (Ai+1).

Отже, B(x,1) (Vj = ( для всіх j>i+1.

Припустимо, що існує розбиття V=(i(( Vi і натуральне число m, що
задовольняють припущенню леми. Визначимо бієкцію f: N( V так, що з умов
a,b(N, an(( елементів множини X назвемо (-променем, якщо xn+1
( B(xn,() для всіх n((.

B, то кожна диз’юнктна сім’я (-променів на множині X скінченна.

-відображення. Виберемо m(( так, що

(() B(f(y),()( f(B(y,m))

для всіх y(N. Нехай n(( (-промінь. Виберемо y0(N з f(y0)=x0.
Користуючись співвідношенням ((), побудуємо індуктивну послідовність
n(( в N, таку що f(yn)=xn і |yn+1 — yn|( m для всіх n((. Оскільки
послідовність n(( ін’єктивна, то відрізок [a,b](N довжини m, містить
точку e, таку що f(e)({xn: n((}. Звідси випливає, що кожна диз’юнктна
сім’я (-променів в X має потужність ( m.

Для довільної послідовності i(( натуральних чисел позначимо [ki]=
{1,2,…,ki}, i((. Прямим добутком X=(i(( [ki] називається множина усіх
векторів x=(x(0), x(1),…, x(i),…), таких що x(i)([ki] і x(i)=1 для всіх
i((, за винятком деякого скінченного числа індексів. Для довільних x(X,
m(( покладемо

B(x,m)={y(X: y(i)=x(i) для всіх i( m}.

Кульову структуру (X, (, B) позначимо через B(i(().

Лема 5. Нехай i(( , i(( послідовності натуральних чисел . Якщо
ki( mi для всіх i((, то

B(i(().

Доведення. Для кожного i(( зафіксуємо деяке відображення fi [ki] на
[mi]. Відображення f: (i(( [ki]((i(( [mi] визначимо за правилом

f(x(0), x(1),…, x(i),…)=(f0 (x(0)), f1 ( x(1)),…, fi ( x(i)),…).

-відображення.

Для кожного i(( зафіксуємо ін’єктивне відображення gi: [mi] ([ki] таке
що gi(1)=1. Визначимо відображення g: (i(( [mi]((i(( [ki] за правилом

g((y(0), y(1), …, y(i) ,…)) = (g0(y(0)), g1( y(1)), …, gi( y(i)) ,…).

-відображенням.

Лема 6. Нехай i(( ? послідовність натуральних чисел, g: ((( ?
неспадне відображення. Покладемо m0=k0 k1 … kg(0), mi+1=kg(i)+1 kg(i)+2
… kg(i+1). Тоді кульові структури B(i(() і B(i(() ізоморфні .

Доведення. Зафіксуємо довільну бієкцію f0: [m0]([k0] ( [k1](…([kg(0)] і
для кожного i(( визначимо деяку бієкцію

fi: [mi]([kg(i)+1] ( [kg(i)+2](…([kg(i+1)] .

Бієкцію f: (i(( [mi]((i(( [ki] визначимо за правилом

f((x(0), x(1), …, x(i) ,…)) = (f0(x(0)), f1( x(1)), …, fi( x(i)) ,…).

Оскільки f(B(x,m))=B(f(x),g(0) + g(1)+ …g(m-1)) для кожного x( (i(( [mi]
і кожного натурального числа m, то f ? ізоморфізм.

Лема 7. Нехай i(( і i(( ? послідовності натуральних чисел, ki>1,
mi>1 для всіх i(( . Тоді

B(i(().

Доведення. За лемою 10.6 існує послідовність i(( натуральних чисел
така що кульові структури B(i(() і B(i(() ізоморфні, причому Ki
( mi для всіх i((. За лемою 10.5

B(i(().

Лема 8. Нехай i((, i(( ? послідовності натуральних чисел. Для
кожного i(( покладемо Ki=k0k1…ki, Mi=m0m1…mi. Кульові структури
B(i(() і B(i(() ізоморфні тоді і тільки тоді, коли для кожного
k(( існують l,m(( такі, що Kk|Ml i Mk|Km.

Доведення. Припустимо, що ці кульові структури ізоморфні і зафіксуємо
деякий ізоморфізм

f: (i(( [ki]((i(( [mi].

-відображення, то існує l((, таке що f(B(x,k))( B(f(x),l) для кожного
x( (i(( [ki]. Зафіксуємо довільний елемент a((i(( [mi] і виберемо x(
(i(( [ki], для якого f(x)( B(a,l). Тоді B(f(x),l)=B(a,l) i f(B(x,k)) (
B(a,l). Звідси випливає, що f -1(B(a,l)) є диз’юнктним об’єднанням куль
радіуса k. Помітимо, що кожна куля радіуса l в (i(( [mi] має потужність
Ml , а кожна куля радіуса k в (i(( [ki]має потужність Kk. Отже, Kk|Mb .
Для того, щоб знайти число m досить повторити ці міркування для
ізоморфізму f -1.

Припустимо, що для кожного k(( існують l,m(( , такі що Kk|Ml , Mk|Km.
Застосовуючи лему 10.6, можна вважати, що

K0|M0 , M0|K1 , K1|M1, M1|K2 , K2|M2, …

Покладемо

s0=K0, s1=M0/K0, s2=K1/M0, s3=M1/K1 , s4=K2/M1, …

За лемою 6 кульові структури B(i(() і B(i(() ізоморфні.

Лема 9. Нехай група G є об’єднанням зростаючого ланцюга своїх скінченних
підгруп G0(G1(…(Gi(…, G0={e}, e ? одиниця групи G. Покладемо
ki=|Gi+1:Gi|, i((. Тоді кульова структура B(G) ізоморфна B(i(().

Доведення. Для кожного i(( розкладемо Gi+1 на праві суміжні класи по
підгрупі Gi і виберемо деяку множину Xi представників суміжних класів,
e(Xi. Таким чином, Gi+1 =GiXi. Візьмемо довільний елемент g(G і виберемо
найменшу підгрупу Gm+1, для якої y(Gm+1. Для g=e виберемо підгрупу G1.
Тоді g= gm-1 xm-1, gm-1(Gm , xm(Xm-1 . Оскільки gm-1(Gm , то gm-1=gm-2
xm-1 для деяких елементів gm-2 (Gm-1, xm-1(Xm-1. Після m+1 кроків
отримаємо представлення

g=x0x1…xm-1xm, x0 (X0, x1( X1, …, xm(Xm.

Зауважимо, що таке представлення однозначне. Для кожного i(( зафіксуємо
довільну бієкцію fi: Xi([ki], таку що fi(e)=1. Визначимо бієкцію f:
G((i(( [ki] за правилом

f(g)= (f0(x0), f1( x1), …, fm( xm), 1,1,1,…).

Оскільки кожна скінченна підмножина групи G міститься в деякій
скінченній підгрупі, то f ? ізоморфізм між B(G) і B(i(().

B(G).

Доведення. Зручно вважати, що I ? граф з множиною вершин ( і множиною
ребер E={(i,i+1): i((}. Для кожного k(( розглянемо бінарний розклад

k=a020+a121+…+an2n.

Визначимо відображення f: ((G за правилом

f(k)=(a0, a1,…, an, 0,0,0,…).

Для кожного m(( позначимо

Gm={g(G: g=(z0,z1,…, zm, 0, 0, 0, …), z0,…, zm({0,1}}.

Помітимо, що

B(f(k), Gm)(f([k-2m+1, k+2m+1]).

— відображення B(I) на B(G) .

Теорема 1. Для довільного нескінченного зв’язного графа Gr(V,E)
справедливі твердження

B(Gr).

B(I).

-відображення .

Теорема 2. Для кожної нескінченної групи G такі твердження рівносильні

B(I);

B(G);

(iii) група G не являється локально скінченною.

-відображення f: G ( N і виберемо скінченну підгрупу H( G, таку що
B(f(g),1)( f(B(g,H)). Зафіксуємо довільний елемент g0(G і виберемо
максимальне натуральне число m(f(B(g0,H)). Виберемо g1(B(g0,H) з
f(g1)=m. Оскільки H ? підгрупа, то B(g1,H)( B(g0,H). Отже B(f(g1,1))(
f(B(g0,H)) і m+1(f(B(g0,H)), що суперечить вибору m. Отже, група G не
може бути локально скінченною.

-відображення f: N(G і виберемо скінченну підгрупу H ( G, таку що

f(B(n,1)) ( B(f(n),H)

для кожного n(N. Виберемо максимальне число m(f -1 (B(f(1)),H). Оскільки
f(m)(B(f(1),H) і H ? підгрупа, то B(f(m),H)=B(f(1),H). Оскільки
f(B(m,1)) ( B(f(m),H), то m+1(B(f(1),H), що суперечить вибору числа m.

-відображення B(G) на B(I).

(iii) ( (ii). Виберемо нескінченну скінченно породжену підгрупу G( ( G і
ототожнимо її з кульовою структурою B(Cay). Застосуємо теорему 10.1.

B(G) тоді і тільки тоді, коли група G містить нескінченну циклічну
підгрупу скінченного індексу, або G ? зліченна локально скінченна група.

B(Gr) і розглянемо два випадки.

Випадок 1. Група G містить елемент g нескінченного порядку. Нехай C –
підгрупа породжена елементом g, e ? одиниця групи G. Покладемо (={e,g} і
помітимо, що для кожного елемента x(G послідовність n(( є
(-променем в B(G). За лемою 4 C ? підгрупа скінченного індексу.

B(G’). Ототожнимо B(G’) з кульовою структурою B(Cay) її графа Келі. За
лемою 2. група G( лінійного зросту. За теоремою Громова [21] G( має
нільпотентну підгрупу скінченного індексу. Оскільки H ? скінченно
породжена періодична нільпотентна підгрупа, то H скінченна. Отже, G’
скінченна, що суперечить її вибору.

B(G).

Припустимо, що G ? скінченне розширення нескінченної циклічної підгрупи
C, породженої елементом g. Можна вважати, що підгрупа C інваріантна і
x-1gx({g,g-1} для всіх елементів x(G. Розкладемо G на праві суміжні
класі по підгрупі C і виберемо деяку множину представників
H={h1,h2,…,hn}, причому H=H-1. Для всіх i,j ( {1,2,..,n} виберемо
a(i,j)(Z так, що hi,hj(ga(i,j)H. Покладемо a=max{|a(i,j)+1|: i,j (
{1,2,..,n}. Розглянемо граф Келі Сау групи G, визначений системою
твірних H( {g,g-1}. Покладемо V0={gkH: |k|( a}, V1={gkH: a<|k|( 2a}, V2={gkH: 2a<|k|( 3a},… . B(Cay). Теорема 4. Для довільної групи G такі твердження еквівалентні B(I); (ii) G є скінченним розширенням нескінченної циклічної групи. Доведення випливає з теореми 2 і 3. Задача 1. Довести, що кульова структура B(G) групи G ізоморфна кульовій структурі B(Z) групи цілих чисел тоді і тільки тоді, коли G ? скінченне розширення нескінченної циклічної групи. Задача 2. Довести, що кульові структури B(I) і B(Z) неізоморфні. За наведених задач випливає, що не існує групи G, для якої B(G) ізоморфна B(I). Теорема .5. Для довільних локально скінченних груп G1, G2 справедливі такі твердження B(G2). Доведення випливає з лем 9 і 7. Теорема 6. Нехай G1, G2 ? зліченні локально скінченні групи. Кульові структури B(G1) i B(G2) ізоморфні тоді і тільки тоді коли справедливі наступні обидва твердження : (i) для кожної скінченної підгрупи F( G1 існує скінченна підгрупа H( G2 , така що |F| ? дільник |H|; (ii) для кожної скінченної підгрупи H( G2 існує скінченна підгрупа F( G1 , така що |H| ? дільник |F|; Доведення. Виберемо послідовність F0 ( F1(…( Fi (… скінченних підгруп групи G1 таку, що G1 = (n(( Fi , F0 ? одинична підгрупа. Покладемо ki=|Fi+1 : Fi|, n((. Виберемо послідовність H0 ( H1(…( Hi (… скінченних підгруп групи G2 таку, що G2 = (i(( Hi , H0 ? одинична підгрупа. Покладемо mi=|Hi+1 : Hi|, i((. За лемою 9 B(G1), B(i(( ) і B(G2)
B(i(( ) попарно ізоморфні кульові структури. Відмітимо, що кожна
скінченна підгрупа групи G1 міститься в деякій підгрупі Fk і кожна
скінченна підгрупа групи G2 міститься в деякій підгрупі Hm. Отже, ми
можемо застосувати лему 8.

Аналізуючи викладені результати природно виникає таке питання.

B2 )?

B(I) невірне. Отже, відповідь на перше запитання негативна.

B(Gr) не вірне. Отже відповідь на друге запитання теж негативна.

B(G) для кожної зліченної групи G.

Зваженим графом Grw(V,E) назвемо граф Gr(V,E) разом з функцією w: E ( N,
що приписує кожному ребру e ( E його вагу w(e)(N. Довжина шляху x1, x2,
…, xn у зваженому графі ? це сума довжин w(x1,x2), w(x2,x3),…,
w(xn-1,xn.). Покладемо d(x,x)=0, x(V і d(x,y)= (, якщо x,y належить
різним зв’язним компонентам графа Gr. Якщо ж x,y належать одній зв’язній
компоненті графа Gr, позначимо через dw(x,y) довжину найкоротшого
зваженого шляху між x і y. Покладемо Bw(x,m)={y(V: dw(x,y)( m}, m((.
Кульову структуру (V,(,Bw) позначимо через B(Grw).

Задача 4. Довести, що кульова структура B(G) довільної зліченної групи G
ізоморфна кульовій структурі B(Grw) деякого зваженого графа Grw.

B(G2)? За теоремою 5 це так, якщо групи G1, G2 зліченні.

За теоремою 6. існує рівно континуум попарно неізоморфних кульових
структур зліченних локально скінченних груп.

Проблема 2. Нехай ( ? довільний нескінченний кардинал. Яка максимальна
кількість груп потужності ( з попарно неізоморфними кульовими
структурами?

Похожие записи