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

 

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

BB(I),   B(I)B,  B(I)B.

Нехай Gr1(V1,E1), Gr2(V2,E2) ─ графи, kÎN. Відображення f множини V1 на множину V2 називається k-домінантним, якщо B(f(x),1)Í f(B(x,k)) для кожного xÎV1. Лема 10.1 стверджує, що відображення f: V1 ®V2 є -відображенням кульової структури B(Gr1) на кульову структуру B(Gr2) тоді і тільки тоді, коли f домінантне відображення для деякого kÎN.

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

Доведення. Зафіксуємо довільні xÎV1, m Îw. Для елемента yÎB(f(x),m) виберемо елементи y1, y2, …, yn, n<m з кулі B(f(x),m), такі що y1=f(x), yn=y і (yi, yi+1)ÎE2 для всіх i£ n-1. За припущенням існують елементи x1,x2,…,xnÎV1, такі що x=x1, f(x1)=y1, f(x2)=y2,…, f(xn)=yn і  d(xi, xi+1)£ k для всіх  i£ n-1 . Оскільки y=yn, n£ m,  то yÎf(B(x,km)).

Лема 10.2. Нехай Gr1(V1,E1), Gr2(V2,E2) графи. Припустимо що існує відображення g: w®w,  таке що |B(x,m)|£ g(m)  для всіх xÎV1, m Îw. Якщо B(Gr1) B(Gr2), то існує kÎw,  таке що |B(y,m)|£ g(km) для всіх yÎV2, m Îw.

Доведення. Нехай f ─ -відображення B(Gr1) на B(Gr2). Виберемо kÎw так, що B(f(x),1) Í f(B(x,k)) для всіх xÎV1. За лемою 10.1  B(f(x),m)Í f(B(x,km)) для всіх xÎV1. Отже, |B(f(x),m)|£ g(k,m) для всіх xÎV1, m Îw.  Оскільки f відображає V1  на V2 , то |B(y,m)|£ g(km)  для всіх yÎV2, m Îw.

Лема 10.3. Для довільного нескінченного графа Gr(V,E), B(I) B(Gr) тоді і тільки тоді, коли існують розбиття V=ÈiÎw Vi і натуральне число m, такі що |Vi|£ m і B(x,1)ÇVj=Æ для всіх xÎVi, i Îw  і всіх j>i+1.

Доведення. Припустимо, що B(I)B(Gr) і зафіксуємо -відображення 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Îw Vi. Зафіксуємо iÎw  і візьмемо довільний елемент 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Îw Vi і натуральне число m, що задовольняють припущенню леми. Визначимо бієкцію f: N® V так, що з умов a,bÎN, a<b і f(a)ÎVi, f(b)ÎVj   випливає i<j. Зафіксуємо iÎw  і візьмемо довільний елемент xÎVi. Виберемо aÎN з f(a)=x. Тоді

B(f(a),1)=B(x,1) Í Vi-1ÈViÈVi+1 .

Отже, B(f(a),1)Í B(a,2m). Звідси випливає, що f 2m- домінантне відображення. За лемою 10.1, f є -відображення B(I) на B(Gr).

Нехай B(X,P,B) довільна кульова структура, aÎP. Ін'єктивну послідовність <xn>nÎw елементів множини X назвемо a-променем, якщо xn+1 Î B(xn,a) для всіх nÎw.

Лема 10.4. Нехай B(X,P,B) кульова структура, aÎP. Якщо B(I) B, то кожна диз'юнктна сім'я a-променів на множині X скінченна.

Доведення. Нехай f: N® X -відображення. Виберемо mÎw так, що

(*) B(f(y),a)Í f(B(y,m))

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

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

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

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

Лема 10.5. Нехай  <ki>iÎw , <mi>iÎw послідовності натуральних чисел . Якщо ki³ mi для всіх iÎw, то

B(<ki>iÎw) B(<mi>iÎw),   B(<mi>iÎw) B(<ki>iÎw).

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

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

Тоді B(f(x),m)=f(B(x,m)) для всіх xÎÄiÎw [ki], mÎw . Отже,  f -відображення.

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

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

Тоді g(B(y,m))Í  B(g(y),m)  для всіх yÎÄ [mi], mÎw. Отже, g  є -відображенням.

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

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

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

Бієкцію f: ÄiÎw [mi]®ÄiÎw [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Îw [mi]  і кожного натурального числа m, то f ізоморфізм.

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

B(<ki>iÎw) B(<mi>iÎw),  B(<mi>iÎw) B(<ki>iÎw).

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

B(<ki>iÎw) B(<mi>iÎw),  B(<mi>iÎw) B(<ki>iÎw).

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

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

f: ÄiÎw [ki]®ÄiÎw [mi].

Оскільки f -відображення, то існує lÎw, таке що f(B(x,k))Í B(f(x),l) для кожного xÎ ÄiÎw [ki]. Зафіксуємо довільний елемент aÎÄiÎw [mi] і виберемо xÎ ÄiÎw [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Îw [mi] має потужність Ml , а кожна куля радіуса k в ÄiÎw [ki]має потужність Kk. Отже, Kk|Mb . Для того, щоб знайти число m досить повторити ці міркування для ізоморфізму f -1.

Припустимо, що для кожного kÎw  існують l,mÎw , такі що 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, …

За лемою 10.6 кульові структури  B(<ki>iÎw) і B(<si>iÎw)  ізоморфні.

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

Доведення. Для кожного iÎw розкладемо 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Îw зафіксуємо довільну бієкцію fi: Xi®[ki], таку що fi(e)=1. Визначимо бієкцію f: G®ÄiÎw [ki] за правилом

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

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

Лема 10.10. Нехай G=Äw Z2 пряма сума w копій групи Z2={0,1}. Тоді B(I) B(G).

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

k=a020+a121+…+an2n.

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

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

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

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]).

Звідси випливає, що f   - відображення B(I)  на B(G) .

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

B(Gr) B(I),  B(I) B(Gr).

Доведення. За теоремою 4.4 граф Gr(V,E) розкладається на квазіпромені. Кожен квазіпромінь допускає 3-домінантне відображення на I. Отже, B(Gr) B(I).

Доведемо твердження B(I) B(Gr). Припустимо спочатку, що граф Gr локально скінченний. За лемою Кьоніга існує промінь <xn>nÎw в графі Gr. Покладемо f(n+1)=xn, nÎw і помітимо, що f(B(x,m))Í B(f(x),m)  для всіх x,mÎw. Отже, f -відображення. Припустимо, що граф Gr не є локально скінченним і зафіксуємо вершину vÎV з нескінченною кулею B(v,1). Виберемо довільну зліченну підмножину, {yn: nÎw} множини B(v,1)\{v}. Покладемо f(n)=yn , nÎw . Оскільки  f(B(x,m))Í B(f(x),2)  для всіх  xÎw, nÎw , f -відображення .

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

(i) B(G) B(I);

(ii) B(I) B(G);

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

Доведення.  (i) Þ (iii). Припустимо, що B(G) B(I) для деякої локально скінченної групи 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 не може бути локально скінченною.

(ii) Þ (iii). Припустимо, що B(I)B(Gr), але група 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.

(iii) Þ (i). Виберемо довільну нескінченну скінченно породжену підгрупу G¢ Í G. Розіб'ємо G на праві суміжні класи по G¢  і зафіксуємо деяку множину X їх представників. Таким чином, G=G¢X і кожен елемент gÎG однозначно записується у вигляді g=g¢ x¢ , g¢ ÎG¢ , xÎX. Визначимо відображення f¢: G® G¢  за формулою f¢(g)=g¢ . Очевидно, що f¢ -відображення B(G) на B(G¢). Ототожнимо B(G¢) з кульовою структурою B(Cay) графа Келі Сау групи G. За теоремою 10.1, існує -відображення f¢¢ кульової структури B(Cay) на B(I). Тоді  f=f¢¢ f¢   -відображення B(G) на B(I).

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

Теорема 10.3. Нехай G   нескінченна група. Тоді B(I) B(G)  тоді і тільки тоді, коли група G містить нескінченну циклічну підгрупу скінченного індексу, або G зліченна локально скінченна група.

Доведення. Припустимо, що B(I) B(Gr)  і розглянемо два випадки.

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

Випадок 2. Групa G періодична. Припустимо, що G не є локально скінченою і виберемо скінченну підмножину FÌG, що породжує нескінченну підгрупу G¢. Розкладемо G нa праві суміжні класи по G¢. Виберемо деяку множину X представників суміжних класів. Тоді G=G¢ X і кожен елемент gÎG однозначно записується у вигляді g=g'x, g'ÎG', xÎX. Визначимо відображення f: G® G¢ за формулою f(g)=g'. Очевидно, що f -відображення B(G) на B(G'). Значить, B(I) B(G'). Ототожнимо B(G') з кульовою структурою B(Cay) її графа Келі. За лемою 10.2. група G¢ лінійного зросту. За теоремою Громова [21] G¢ має нільпотентну підгрупу скінченного індексу. Оскільки H скінченно породжена періодична нільпотентна підгрупа, то H скінченна. Отже, G' скінченна, що суперечить її вибору.

Нехай G локально скінченна група. За лемою 10.9 існує послідовність <kn>nÎw натуральних чисел, така що B(G) ізоморфна B(<kn>nÎw ). Позначимо через H пряму суму w копій групи Z2. За лемою 10.7  B(H) B(<kn>nÎw ). За лемою 10.10   B(I) B(H). Отже,  B(I) 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},…  .

За лемою10.3 B(I) B(Cay).

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

(i)

B(I) B(G),   B(G) B(I);

(ii)

G є скінченним розширенням нескінченної циклічної групи.

Доведення випливає з теореми 10.2 і 10.3.

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

Задача 10.2. Довести, що кульові структури B(I) і B(Z) неізоморфні.

За наведених задач випливає, що не існує групи G, для якої B(G) ізоморфна B(I).

Теорема 10.5. Для довільних локально скінченних груп  G1, G2 справедливі такі твердження

B(G1) B(G2),   B(G1) B(G2).

Доведення випливає з лем 10.9 і 10.7.

Теорема 10.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Îw Fi , F0 одинична підгрупа. Покладемо ki=|Fi+1 : Fi|, nÎw. Виберемо послідовність  H0 Ì H1ÌÌ Hi Ìскінченних підгруп групи G2 таку, що G2 = ÈiÎw Hi ,  H0  одинична підгрупа.  Покладемо mi=|Hi+1 : Hi|, iÎw. За лемою 10.9 B(G1), B(<ki>iÎw ) і B(G2)  B(<mi>iÎw ) попарно ізоморфні кульові структури. Відмітимо, що кожна скінченна підгрупа групи G1 міститься в деякій підгрупі Fk і кожна скінченна підгрупа групи G2 міститься в деякій підгрупі Hm. Отже, ми можемо застосувати лему 10.8.

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

Нехай B1, B2 довільні кульові структури. Чи вірно, що B2  B1 (відповідно B2  B1) якщо B1  B2 (відповідно B1  B2 )?

Візьмемо довільну зліченну локально скінченну групу G. За теоремою 10.3 B(I) B(G). За теоремою 10.2 співвідношення B(G) B(I) невірне. Отже, відповідь на перше запитання негативна.

Розглянемо повний граф Gr з множиною вершин w. Позначимо через Im граф з множиною вершин {1,2,…,m} і множиною ребер {(1,2), (2,3),…,(m-1,m)}. Приклеїмо кожен граф Im+1, mÎw ребром (m,1) до вершини m графа Gr. Одержаний граф позначимо через Gr'. Очевидно, що B(Gr) B(Gr'), але співвідношення B(Gr') B(Gr) не вірне. Отже відповідь на друге запитання теж негативна.

Задача 10.3. Вказати зліченний локально скінченний граф Gr, такий що 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Îw. Кульову структуру (V,w,Bw) позначимо через B(Grw).

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

Проблема 10.1. Нехай G1, G2 нескінченні локально скінченні групи одної потужності. Чи вірно, що B(G1) B(G2)? Чи вірно, що B(G1) B(G2)? За теоремою 10.5 це так, якщо групи G1, G2  зліченні.

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

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