WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Розкладність графів. Комбінаторні розміри підмножин графів і груп - Реферат

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


Реферат на тему:
Розкладність графів. Комбінаторні розміри підмножин графів і груп
Застосуємо результати попереднього параграфу до кульових структур графів і груп.
Теорема 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 iЗадача 1. Нехай Gr(V,E) скінченний орієнтовний граф. Для кожної вершини v V позначимо через St(v) множину усіх вершин x V, для яких існує орієнтовний шлях від v до x. Визначимо передпорядок на V за таким правилом: v1 v2 тоді і тільки тоді, коли St(v1) St(v2). Довести, що вершина v максимальна відносно тоді і тільки тоді, коли {v} кусково велика підмножина кульової структури (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. Цікаво було б довести це твердження елементарними методами.
Теорему 4. можна посилити в іншому напрямку [7]: якщо групу G розбито на n підмножин G=A1 A2 … An, то знайдуться такі підмножинa Ai розбиття, натуральне число k і підмножина K G, що G = FAiAi-1 , |K| k і (AiAi-1) підгрупа групи 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 теж не поширюється на всі напівгрупи.
Loading...

 
 

Цікаве