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

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

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

B $$$$ B (I), B (I) $$$$ B, B (I) $$$$ B.

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

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

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

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

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

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

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

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

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

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

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

Припустимо, що існує розбиття V= Vi і натуральне число m, що задовольняють припущенню леми. Визначимо бієкцію f: Nтак, що з умов a, ba<b і f (a) f (b) випливає i<j. Зафіксуємо i і візьмемо довільний елемент x Виберемо aз f (a)=x. Тоді.

B (f (a), 1)=B (x, 1) -11 .

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

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

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

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

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

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

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

B (x, m)={yy (i)=x (i) для всіх i.

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

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

B (<ki>i) $$$$ B (<mi>i), B (<mi>i) $$$$ B (<ki>i).

Доведення. Для кожного i зафіксуємо деяке відображення fi [ki] на [mi]. Відображення f: [ki]i [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)) для всіх xi [ki], m. Отже, f — $$$$ -відображення.

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

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

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

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

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

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

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

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

B (<ki>i) $$$$ B (<mi>i), B (<mi>i) $$$$ B (<ki>i).

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

B (<ki>i) $$$$ B (<mi>i), B (<mi>i) $$$$ B (<ki>i).

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

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

f: [ki]i [mi].

Оскільки f $$$$ -відображення, то існує l, таке що f (B (x, k))f (x), l) для кожного x [ki]. Зафіксуємо довільний елемент ai [mi] і виберемо x [ki], для якого f (x)a, l). Тоді B (f (x), l)=B (a, l) i f (B (x, k)) a, l). Звідси випливає, що f -1(B (a, l)) є диз’юнктним об'єднанням куль радіуса k. Помітимо, що кожна куля радіуса l в [mi] має потужність Ml, а кожна куля радіуса k в [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 (<ki>i) і B (<si>i) ізоморфні.

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

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

g=x0x1…xm-1xm, x0 x1, …, xm.

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

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

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

Лема 10. Нехай G= Z2 — пряма сума опій групи Z2={0,1}. Тоді 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={gg=(z0,z1,…, zm, 0, 0, 0, …), z0,…, zm1}}.

Помітимо, що.

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

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

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

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

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

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

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

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

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

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

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

(ii) ii). Припустимо, що B (I) $$$$ B (Gr), але група G не є локально скінченною. Зафіксуємо $$$$ -відображення f: Nі виберемо скінченну підгрупу H таку що.

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

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

(iii)). Виберемо довільну нескінченну скінченно породжену підгрупу G Розіб'ємо G на праві суміжні класи по Gі зафіксуємо деяку множину X їх представників. Таким чином, G=Gі кожен елемент gоднозначно записується у вигляді g=ggxВизначимо відображення fза формулою f=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) i). Виберемо нескінченну скінченно породжену підгрупу Gі ототожнимо її з кульовою структурою B (Cay). Застосуємо теорему 10.1.

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

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

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

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

Нехай G — локально скінченна група. За лемою 9 існує послідовність <kn>n натуральних чисел, така що B (G) ізоморфна B (<kn>n). Позначимо через H пряму суму опій групи Z2. За лемою 7 B (H) $$$$ B (<kn>n). За лемою 10 B (I) $$$$ B (H). Отже, B (I) $$$$ B (G).

Припустимо, що G — скінченне розширення нескінченної циклічної підгрупи C, породженої елементом g. Можна вважати, що підгрупа C інваріантна і x-1gxg-1} для всіх елементів xРозкладемо G на праві суміжні класі по підгрупі C і виберемо деяку множину представників H={h1,h2,…, hn}, причому H=H-1. Для всіх i, j, 2,., n} виберемо a (i, j) так, що hi, hji, j) H. Покладемо a=max{|a (i, j)+1|: i, j, 2,., n}. Розглянемо граф Келі Сау групи G, визначений системою твірних H, g-1}. Покладемо V0={gkH: |k|, V1={gkH: a<|k|}, V2={gkH: 2a<|k|},… .

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

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

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

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

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

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

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

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

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

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

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

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

Доведення. Виберемо послідовність F0 скінченних підгруп групи G1 таку, що G1 = Fi, F0 — одинична підгрупа. Покладемо ki=|Fi+1: Fi|, n. Виберемо послідовність H0 скінченних підгруп групи G2 таку, що G2 = Hi, H0 — одинична підгрупа. Покладемо mi=|Hi+1: Hi|, i. За лемою 9 B (G1), B (<ki>i) і B (G2) B (<mi>i) попарно ізоморфні кульові структури. Відмітимо, що кожна скінченна підгрупа групи G1 міститься в деякій підгрупі Fk і кожна скінченна підгрупа групи G2 міститься в деякій підгрупі Hm. Отже, ми можемо застосувати лему 8.

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

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

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

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

Задача 3. Вказати зліченний локально скінченний граф Gr, такий що B (Gr) $$$$ B (G) для кожної зліченної групи G.

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

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

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

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

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