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

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

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

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

{xB (x, k) Vi, m)}.

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

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

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

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

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

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

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

B (Sn (x), k), d+n+k)B (Sn (x), k), d+n+k).

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

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

B (x, b) b (x), 2b), B (x, a (n+1)+b)B (x, an+b))an+b (x), a).

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

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

V= V’E=E', y0)}n, 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= Ai так, що жодне з підмножин VAi не є великою. Зокрема, існує розбиття V=V1 таке що підмножини V1, V2 не є великими.

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

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

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

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

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

{xBl (x, K) (Ai, F)}.

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

GAi Ai-1f=F Ai Ai-1 .

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

Теорему 4. можна посилити в іншому напрямку [7]: якщо групу G розбито на n підмножин G=A1 то знайдуться такі підмножинa Ai розбиття, натуральне число kath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >22n-1−1 і підмножина K що G = FAiAi-1, |K| і (AiAi-1) $${}^{4^{k-1}}$$ ідгрупа групи G.

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

G=KAiAi-1, |K|.

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

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

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

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

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

Задача 3. Довести що кожну нескінченну групу 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 ескінченна підмножина потужності (X) — напівгрупа всіх відображень XО. Равський довів, що для будь-якого розбиття S (X)=<існуєтаке що S (X)=Sдля деякого елемента s). Отже, принаймні одна із підмножин розбиття є великою в кульовій структурі Br (S (x)). В [32] побудована зліченна напівгрупа, така що для довільного її скінченного розбиття принаймні одна із підмножин розбиття велика справа. Таким чином, зліченна напівгрупа S не є розкладною відносно сім'ї великих справа підмножин із S. Цей же приклад показує, що теорема 4.11 теж не поширюється на всі напівгрупи.