Реферат на тему:
Розкладність графів. Комбінаторні розміри підмножин графів і груп
Застосуємо результати попереднього параграфу до кульових структур
графів і груп.
Теорема 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( i
(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=((
Нашли опечатку? Выделите и нажмите CTRL+Enter
