WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Розкладність графів. Квазіцикли і квазіпромені - Реферат

Розкладність графів. Квазіцикли і квазіпромені - Реферат

випадку 2. Якщо множина S1' незліченна, то розіб'ємо її на зліченні підмножини і для кожної з них побудуємо відповідний квазіпромінь з початком в корені x дерева Gr(V,E).
Теорема 5. Для кожного нескінченного звязного графа Gr(V,E) і кожного натурального числа r існує розбиття V=V0 V1 … Vr-1, таке що
dist(V0 ,V1) 3, dist(V1 ,V2) 3,…,dist(Vr-2 ,Vr-1) 3.
Доведення. Розбиття з доведення теореми 2 застосуємо до кожного квазіпроменя, що виникає в процесі доведення теореми 4.
Теорема 5. Нехай Gr(V,E) - нескінченний звязний граф. Тоді існує зліченна сім'я { n: n } розбиттів множини V, така що
(і) |F|=n+1, diam F 3n для всіх F n;
(іі) якщо n+1|m+1, то m є укрупненням розбиття n, тобто кожна підмножина розбиття m є об'єднанням підмножин розбиття n.
Доведення.Скористаємося розбиттям A з теореми 4. Для кожної підмножини A A побудуємо квазіпромінь n , що проходить через усі вершини підмножини A. Розіб'ємо цей квазіпромінь на відрізки
{x0,x1,…,xn}, {xn+1,xn+2,…,x2n+1},{x2n+2,x2n+3,…,x3n+2},…
Одержані відрізки оголосимо підмножинами розбиття n.
Теорема 6. Нехай G - нескінченна група з одиницею e, S - скінченна підмножина групи G, що породжує нескінченну підгрупу, S=S-1, e S. Тоді існує зліченна сім'я розбиттів { n: n } групи G, така що
(і) |F|=n+1 і xy-1 S 3n для всіх x,y F і кожної підмножини F n;
(іі) якщо n+1|m+1, то m є укрупненням розбиття n.
Доведення. Розглянемо граф Келі Cay(G,S), де x,y E тоді і тільки тоді, коли x,y G, x y, xy-1 S. Застосуємо теорему 5 до кожної звязної компоненти графа Cay(G,S).
Для подальшого розвитку теми скористаємося відомою теоремою про спільну трансверсаль двох розбиттів [5, теорема 4].
Нехай X - довільна множина, n - натуральне число, , ' - розбиття множини X на підмножини потужності n. Тоді існує підмножина T X, така що |T F|=|T F'|=1 для всіх підмножин F n, F' n'. Підмножина T називається спільною трансверсаллю розбиттів , '.
Теорема 7. Нехай G - нескінченна група з одиницею e, S - скінченна підмножина групи G, що породжує нескінченну підгрупу, S=S-1, e S. Тоді для кожного n існує розбиття G=X0 X1 … Xn, таке що
G=S 3nXi=Xi S 3n
для кожного i {0,1,…,n}.
Доведення. Розглянемо розбиття n з теореми 4.6. Покладемо n(0)= n, n'(0)={F-1: F n }. До пари розбиттів n(0), n'(0) застосуємо теорему про спільну трансверсаль і виберемо підмножину X0 G, таку що |X0 F|=|X0 F-1|=1 для всіх F n(0). Видалимо X0 з групи G, покладемо
n(1)={FX0 : F n(0)}, n'(1)={F-1: F n (1)}
і до пари розбиттів n (1), n'(1) множини GX0 застосуємо теорему про спільну трансверсаль. Позначимо цю спільну трансверсаль через X1 видалимо підмножину X1 з GX0 і т.д.
Теорема 8. Нехай G - нескінченна група з одиницею e, S - скінченна підмножина групи G, що породжує нескінченну підгрупу, S=S-1, e S. Тоді існує розбиття G= n Xn, таке що
G=S 3 2n Xn=Xn S 3 2n
для всіх n .
Доведення. Застосуємо сім'ю розбиттів { n n: n } з теореми 4.6. Покладемо A0= 1, A0' ={F-1: F 1}. До пари розбиттів A1 , A1' множини GX0 застосуємо теорему про спільну трансверсаль і виберемо підмножину X1 GX0 таку що |X1 F|=|X1 F-1|=1 для всіх F A1. Видалимо X1 з множини GX0 і позначимо
A2={F(X0 X1): F 4}, A2'={F-1: F A2}.
До пари розбиттів A2, A2' множини G(X0 X1) застосуємо теорему про спільну трансверсаль, позначимо цю спільну трансверсаль через X2 і.т.д.
Теорема 9. Нехай G - довільна група, H - скінченна підгрупа групи G, |H|=n+1. Тоді існує розбиття G=X0 X1 … Xn таке що G=H Xi=Xi H для всіх i {0,1,…,n}.
Доведення. Розглянемо розбиття групи G на праві та ліві суміжні класи за підгрупою H і до цієї пари розбиттів застосуємо теорему про спільну трансверсаль.
Теорема 10. Нехай G - нескінченна група, H0 H1 … Hn … - зростаючий ланцюг її скінченних підгруп, |H0|>1. Тоді існує розбиття G= n Xn таке що G=Hn Xn = Xn Hn для всіх n .
Доведення. Для кожного n позначимо через n та n' розбиття групи G на ліві та праві суміжні класи по підгрупі Hn. До сім'ї розбиттів { n : n } застосуємо міркування з доведення теореми 8.
Підмножина X групи G називається великою зліва (справа), якщо знайдеться така скінченна підмножина F G, що G=FX (G=XF). Підмножина X, що одночасно велика зліва і справа, називається великою. А. Белла та В.І. Малихін поставили таке запитання [14].
Чи кожну нескінченну групу можна розбити на дві великі підмножини?
Відповідь на це запитання дає остання теорема цього параграфу.
Теорема 11. Кожну нескінченну групу G можна розбити на зліченне число великих підмножин.
Доведення. Якщо кожна скінченна підмножина групи G породжує скінченну підгрупу, то в групі G існує зростаючий ланцюг H0 H1 … Hn … скінченних підгруп. В цьому випадку застосовуємо теорему 10. В іншому випадку деяка скінченна підмножина S G породжує нескінченну підгрупу. Застосовуємо теорему 8.
Задача 2. Довести, що будь-яка сім'я великих зліва підмножин аменабельної (зокрема, абелевої) групи, що попарно не перетинаються, є скінченною або зліченною. Нагадаємо, що група G називається аменабельною, якщо існує міра , визначена на всіх підмножинах групи G, така що
(і) (G)=1;
(іі) (A1 A2 … An)= (A1)+ (A2)+ …+ (An) для довільних підмножин A1, A2, …, An, що попарно не перетинаються;
(ііі) (gA)= (A) для довільних g G, A G.
Задача 3. Нехай X - довільна нескінченна множина, F(X)- вільна група в алфавіті X. Вказати розбиття групи G на |X| великих зліва підмножин. Вказати розбиття групи G на |X| великих підмножин.
Нехай G - довільна група, X - непорожня підмножина із G. Лівим (правим) індексом підмножини X назвемо найменший кардинал k, для якого знайдеться підмножина F G, |F|=k, така що G=FX (G=XF). Максимальний серед лівого та правого індексів називається індексом підмножини X.
Задача 4. Нехай G - нескінченна група, |G|=k. Довести, що існує розбиття групи G на k підмножин, лівий індекс кожної з яких Проблема 1. Нехай G - нескінченна група, |G|=k. Чи можна розбити G на k підмножин, індекс кожної з яких
Loading...

 
 

Цікаве