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

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

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

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

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

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

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

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

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

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

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

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

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

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

B(x,b)Í B(Sb(x),2b), B(x, a(n+1)+b)\B(x,an+b))Í B(San+b(x),a)

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

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

V= V'È Y, E=E'È{(x, y0)}È{(yn, yn+1): n Î w}.

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

Приклад 9.2. Для кожного нескінченного кардинала a побудуємо зв'язний граф Gr(V,E) нескінченного діаметра, такий що множину вершин V можна розбити на a великих підмножин. Візьмемо однорідне дерево локального степеня a. Зафіксуємо довільну вершину x дерева і виберемо по одному елементу з кожної підмножини Sn(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 Ai так, що жодне з підмножин V\Ai не є великою. Зокрема, існує розбиття V=V1 È V2, таке що підмножини V1, V2 не є великими.

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

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

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

Теорема 9.4. Для довільного скінченного розбиття G=A1 È A2 È…È An групи G знайдуться такі підмножини розбиття Ai і скінченна підмножина F, що G=F Ai Ai-1.

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

{x Î G: Bl(x,K) Í Bl(Ai ,F)}

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

G Í F Ai Ai-1f=F Ai Ai-1 .

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

Теорему 9.4. можна посилити в іншому напрямку [7]: якщо групу G розбито на n підмножин G=A1 È A2 È…È An, то знайдуться такі підмножинa Ai розбиття, натуральне число k£ і підмножина K Í G, що G = FAiAi-1 , |K|£ k і (AiAi-1) - підгрупа групи G.

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

G=KAiAi-1 , |K|£ n.

Проблема 9.1. Довільну групу G розбито на n підмножин G=A1 È A2 È…È An. Чи вірно, що G=KAiAi-1 для деякої підмножини Ai розбиття і деякої скінченної підмножини 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 An так, що кожна підмножина G\An не являється великою в кульовій структурі B l(G). Це твердження узагальнюється так [28].

Нехай G - нескінченна група потужності a, g=cf a. Тоді існує розбиття G=È d<a X d групи X, таке що G ¹ F(G\X d) для кожного d<a і кожної підмножини F потужності <g. Зокрема, кожну групу G регулярної потужності a можна розбити на дві підмножини G=A1 È A2 так, що G ¹ FA1, G ¹ FA2 для кожної підмножини 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, Fine, Bl) і B r(S)=(S, Fine, Br), де Fine - сім'я усіх скінченних підмножин, що містять одиницю, Bl(x,F)=Fx, Br(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 теж не поширюється на всі напівгрупи.