§ 9 Комбінаторні розміри підмножин графів і груп

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

Теорема 9.1 Якщо множину вершин V довільно зв'язного графа Gr(V,E) розбито на скінченне число підмножин V=V₁È V₂È …ÈV_n, то принаймні одна підмножина V_i розбиття має таку властивість: існує натуральне число m, таке що підмножина

{xÎV: B(x,k)Í B(V_i,m)}

непорожня для кожного натурального числа k.

Доведення. Розглянемо кульову структуру B(Gr) і, користуючись теоремою 8.2, виберемо кусково велику підмножину V_i розбиття.

Якщо Gr(V,E) - звязний граф скінченного діаметра, то кожна одноелементна підмножина {x}, xÎV велика в кульовій структурі B(Gr), еквівалентно, {x} має скінченний індекс. Отже, кожна підмножина довільного розбиття V на непорожні множини велика. Перше твердження наступної теореми показує, що це не можливо для графів нескінченного діаметра.

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

(і) множину V можна розбити на зліченне число малих підмножин;

(іі) множину V можна розбити на зліченне число великих підмножин.

Доведення. (і) Зафіксуємо довільну вершину xÎV і покладемо S₀(x)={x}, S_n+1(x)=B(x,n+1)\B(x,n), n Îw. Оскільки Gr - звязний граф нескінченного діаметра, то S_n(x)¹Æ для кожного nÎw. Очевидно, що V=È_nÎw S_n(x). Покажемо, що кожна підмножина S_n(x) мала. Візьмемо довільне натуральне число k і виберемо деяку вершину yÏB(S_n(x),k). Позначимо через d відстань від y до x. Тоді

B(S_n(x),k)ÍB(y, d+n+k)ÍB(V\B(S_n(x), k), d+n+k).

Отже, V=B(V\B(S_n(x), k), d+n+k).

(іі) Зафіксуємо пару натуральних чисел a, b і розглянемо нескінченну арифметичну прогресію W={an+b: nÎw}. Покладемо L(W)=È_nÎw S_an+b(x) і помітимо, що

B(x,b)ÍB(S_b(x),2b), B(x, a(n+1)+b)\B(x,an+b))ÍB(S_an+b(x),a)

для кожного nÎw. Отже, B(L(W), a+2b)=V і підмножина L(W) велика. Розіб'ємо w=È_iÎw W_i на нескінченні арифметичні прогресії. Тоді V= È_iÎw L(W_i ) і {L(W_i ): iÎw} диз'юнктна сім'я великих підмножин.

Приклад 9.1. Для кожного нескінченного кардинала a побудуємо зв'язний граф Gr(V,E) нескінченного діаметра, такий що множину вершин V не можна розбити на незліченне число великих підмножин. Візьмемо повний граф Gr'(V',E'), |V'|=a. Зафіксуємо довільний елемент xÎV' і візьмемо зліченну множину Y={y_n: nÎw}, таку що YÇV'=Æ. Покладемо

V= V'ÈY, E=E'È{(x, y₀)}È{(y_n, y_n+1): nÎw}.

Досить помітити що кожна велика підмножина множини вершин V графа Gr(V,E) містить деяку нескінченну підмножину множини Y.

Приклад 9.2. Для кожного нескінченного кардинала a побудуємо зв'язний граф Gr(V,E) нескінченного діаметра, такий що множину вершин V можна розбити на a великих підмножин. Візьмемо однорідне дерево локального степеня a. Зафіксуємо довільну вершину x дерева і виберемо по одному елементу з кожної підмножини S_n(x), n>0. Утвориться деяка підмножина L. Очевидно, що B(L,1)=V, а тому підмножина L велика. Далі множину вершин V легко розбити на a підмножин цього типу.

За теоремою 8.5. кульова структура B(Gr) довільного нескінченного звязного локального скінченного графа Gr w-розкладна відносно сім'ї всіх великих підмножин графа. Поширимо це твердження на довільні графи нескінченного діаметра.

Теорема 9.3. Множину V вершин довільного звязного графа Gr(V,E) нескінченного діаметра можна розбити на зліченне число підмножин V= È_iÎw A_i так, що жодне з підмножин V\A_i не є великою. Зокрема, існує розбиття V=V₁ÈV₂, таке що підмножини V₁, V₂ не є великими.

Доведення. Зафіксуємо довільний елемент x₀ÎV. Припустимо, що елементи x₀, x₁, …, x_n вже вибрано так, що B(x_i,i)ÇB(x_j,j)=Æ, 0£ i<j£ n. Виберемо mÎw так, що B(x_i,i)Í B(x₀,m) для всіх i£ n. Оскільки діаметр графа нескінченний то знайдеться елемент x_n+1ÏB(x₀, m+n+1). Тоді B(x_n+1, n+1)Ç B(x_i, i)=Æ для всіх i£ n. Застосуємо теорему 8.4 до послідовностей <n>_nÎw і <x_n>_nÎw .

Задача 9.1. Нехай Gr(V,E) - скінченний орієнтовний граф. Для кожної вершини vÎV позначимо через St(v) множину усіх вершин xÎV, для яких існує орієнтовний шлях від v до x. Визначимо передпорядок £ на V за таким правилом: v₁£ v₂ тоді і тільки тоді, коли St(v₁)Í St(v₂). Довести, що вершина v максимальна відносно £ тоді і тільки тоді, коли {v} кусково велика підмножина кульової структури (Gr).

Перейдемо до кульових структур груп.

Теорема 9.4. Для довільного скінченного розбиття G=A₁ÈA₂È…ÈA_n групи G знайдуться такі підмножини розбиття A_i і скінченна підмножина F, що G=F A_i A_i^-1.

Доведення. Застосуємо теорему 8.2 до кульової структури B_l(G) і виберемо кусково велику підмножину A_i розбиття. Тоді знайдеться така скінченна підмножина F, що підмножина

{xÎG: B_l(x,K) Í B_l(A_i ,F)}

непорожня для довільної скінченної підмножини K групи G, що містить одиницю e. Позначимо через Fin_e сім'ю всіх скінченних підмножин з одиницею. Для кожної підмножини KÎFin_e виберемо елемент x(K)ÎG, такий що K x(K)Í F A_i. Оскільки eÎK, то x(K)=f(K) a(K) для деяких елементів f(K)ÎF, a(K)ÎA_i. Виберемо конфінальну в Fin_e підмножину Fin' таку, що f(K)=f для всіх KÎFin'. Тоді для кожного gÎG знайдеться a(g)ÎA_i, такий що gfa(g)ÎFA_i. Значить,

GÍ F A_i A_i^-1f=F A_i A_i^-1 .

Використовуючи техніку ультрафільтрів, можна довести [29], що G=FA_iA_i^-1=FA_i^-1A_i для деяких підмножини A_i розбиття і скінченної підмножини F. Цікаво було б довести це твердження елементарними методами.

Теорему 9.4. можна посилити в іншому напрямку [7]: якщо групу G розбито на n підмножин G=A₁ÈA₂È…ÈA_n, то знайдуться такі підмножинa A_i розбиття, натуральне число k£ і підмножина KÍ G, що G = FA_iA_i^-1 , |K|£ k і (A_iA_i^-1) - підгрупа групи G.

Задача 9.2. Нехай аменабільну групу G розбито на n підмножин G=A₁ÈA₂È…ÈA_n. Довести, що знайдуться підмножина A_i розбиття і скінченна підмножина K, такі що

G=KA_iA_i^-1 , |K|£ n.

Проблема 9.1. Довільну групу G розбито на n підмножин G=A₁ÈA₂È…ÈA_n. Чи вірно, що G=KA_iA_i^-1 для деякої підмножини A_i розбиття і деякої скінченної підмножини K, |K|£ n?

За теоремою 4.11 кожну нескінченну групу G можна розбити на зліченне число підмножин, кожна з яких велика в кульових структурах B_l(G), B_r(G).

Можна довести [7], що кожну нескінченну групу можна розбити на зліченне число підмножин, кожна з яких мала в кульових структурах B_l(G), B_r(G).

За теоремою 8.5. кожну зліченну групу G можна розбити на зліченне число підмножин G=È_nÎw A_n так, що кожна підмножина G\A_n не являється великою в кульовій структурі B_l(G). Це твердження узагальнюється так [28].

Нехай G - нескінченна група потужності a, g=cfa. Тоді існує розбиття G=È_d<a X_d групи X, таке що G¹F(G\X_d) для кожного d<a і кожної підмножини F потужності <g. Зокрема, кожну групу G регулярної потужності a можна розбити на дві підмножини G=A₁ÈA₂ так, що G¹FA₁, G¹FA₂ для кожної підмножини F потужності <a. Невідомо [4], чи вірне це твердження для груп сингулярної потужності.

Задача 9.3. Довести що кожну нескінченну групу G потужності a можна розбити на a підмножин G=È_d<a G_d так, що кожна підмножина G\G_d не є великою в кульовій структурі B_l(G).

Задача 9.4. Довести що підмножина S групи G мала в кульових структурах B_l(G) і B_r(G) тоді і тільки тоді, коли підмножина G\FSF велика в кульових структурах B_l(G) і B_r(G).

Задача 9.5. Довести що кожна нескінченна група G породжується деякою підмножиною S, малою в кульових структурах B_l(G) і B_r(G).

Для напівгрупи S з одиницею e визначимо дві кульові структури B_l(S)=(S, Fin_e, B_l) і B_r(S)=(S, Fin_e, B_r), де Fin_e - сім'я усіх скінченних підмножин, що містять одиницю, B_l(x,F)=Fx, B_r(x,F)=xF.

Нехай X - нескінченна підмножина потужності g, S(X) - напівгрупа всіх відображень X®X. О. Равський довів, що для будь-якого розбиття S(X)=È_a<g S_a існує a<g, таке що S(X)=S_a s для деякого елемента sÎS(X). Отже, принаймні одна із підмножин розбиття є великою в кульовій структурі B_r(S(x)). В [32] побудована зліченна напівгрупа, така що для довільного її скінченного розбиття принаймні одна із підмножин розбиття велика справа. Таким чином, зліченна напівгрупа S не є розкладною відносно сім'ї великих справа підмножин із S. Цей же приклад показує, що теорема 4.11 теж не поширюється на всі напівгрупи.