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

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

d(x₁,x₂)£ 3, d(x₂,x₃)£ 3,…, d(x_k-1,x_k)£ 3, d(x_k,x₁)£ 3.

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

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

Доведення. Оскільки в графі 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') . За припущенням індукції існує квазіцикл x₂,x₃,…,x_n в дереві Gr', такий що x₂=z, x_n=y. Тоді x₁,x_2, x₃,…,x_n - квазіцикл в дереві Gr.

Випадок 2. |B(x,1)|>2. Якщо |B(y,1)|=1, то заміною пари x,y парою y,x ми опиняємося у першому випадку. Отже, можна вважати, що |B(x,1)|>1, |B(y,1)|>1. Видалимо ребро (x,y) і одержимо два дерева Gr₁(V₁,E₁), Gr₂(V₂,E₂) з коренями x і y. Нехай |V₁|=k, |V₂|=m. Оскільки k³ 2, m³ 2, то за припущенням індукції існують квазіцикли x₁,x_2,…,x_k і y₁,y_2,…,x_m в деревах Gr₁ і Gr₂, такі що x₁=x, y_m=y і (x₁,x_k)ÎE₁, (y₁,y_m)ÎE₂ . Оскільки відстань між x_k та y₁ в дереві Gr дорівнює 2, то x₁,x_2,…,x_k , y₁,y_2,…,x_m - потрібний нам квазіцикл в дереві Gr.

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

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

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

dist(V₀,V₁)£ 3, dist(V₁,V₂)£ 3,…, dist(V_r-2,V_r-1 )£ 3, dist(V_r-1, V₀ )£ 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. Покладемо V₀=c ^-1(0), V₁=c ^-1(1),…, V_r-1=c ^-1(r-1).

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

Послідовність <x_n>_nÎw різних вершин нескінченного зв'язного графа називається квазіпроменем, якщо d(x_{n ,} x_n+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 і назвемо її коренем. Для кожного натурального числа позначимо через S_i множину усіх вершин дерева, відстань від яких до кореня дорівнює i. Позначимо через S_i' множину всіх вершин yÎS_i, через які проходить скінченне число шляхів з початком у корені x, S_i''= S_i \ S_i'. Розглянемо два випадки.

Випадок 1. Множина S_i' скінченна. Нехай S_i'={y₁,y₂,…,y_n}. Позначимо через T₁, T₂,…,T_n дерева з коренями y₁,y₂,…,y_n, що утворюються після видалення вершини x і ребер (x,y₁), (x,y₂),…,(x,y_n). Позначимо через V₁,V₂,…,V_n множини вершин дерев T₁, T₂,…,T_n і покладемо X={x}ÈV₁ÈV₂È…ÈV_n. Виберемо довільну вершину yÎS₁'. Якщо S₁'=Æ покладемо y=x. За теоремою 4.1 існує квазіцикл x₁,x_2,…,x_k , що проходить через усі вершини звязного графа Gr[X'], такий що x₁=x, x_k=y. Для продовження цього квазіциклу до квазіпроменя виберемо довільну вершину zÎS₁'', суміжну з вершиною x видалимо всі вершини утвореного квазіцикла і до дерева з коренем z застосуємо рекурсію. Врешті решт ми побудуємо квазіпромінь, що виходить з кореня x, враховуючи при цьому ситуації, що можуть виникнути у випадку 2.

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

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

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

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

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

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

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

dist(V₀ ,V₁)£ 3, dist(V₁ ,V₂)£ 3,…,dist(V_r-2 ,V_r-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 побудуємо квазіпромінь <x_n>_nÎw , що проходить через усі вершини підмножини A. Розіб'ємо цей квазіпромінь на відрізки

{x₀,x₁,…,x_n}, {x_n+1,x_n+2,…,x_2n+1},{x_2n+2,x_2n+3,…,x_3n+2},…

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

Теорема 4.6. Нехай G - нескінченна група з одиницею e, S - скінченна підмножина групи G, що породжує нескінченну підгрупу, S=S^-1, eÎS. Тоді існує зліченна сім'я розбиттів {Á_n: nÎw} групи G, така що

(і) |F|=n+1 і xy^-1ÎS ³ⁿ для всіх 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=X₀È X₁È…È X_n, таке що

G=S ³ⁿX_i=X_i S ³ⁿ

для кожного iÎ{0,1,…,n}.

Доведення. Розглянемо розбиття Á_n з теореми 4.6. Покладемо Á_n(0)=Á_n, Á_n^'(0)={F^-1: FÎÁ_n }. До пари розбиттів Á_n(0),Á_n^'(0) застосуємо теорему про спільну трансверсаль і виберемо підмножину X₀ ÍG, таку що |X₀ Ç F|=|X₀ Ç F^-1|=1 для всіх FÎÁ_n(0). Видалимо X₀ з групи G, покладемо

Á_n(1)={F\X₀ : FÎÁ_n(0)}, Á_n^'(1)={F^-1: FÎÁ_n (1)}

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

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

G=S ^3×2n X_n=X_n S ^3×2n

для всіх nÎw .

Доведення. Застосуємо сім'ю розбиттів {Á_n n: nÎw } з теореми 4.6. Покладемо A₀=Á₁, A₀' ={F^-1: FÎÁ₁}. До пари розбиттів A₁ , A₁' множини G\X₀ застосуємо теорему про спільну трансверсаль і виберемо підмножину X₁ Í G\X₀ таку що |X₁Ç F|=|X₁Ç F^-1|=1 для всіх FÎA₁. Видалимо X₁ з множини G\X₀ і позначимо

A₂={F\(X₀ ÈX₁): FÎÁ₄}, A₂'={F^-1: FÎA₂}.

До пари розбиттів A₂, A₂' множини G\(X₀ ÈX₁) застосуємо теорему про спільну трансверсаль, позначимо цю спільну трансверсаль через X₂ і.т.д.

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

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

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

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

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

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

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

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

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

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

(і) m(G)=1;

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

(ііі) 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 ?