Реферат на тему:

Розкладність графів. Комбінаторні розміри підмножин графів і груп

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

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

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

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

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

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

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

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

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

Доведення. (і) Зафіксуємо довільну вершину x(V і покладемо S0(x)={x},
Sn+1(x)=B(x,n+1)\B(x,n), n ((. Оскільки Gr ( звязний граф нескінченного
діаметра, то Sn(x)(( для кожного n((. Очевидно, що V=(n(( 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((}. Покладемо L(W)=(n(( 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((. Отже, B(L(W), a+2b)=V і підмножина L(W) велика.
Розіб’ємо (=(i(( Wi на нескінченні арифметичні прогресії. Тоді V= (i((
L(Wi ) і {L(Wi ): i((} диз’юнктна сім’я великих підмножин.

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

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

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

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

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

Теорема 3. Множину V вершин довільного звязного графа Gr(V,E)
нескінченного діаметра можна розбити на зліченне число підмножин V= (i((
Ai так, що жодне з підмножин V\Ai не є великою. Зокрема, існує розбиття
V=V1(V2, таке що підмножини V1, V2 не є великими.

Доведення. Зафіксуємо довільний елемент x0(V. Припустимо, що елементи
x0, x1, …, xn вже вибрано так, що B(xi,i)(B(xj,j)=(, 0( in(( і n(( .

(Gr).

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

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

Доведення. Застосуємо теорему до кульової структури 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. Цікаво було б довести це твердження елементарними
методами.

( підгрупа групи G.

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

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

Проблема 1. Довільну групу G розбито на n підмножин G=A1(A2(…(An. Чи
вірно, що G=KAiAi-1 для деякої підмножини Ai розбиття і деякої
скінченної підмножини K, |K|( n?

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

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

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

Нехай G ( нескінченна група потужності (, (=cf(. Тоді існує розбиття
G=((<( X( групи X, таке що G(F(G\X() для кожного (<( і кожної підмножини F потужності <(. Зокрема, кожну групу G регулярної потужності ( можна розбити на дві підмножини G=A1(A2 так, що G(FA1, G(FA2 для кожної підмножини F потужності <(. Невідомо [4], чи вірне це твердження для груп сингулярної потужності. Задача 3. Довести що кожну нескінченну групу G потужності ( можна розбити на ( підмножин G=((<( G( так, що кожна підмножина G\G( не є великою в кульовій структурі Bl(G). Задача 4. Довести що підмножина S групи G мала в кульових структурах Bl(G) і Br(G) тоді і тільки тоді, коли підмножина G\FSF велика в кульових структурах Bl(G) і Br(G). Задача 9.5. Довести що кожна нескінченна група G породжується деякою підмножиною S, малою в кульових структурах Bl(G) і Br(G). Для напівгрупи S з одиницею e визначимо дві кульові структури Bl(S)=(S, Fine, Bl) і Br(S)=(S, Fine, Br), де Fine ( сім'я усіх скінченних підмножин, що містять одиницю, Bl(x,F)=Fx, Br(x,F)=xF. Нехай X ( нескінченна підмножина потужності (, S(X) - напівгрупа всіх відображень X(X. О. Равський довів, що для будь-якого розбиття S(X)=((<( S( існує (<(, таке що S(X)=S( s для деякого елемента s(S(X). Отже, принаймні одна із підмножин розбиття є великою в кульовій структурі Br(S(x)). В [32] побудована зліченна напівгрупа, така що для довільного її скінченного розбиття принаймні одна із підмножин розбиття велика справа. Таким чином, зліченна напівгрупа S не є розкладною відносно сім'ї великих справа підмножин із S. Цей же приклад показує, що теорема 4.11 теж не поширюється на всі напівгрупи.

Похожие записи