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

Теорема 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)={F\X0 : F((n(0)}, (n'(1)={F-1: F((n (1)}

і до пари розбиттів (n (1), (n'(1) множини G\X0 застосуємо теорему про спільну трансверсаль. Позначимо цю спільну трансверсаль через X1 видалимо підмножину X1 з G\X0 і т.д.

Теорема 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' множини G\X0 застосуємо теорему про спільну трансверсаль і виберемо підмножину X1 ( G\X0 таку що |X1( F|=|X1( F-1|=1 для всіх F(A1. Видалимо X1 з множини G\X0 і позначимо

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

Чи кожну нескінченну групу можна розбити на дві великі підмножини?