§ 4. Квазіцикли і квазіпромені

Послідовність x1,x2,…,xk різних вершин зв'язного графа Gr(V,E) називається квазіциклом, якщо

d(x1,x2)£ 3, d(x2,x3)£ 3,…, d(xk-1,xk)£ 3, d(xk,x1)£ 3.

В кожному скінченному зв'язному графі існує квазіцикл, що проходить через кожну його вершину. Це твердження випливає з такої теореми про квазіцикл.

Теорема 4.1. Нехай Gr(V,E) - скінченний зв'язний граф, |V|=n, n ³ 2. Для довільних суміжних вершин x,y Î V існує квазіцикл x1,x2,…,xn , такий що x=x1, y=xn .

Доведення. Оскільки в графі Gr(V,E) є кістяк, в якому вершини x,y теж суміжні, можна вважати, що Gr(V,E) - дерево. Застосуємо індукцію по n. Для n=2 твердження очевидне. Приймемо припущення індукції і розглянемо два випадки.

Випадок 1. |B(x,1)|=2, тобто x - кінцева вершина дерева і B(x,1)={x,y}. Видалимо вершину x і ребро (x,y). Одержимо дерево Gr'(V',E') з множиною вершин V'=V\{x} і множиною ребер E'=E\{x,y}. Виберемо вершину z, суміжну з вершиною y в дереві Gr'(V',E') . За припущенням індукції існує квазіцикл x2,x3,…,xn в дереві Gr', такий що x2=z, xn=y. Тоді x1,x2, x3,…,xn - квазіцикл в дереві Gr.

Випадок 2. |B(x,1)|>2. Якщо |B(y,1)|=1, то заміною пари x,y парою y,x ми опиняємося у першому випадку. Отже, можна вважати, що |B(x,1)|>1, |B(y,1)|>1. Видалимо ребро (x,y) і одержимо два дерева Gr1(V1,E1), Gr2(V2,E2) з коренями x і y. Нехай |V1|=k, |V2|=m. Оскільки k ³ 2, m ³ 2, то за припущенням індукції існують квазіцикли x1,x2,…,xk і y1,y2,…,xm в деревах Gr1 і Gr2, такі що x1=x, ym=y і (x1,xk)Î E1, (y1,ym)Î E2 . Оскільки відстань між xk та y1 в дереві Gr дорівнює 2, то x1,x2,…,xk , y1,y2,…,xm - потрібний нам квазіцикл в дереві Gr.

Задача 4.1. Навести приклад скінченного дерева Gr(V,E), для якого не існує упорядкування x1,x2,…,xn множини вершин V, такого що d(x1,x2)£ 2, d(x2,x3)£ 2,…, d(xn-1,xn)£ 2. Графи, що допускають подібні упорядкування вивчаються в наступному параграфі.

Застосуємо теорему 4.1 для побудови деяких розбиттів графів.

Теорема 4.2. Нехай r,n - натуральні числа, r - дільник числа n. Для кожного зв'язного графа Gr(V,E), |V|=n існує врівноважене розбиття V=V0 È V1 È…È Vr-1 таке що

dist(V0,V1)£ 3, dist(V1,V2)£ 3,…, dist(Vr-2,Vr-1 )£ 3, dist(Vr-1, V0 )£ 3.

Доведення. Для n=1 твердження очевидне. Для n ³ 2 візьмемо довільні суміжні вершини x,y. За теоремою 4.1 існує бієкція f: V® {0,1,…,n-1}, така що f(0)=x, f(n-1)=y і d(f(i),f(i+1))£ 3 для всіх i Î {0,1,…,n-2}. Для довільної вершини v Î V покладемо c(v)=f(v) mod r. Покладемо V0=c -1(0), V1=c -1(1),…, Vr-1=c -1(r-1).

Зауважимо, що індекс кожної підмножини розбиття з теореми 4.2 не перевищує 3r . Отже, порівняно з теоремою 1.2, теорема 4.2 програє в оцінці індексу розбиття, але виграє в оцінці відстаней між сусідніми підмножинами розбиття.

Послідовність <xn>n Î w різних вершин нескінченного зв'язного графа називається квазіпроменем, якщо d(xn , xn+1)£ 3 для всіх n Î w . Граф Gr(V,E) назвемо квазіпроменевим, скорочено qr-графом, якщо існує квазіпромінь, що проходить через усі вершини цього графа. Якщо в скінченному зв'язному графі, за теоремою 4.1, існує квазіцикл, що проходить через усі вершини, далеко не кожен нескінченний зв'язний граф має квазіпромінь, що проходить через усі його вершини. Характеризація локальноскінченних qr-дерев викладена в наступному параграфі. Незважаючи на це, поняття квазіпроменя виявляється досить корисним для побудови розбиттів довільних нескінченних зв'язних графів. Центральними результатами цього параграфу є наступні дві теореми.

Теорема 4.3. Нехай Gr(V,E) - зліченний зв'язний граф. Тоді існує розбиття A множини вершин V на скінченне або зліченне число підмножин, таке що для кожної підмножини A Î A

(і) граф Gr[A] зв'язний;

(іі) граф Gr[A] є qr-графом.

Доведення. Оскільки кожен звязний граф має кістяк, ми можемо вважати граф Gr(V,E) деревом. Зафіксуємо довільну вершину x Î V і назвемо її коренем. Для кожного натурального числа позначимо через Si множину усіх вершин дерева, відстань від яких до кореня дорівнює i. Позначимо через Si' множину всіх вершин y Î Si, через які проходить скінченне число шляхів з початком у корені x, Si''= Si \ Si'. Розглянемо два випадки.

Випадок 1. Множина Si' скінченна. Нехай Si'={y1,y2,…,yn}. Позначимо через T1, T2,…,Tn дерева з коренями y1,y2,…,yn, що утворюються після видалення вершини x і ребер (x,y1), (x,y2),…,(x,yn). Позначимо через V1,V2,…,Vn множини вершин дерев T1, T2,…,Tn і покладемо X={x}È V1 È V2 È…È Vn. Виберемо довільну вершину y Î S1'. Якщо S1'=Æ покладемо y=x. За теоремою 4.1 існує квазіцикл x1,x2,…,xk , що проходить через усі вершини звязного графа Gr[X'], такий що x1=x, xk=y. Для продовження цього квазіциклу до квазіпроменя виберемо довільну вершину z Î S1'', суміжну з вершиною x видалимо всі вершини утвореного квазіцикла і до дерева з коренем z застосуємо рекурсію. Врешті решт ми побудуємо квазіпромінь, що виходить з кореня x, враховуючи при цьому ситуації, що можуть виникнути у випадку 2.

Випадок 2. Множина S1' нескінченна. Нехай S1'={yn: n Î w}. Позначимо через Tn дерево з коренем yn, утворене видаленням ребра (x,yn). Нехай Vn - множина всіх вершин дерева Tn. Покладемо X={x}ÈÈ n Î w Vn. Послідовним застосуванням теореми 4.1 побудуємо квазіпромінь з початком в x, що проходить через всі вершини звязного графа Gr[X].

Як в першому, так і у другому випадках, вже побудовано квазіпромінь з початком у вершині x. Видалимо з дерева всі вершини, через які проходить цей квазіпромінь. Виберемо найменше натуральне число i, для якого підмножина Si'' не увійшла до утвореного квазіпроменя. Зауважимо, що при цьому Si'=Æ. Виберемо довільний елемент z Î Si'', через який не пройшов квазіпромінь, і застосуємо рекурсію до дерева з коренем z.

Теорема 4.4. Нехай Gr(V,E) - довільний нескінченний зв'язний граф. Тоді існує розбиття A множини V на зліченні підмножини, таке що для кожної підмножини A Î A

(і) граф Gr[A È {x}] зв'язний для деякого елемента x Î V;

(іі) граф Gr[A È {x}] є qr-графом з квазіпроменем, що починається з вершини x.

Доведення. Застосуємо схему доведення і позначення теореми 4.3. Відмінність може виникнути лише у випадку 2. Якщо множина S1' незліченна, то розіб'ємо її на зліченні підмножини і для кожної з них побудуємо відповідний квазіпромінь з початком в корені x дерева Gr(V,E).

Теорема 4.5. Для кожного нескінченного звязного графа Gr(V,E) і кожного натурального числа r існує розбиття V=V0 È V1 È…È Vr-1, таке що

dist(V0 ,V1)£ 3, dist(V1 ,V2)£ 3,…,dist(Vr-2 ,Vr-1)£ 3.

Доведення. Розбиття з доведення теореми 4.2 застосуємо до кожного квазіпроменя, що виникає в процесі доведення теореми 4.4.

Теорема 4.5. Нехай Gr(V,E) - нескінченний звязний граф. Тоді існує зліченна сім'я {Á n: n Î w} розбиттів множини V, така що

(і) |F|=n+1, diam F £ 3n для всіх F Î Á n;

(іі) якщо n+1|m+1, то Á m є укрупненням розбиття Á n, тобто кожна підмножина розбиття Á m є об'єднанням підмножин розбиття Á n.

Доведення. Скористаємося розбиттям A з теореми 4.4. Для кожної підмножини A Î A побудуємо квазіпромінь <xn>n Î w , що проходить через усі вершини підмножини A. Розіб'ємо цей квазіпромінь на відрізки

{x0,x1,…,xn}, {xn+1,xn+2,…,x2n+1},{x2n+2,x2n+3,…,x3n+2},…

Одержані відрізки оголосимо підмножинами розбиття Á n.

Теорема 4.6. Нехай G - нескінченна група з одиницею e, S - скінченна підмножина групи G, що породжує нескінченну підгрупу, S=S-1, e Î S. Тоді існує зліченна сім'я розбиттів {Á n: n Î w} групи 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. Застосуємо теорему 4.5 до кожної звязної компоненти графа Cay(G,S).

Для подальшого розвитку теми скористаємося відомою теоремою про спільну трансверсаль двох розбиттів [5, теорема 7.4.4].

Нехай X - довільна множина, n - натуральне число, Á,Á' - розбиття множини X на підмножини потужності n. Тоді існує підмножина T Í X, така що |T Ç F|=|T Ç F'|=1 для всіх підмножин F Î Á n, F'Î Á n'. Підмножина T називається спільною трансверсаллю розбиттів Á,Á'.

Теорема 4.7. Нехай G - нескінченна група з одиницею e, S - скінченна підмножина групи G, що породжує нескінченну підгрупу, S=S-1, e Î S. Тоді для кожного n Î w існує розбиття 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 і т.д.

Теорема 4.8. Нехай G - нескінченна група з одиницею e, S - скінченна підмножина групи G, що породжує нескінченну підгрупу, S=S-1, e Î S. Тоді існує розбиття G= È n Î w Xn, таке що

G=S 3×2n Xn=Xn S 3×2n

для всіх n Î w .

Доведення. Застосуємо сім'ю розбиттів {Á n n: n Î w } з теореми 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 і.т.д.

Теорема 4.9. Нехай G - довільна група, H - скінченна підгрупа групи G, |H|=n+1. Тоді існує розбиття G=X0 È X1 È…È Xn таке що G=H Xi=Xi H для всіх i Î{0,1,…,n}.

Доведення. Розглянемо розбиття групи G на праві та ліві суміжні класи за підгрупою H і до цієї пари розбиттів застосуємо теорему про спільну трансверсаль.

Теорема 4.10. . Нехай G - нескінченна група, H0 Ì H1 Ì…Ì Hn Ì… - зростаючий ланцюг її скінченних підгруп, |H0|>1. Тоді існує розбиття G=È n Î w Xn таке що G=Hn Xn = Xn Hn для всіх n Î w.

Доведення. Для кожного n Î w позначимо через Á n та Á n' розбиття групи G на ліві та праві суміжні класи по підгрупі Hn. До сім'ї розбиттів {Á n : n Î w } застосуємо міркування з доведення теореми 4.8.

Підмножина X групи G називається великою зліва (справа), якщо знайдеться така скінченна підмножина F Í G, що G=FX (G=XF). Підмножина X, що одночасно велика зліва і справа, називається великою. А. Белла та В.І. Малихін поставили таке запитання [14].

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

Відповідь на це запитання дає остання теорема цього параграфу.

Теорема 4.11. Кожну нескінченну групу G можна розбити на зліченне число великих підмножин.

Доведення. Якщо кожна скінченна підмножина групи G породжує скінченну підгрупу, то в групі G існує зростаючий ланцюг H0 Ì H1 Ì…Ì Hn Ì… скінченних підгруп. В цьому випадку застосовуємо теорему 4.10. В іншому випадку деяка скінченна підмножина S Ì G породжує нескінченну підгрупу. Застосовуємо теорему 4.8.

Задача 4.2. Довести, що будь-яка сім'я великих зліва підмножин аменабельної (зокрема, абелевої) групи, що попарно не перетинаються, є скінченною або зліченною. Нагадаємо, що група G називається аменабельною, якщо існує міра m, визначена на всіх підмножинах групи G, така що

(і) m(G)=1;

(іі) m(A1 È A2 È …È An)= m(A1)+m(A2)+ …+m(An) для довільних підмножин A1, A2, …, An, що попарно не перетинаються;

(ііі) m(gA)=m(A) для довільних g Î G, A Í G.

Задача 4.3. Нехай X - довільна нескінченна множина, F(X)- вільна група в алфавіті X. Вказати розбиття групи G на |X| великих зліва підмножин. Вказати розбиття групи G на |X| великих підмножин.

Нехай G - довільна група, X - непорожня підмножина із G. Лівим (правим) індексом підмножини X назвемо найменший кардинал k, для якого знайдеться підмножина F Í G, |F|=k, така що G=FX (G=XF). Максимальний серед лівого та правого індексів називається індексом підмножини X.

Задача 4.4. Нехай G - нескінченна група, |G|=k. Довести, що існує розбиття групи G на k підмножин, лівий індекс кожної з яких <k.

Проблема 4.1. Нехай G - нескінченна група, |G|=k. Чи можна розбити G на k підмножин, індекс кожної з яких <k ?