Розкладність графів. Врівноважені розбиття нескінченних графів

Задача 1. Нехай - натуральне число, Gr(V,E) однорідне дерево степеня . Довести, що існує розфарбування , таке що кожна куля радіуса 1 містить точки усіх кольорів.

Теорема 3. Нехай - нескінченний кардинал, Gr(V,E) - однорідний граф степеня . Тоді існує таке розфарбування , що кожна куля радіуса 1 містить точки усіх кольорів.

Доведення. З однорідності Gr(V,E) випиває, що . Отже, існує перелік множини і для побудови можна застосувати стандартний діагональний процес.

У зв'язку з теоремою 3 виникає таке питання. Нехай - нескінченний кардинал, Gr(V,E) - зв'язний граф, причому для всіх . Чи можна розфарбувати множину вершин кольорами так, щоб кожна куля радіуса 1 містила точки усіх кольорів? Наступний приклад дає негативну відповідь на це питання. Більше того, він показує, що навіть 3-розфарбування з цією властивістю може не існувати.

Приклад 2. Нехай - нескінченний кардинал, - множина потужності , - сім'я усіх підмножин потужності множини . Розглянемо граф Gr(V,E) з множиною вершин і множиною ребер вигляду , де і . Зафіксуємо довільне 3-розфарбування . Оскільки множина нескінченна, то знайдеться однокольорова підмножина множини . Але тоді куля містить точки щонайбільше двох кольорів. Залишилось зауважити, що для всіх , а для всіх .

Задача 2. Нехай - нескінченний кардинал, Gr(V,E) - дерево і для всіх . Довести, що існує - розфарбування множини , таке що кожна куля радіуса 1 містить точки усіх кольорів.

Для того, щоб ввести поняття врівноваженого розбиття множини вершин нескінченного зв'язного графа дамо таке означення.Нехай Gr(V,E) - зліченний зв'язний граф. Послідовність скінченних підмножин множини назвемо покриваючою, якщо виконуються такі умови:

(і) ;

(іі) при ;

(ііі) кожен індукований підграф зв'язний.

Розбиття назвемо врівноваженим відносно покриваючої послідовності , якщо

Граф називається локально скінченним, якщо локальний степінь кожної його вершини скінченний. Нехай Gr(V,E) - зліченний локально скінченний граф, . Очевидно, що є покриваючою послідовністю, а тому покриваючою буде і будь-яка її підпослідовність.

Теорема 4. Для кожного зв'язного локально скінченного зліченного графа Gr(V,E) і кожного натурального числа існує розбиття індексу множини на підмножин, врівноважене відносно деякої покриваючої послідовності скінченних підмножин множини .

Для доведення теореми скористаємося такою лемою.

Лема 1. Нехай Gr(V,E) - зліченний зв'язний локально скінченний граф, - довільне натуральне число. Тоді існує розбиття множини вершин на скінченні підмножини , таке що для всіх

(і) ;

(іі) граф зв'язний;

(ііі) граф зв'язний.

Доведення. Не звужуючи загальності, можна вважати, що Gr(V,E) - дерево. Зафіксуємо довільну вершину і назвемо її коренем. Для кожного назвемо -им поверхом дерева множину усіх вершин, відстань від яких до кореня дорівнює . Оскільки дерево Gr(V,E) локально скінченне, то кожен його поверх скінченний. Розфарбуємо множину вершин V двома кольорами, зеленим і жовтим, за таким правилом. Вершина фарбується зеленим кольором тоді і тільки тоді, коли через неї проходить нескінченне число нескінченних шляхів, що виходять з кореня. Корінь теж фарбується зеленим кольором. Решта вершин дерева фарбується жовтим кольором. Ясно, що множина зелених вершин нескінченна, проте не виключено, що множина жовтих вершин виявилася порожньою.