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

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

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

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

Теорема 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 (VB (Sn (x), k), d+n+k).

Отже, V=B (VB (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 так, що жодне з підмножин VAi не є великою. Зокрема, існує розбиття 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 так, що кожна підмножина GAn не являється великою в кульовій структурі Bl (G). Це твердження узагальнюється так [28].

Нехай G (нескінченна група потужності (, (=cf (. Тоді існує розбиття G=((<(X (групи X, таке що G (F (GX () для кожного (<(і кожної підмножини F потужності <(. Зокрема, кожну групу G регулярної потужності (можна розбити на дві підмножини G=A1(A2 так, що G (FA1, G (FA2 для кожної підмножини F потужності <(. Невідомо [4], чи вірне це твердження для груп сингулярної потужності.

Задача 3. Довести що кожну нескінченну групу G потужності (можна розбити на (підмножин G=((<(G (так, що кожна підмножина GG (не є великою в кульовій структурі Bl (G).

Задача 4. Довести що підмножина S групи G мала в кульових структурах Bl (G) і Br (G) тоді і тільки тоді, коли підмножина GFSF велика в кульових структурах 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 теж не поширюється на всі напівгрупи.