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

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

Теорема 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}, xV велика в кульовій структурі 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}, таку що 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 легко розбити на підмножин цього типу.