| Головна » Статті » Математика | [ Додати статтю ] |
Розкладність графів. Комбінаторні розміри підмножин графів і груп - реферат українською
|
Застосуємо результати попереднього параграфу до кульових структур графів і груп. Теорема 1 Якщо множину вершин V довільно зв'язного графа Gr(V,E) розбито на скінченне число підмножин V=V1 V2Vn, то принаймні одна підмножина Vi розбиття має таку властивість: існує натуральне число m, таке що підмножина {xV: B(x,k) B(Vi,m)} непорожня для кожного натурального числа k. Доведення. Розглянемо кульову структуру B(Gr) і, виберемо кусково велику підмножину Vi розбиття. Якщо Gr(V,E) звязний граф скінченного діаметра, то кожна одноелементна підмножина {x}, xV велика в кульовій структурі B(Gr), еквівалентно, {x} має скінченний індекс. Отже, кожна підмножина довільного розбиття V на непорожні множини велика. Перше твердження наступної теореми показує, що це не можливо для графів нескінченного діаметра. Теорема 2. Для довільного звязного графа Gr(V,E) нескінченного діаметра справедливі такі твердження (і) множину V можна розбити на зліченне число малих підмножин; (іі) множину V можна розбити на зліченне число великих підмножин. Доведення. (і) Зафіксуємо довільну вершину xV і покладемо 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 і виберемо деяку вершину yB(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)= 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 L(Wi ) і {L(Wi ): i} диз'юнктна сім'я великих підмножин. Приклад 1. Для кожного нескінченного кардинала побудуємо зв'язний граф Gr(V,E) нескінченного діаметра, такий що множину вершин V не можна розбити на незліченне число великих підмножин. Візьмемо повний граф Gr'(V',E'), |V'|. Зафіксуємо довільний елемент xV' і візьмемо зліченну множину Y={yn: n}, таку що YV'=. Покладемо 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=V1V2, таке що підмножини V1, V2 не є великими. Доведення. Зафіксуємо довільний елемент x0V. Припустимо, що елементи x0, x1, …, xn вже вибрано так, що B(xi,i)B(xj,j)=, 0 i | |
| Переглядів: 460 | |
| Всього коментарів: 0 | |