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

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

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

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

B.

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

Лема 1. Нехай Gr1(V1,E1), Gr2(V2,E2) x2500 графи, k (N, f x2500 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, n.

B (Gr2), то існує k ((, таке що |B (y, m)|(g (km) для всіх y (V2, m ((.

— відображення B (Gr1) на B (Gr2). Виберемо k ((так, що B (f (x), 1) (f (B (x, k)) для всіх x (V1. За лемою 1 B (f (x), m)(f (B (x, km)) для всіх x (V1. Отже, |B (f (x), m)|(g (k, m) для всіх x (V1, m ((. Оскільки f відображає V1 на V2, то |B (y, m)|(g (km) для всіх y (V2, m ((.

B (Gr) тоді і тільки тоді, коли існують розбиття V=(i ((Vi і натуральне число m, такі що |Vi|(m і B (x, 1)(Vj=(для всіх x (Vi, i ((і всіх j>i+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, a.

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

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

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

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

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

(() B (f (y); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES ()(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 ((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)..

Доведення. Зручно вважати, що I x2500 граф з множиною вершин (і множиною ребер 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 x2500 підгрупа, то 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 x2500 підгрупа, то 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 x2500 зліченна локально скінченна група..

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

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

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

B (G)..

Припустимо, що G x2500 скінченне розширення нескінченної циклічної підгрупи 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 x2500 скінченне розширення нескінченної циклічної групи..

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

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

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

B (G2)..

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

Теорема 6. Нехай G1, G2 x2500 зліченні локально скінченні групи. Кульові структури B (G1) i B (G2) ізоморфні тоді і тільки тоді коли справедливі наступні обидва твердження :.

(i) для кожної скінченної підгрупи F (G1 існує скінченна підгрупа H (G2, така що |F| x2500 дільник |H|;.

(ii) для кожної скінченної підгрупи H (G2 існує скінченна підгрупа F (G1, така що |H| x2500 дільник |F|;.

Доведення. Виберемо послідовність F0 (F1(…(Fi (… скінченних підгруп групи G1 таку, що G1 = (n ((Fi, F0 x2500 одинична підгрупа. Покладемо ki=|Fi+1: Fi|, n ((. Виберемо послідовність H0 (H1(…(Hi (… скінченних підгруп групи G2 таку, що G2 = (i ((Hi, H0 x2500 одинична підгрупа. Покладемо 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 у зваженому графі x2500 це сума довжин 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. Нехай (x2500 довільний нескінченний кардинал. Яка максимальна кількість груп потужності (з попарно неізоморфними кульовими структурами?.