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

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

Для кожного 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(( \x2500 послідовність натуральних чисел, g: ((( \x2500 неспадне відображення. Покладемо 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 \x2500 ізоморфізм.

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

B(i(().

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

B(i(().

Лема 8. Нехай i((, i(( \x2500 послідовності натуральних чисел. Для кожного 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 \x2500 одиниця групи 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 \x2500 ізоморфізм між B(G) і B(i(().

B(G).