§2. Врівноважені розбиття нескінченних графів

Розглянемо довільний зв'язний граф Gr(V,E). За означенням, підмножина має скінченний індекс, якщо знайдеться таке невід'ємне ціле число , що , де для деякої вершини . Найменше невід'ємне ціле число , для якого справедлива ця рівність, називається індексом підмножини і позначається .

За означенням, розбиття множини вершин графа на скінченне число підмножин має скінченний індекс, якщо всі підмножини розбиття є підмножинами скінченного індексу. Найбільший з індексів підмножин розбиття називається індексом розбиття.

Почнемо з поширення на нескінченні графи теореми 1.1.

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

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

(*)

для всіх , , де - куля в графі радіуса з центром в вершині . Позначимо через множину усіх пар , для яких A, а розфарбування задовольняє умову (*). Введемо на множині частковий порядок за таким правилом: тоді і тільки тоді, коли і розфарбування є продовженням розфарбування . Зауважимо, що множина непорожня за теоремою 1.1. Очевидно, що кожен ланцюг в множині має верхню грань. За лемою Цорна, в множині існує максимальний елемент . Припустимо, що і виберемо вершину , суміжну з деякою вершиною . Оскільки , то для всіх . Виберемо максимальне число , для якого . Далі виберемо довільне число , таке що . Покладемо і для всіх . За побудовою, що суперечить максимальності . Отже, і - шукане розфарбування множини .

Зауважимо, що для можна вказати значно простіше доведення теореми. Дійсно, зафіксуємо довільну вершину і для кожної вершини покладемо , якщо число непарне, і якщо число парне.

Приклад 2.1. Розглянемо довільний метричний простір і припустимо, що для фіксованого додатного числа кожна куля містить деяку точку, відмінну від точки . Покажемо, що існує 2-розфарбування простору , для якого кожна куля радіуса містить різнокольорові точки. Для цього визначимо граф з множиною вершин і множиною ребер . Очевидно, що кожна зв'язна компонента цього графу містить принаймні дві точки. Якщо скінченна, застосуємо для її розфарбування теорему 1.1, якщо ж нескінченна - теорему 2.1.

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

Доведення. Спочатку припустимо, що кожна куля , скінченна. Тоді множина зліченна і можна взяти довільну бієкцію .

Припустимо, що деяка вершина є центром нескінченної кулі . Для кожного позначимо . Покладемо , . Покладемо і продовжимо на так, щоб . Далі, для кожної вершини покладемо . Таким чином визначене деяке розфарбування .

Візьмемо довільну вершину . Якщо , то , а множина нескінченна. Якщо , то

,

а множина нескінченна.

Зв'язний граф називається однорідним степеня , якщо локальний степінь кожної його вершини дорівнює . При цьому може бути як скінченним, так і нескінченним кардинальним числом.

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

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

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

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

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

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

Для того, щоб ввести поняття врівноваженого розбиття множини вершин нескінченного зв'язного графа дамо таке означення.

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

(і) ;

(іі) при ;

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

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

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

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

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

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

(і) ;

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

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

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

Упорядкуємо множину зелених вершин так: першою запишемо вершину , далі випишемо всі вершини першого поверху, слідом за ними всі вершини другого поверху і т. д.

До множини віднесемо корінь і всі вершини, що лежать на шляхах від кореня до жовтих вершин, що проходять через жовті вершини першого поверху. Зокрема, всі жовті вершини першого поверху заносяться до . Якщо у цей список попало вершин, то це і буде множина . Якщо ж ні, то приєднаємо до наступну за зелену вершину і всі жовті вершини, що лежать на шляхах від , що проходять через жовті вершини другого поверху і т. д. Після визначення множини беремо першу за списком зелену вершину, що не увійшла до , і повторюємо для неї цю ж процедуру.

Доведення теореми 2.4. Скористаємось розбиттям з леми 2.1 і покладемо . Очевидно, що - покриваюча послідовність. До кожного з графів , застосуємо теорему 1.2 і зафіксуємо врівноважене -розфарбування індексу . За лемою 1.5 ці розфарбування можна вибрати так, що є продовженням розфарбування c, . За візьмемо відображення , звуження якого на кожну з підмножин співпадає з . Ясно що розфарбування породжує -розбиття індексу , врівноважене відносно послідовності .

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

З доведення теореми 2.4 випливає, що для позитивної відповіді на це питання досить поширити лему 2.1 на довільні зліченні зв'язні графи. Проте цей шлях безперспективний. Дійсно, розглянемо дерево Gr(V,E) з множиною вершин і множиною ребер . Очевидно, що множина вершин цього дерева не допускає розбиттів, що задовольняють умови леми 2.1 при .

Проблема 2.2. Нехай Gr(V,E) - зліченний локально скінченний зв'язний граф, , - довільне натуральне число. Чи існує розбиття індексу множини V на підмножин, врівноважене відносно послідовності ? Ця ж проблема відкрита навіть для дерев.

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

існує орієнтовний шлях довжини від до },

існує орієнтовний шлях довжини від до },

В цих позначеннях враховується, що , для всіх , .

За означенням підмножина має скінченний індекс , (відповідно ), якщо знайдеться таке невід'ємне ціле число , що (відповідно ). Найменші невід'ємні цілі числа, для яких виконуються ці рівності, позначимо через A та відповідно.

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

Доведення. Для кожної вершини виберемо вершину , для якої існує ребро . Таким чином ми визначили відображення . Розглянемо неорієнтовний граф Gr_f(V,E_f) цього відображення з множиною неорієнтовних ребер . Легко помітити, що кожна зв'язна компонента Gr_f [S] цього графа може мати не більше одного циклу.

Припустимо, що Gr_f [S] не має жодного циклу. В цьому випадку Gr_f [S] - нескінченне дерево. Виберемо довільну вершину і назвемо її коренем. Пофарбуємо корінь зеленим кольором. Візьмемо довільну вершину . Якщо відстань від до непарна, пофарбуємо жовтим кольором, а якщо парна - зеленим. Позначимо через і підмножини всіх зелених та жовтих вершин відповідно. Ясно, що .

Нехай в графі Gr_f [S] є цикл . Якщо число n парне, пофарбуємо вершини циклу по черзі зеленим та жовтим кольорами. Для непарного числа n пофарбуємо вершини x₁, x₂ зеленим кольором, а вершини x₃, x₄ ,.., x_n по черзі - жовтим та зеленим кольорами. Візьмемо довільну вершину y, що не належить циклу. Виберемо вершину циклу x_i, найближчу за відстанню до вершини y. Якщо ця відстань парна, пофарбуємо y кольором вершини x_i, якщо непарна, то в інший з двох кольорів. Позначимо через S₁ та S₂ множини зелених та жовтих вершин. Якщо число n парне, то S₁=S₂=1. Якщо число n непарне, то S₁=1, S₂=2

Задача 2.3. Нехай S - напівгрупа, aÎS і ax¹x для всіх xÎS. Довести, що існує розбиття S=A₁ÈA₂, таке що

S=A₁È a^-1A₁, S=A₂È a^-1A₂È a^-2A₂,

де a^-1A_i ={xÎS : axÎA_i}, a^-2A_i={xÎS : a²xÎA_i}.

Теорема 2.6. Нехай Gr(V,E) - орієнтовний граф, з кожної вершини якого виходить принаймні одне орієнтовне ребро. Тоді існує розбиття множини вершин V=V₁È V₂, таке, що V₁=1,.V₂£ 2.

Доведення. Скористаємося схемою і позначеннями з доведення попередньої теореми. Якщо граф Gr_f [S] має кінцеві вершини, пофарбуємо їх зеленим кольором.

Припустимо, що Gr_f [S] не має циклів. Пофарбуємо корінь x цього дерева зеленим кольором. Візьмемо довільну непофарбовану вершину yÎS і обчислимо відстань d(x,y). Якщо число d(x,y) парне, пофарбуємо вершину y жовтим кольором, а інакше - зеленим. Очевидно, що S₁=1, S₂£2.

Припустимо, що граф Gr_f [S] має цикл x₁, x₂ ,.., x_n . Можна вважати, що x₂ =f(x₁), x₃=f(x₂),…, x_n=f(x_n-1), x₁ =f(x_n). Якщо число n парне, пофарбуємо вершини циклу по черзі зеленим та жовтим кольорами. Візьмемо довільну непофарбовану вершину y. Якщо відстань від y до найближчої вершини x_i циклу парна, пофарбуємо y кольором вершини x_i. Якщо ця відстань непарна, пофарбуємо вершину іншим з двох кольорів. Ясно, що S₁=1, S₂£2.

Для непарного числа n позначимо через T₁, T₂, …, T_n дерева з коренями x₁, x₂ ,.., x_n , одержані видаленням ребер циклу. Розглянемо два випадки.

Припустимо, що знайдеться вершина x_i циклу, для якої дерево T_i одноелементне. Змінюючи нумерацію, можна вважати, що i=1. Пофарбуємо вершини x₁, x₂ зеленим кольором, а вершини x₃, x₄ ,.., x_n пофарбуємо по черзі жовтим та зеленим кольорами. Далі продовжимо розфарбування на S як і у випадку парного числа n.

Залишилось розглянути випадок, коли всі дерева T₁, T₂, …, T_n не є одноелементними. Пофарбуємо вершини x₁, x₂ ,.., x_n жовтим кольором. Візьмемо довільну непофарбовану вершину z. Якщо відстань від z до найближчої вершини циклу парна, пофарбуємо z жовтим кольором, якщо непарна, то зеленим. Як в першому, так і в другому випадках S₁=1, S₂£ 2.

Задача 2.4. Нехай S - напівгрупа, aÎS і ax¹x для всіх xÎS. Довести, що існує розбиття S=A₁È A₂, таке що

S=A₁È aA₁, S=A₂È a^-1A₂ È a^-2A₂

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

Нехай X - довільна непорожня множина, Á - деяка сім'я її непорожніх підмножин. Підмножина AÍ X називається Á-щільною, якщо FÇ A¹Æ для будь-якої підмножини FÎÁ.

Для фіксованого кардинала n множина X називається n- розкладною відносно сім'ї Á, якщо X можна розбити на n Á-щільних підмножин. В хроматичній термінології множина X є n-розкладною відносно сім'ї Á, якщо X можна розфарбувати n кольорами так, що кожна підмножина FÎÁ містить точки усіх n кольорів. Кожна n-розкладна множина X є n¢-розкладною для всіх кардиналів n¢£ n. Супремум множини кардиналів n, для яких множина X є n-розкладною відносно сім'ї Á, називається показником розкладності X відносно сім'ї Á. Зрозуміло, що множина X 1-розкладна відносно будь-якої сім'ї Á. Замість терміна “2-розкладність”, як правило, вживають термін “розкладність”. Позначимо (Á)= inf {|F|:FÎÁ}. Очевидно, показник розкладності X відносно Á не перевищує (Á). Множина X називається максимально розкладною відносно сім'ї Á, якщо X є (Á) -розкладною відносно Á.

Для довільних графа Gr(V,E) і невід'ємного цілого числа r позначимо через g (Gr,r) показник розкладності множини вершин V відносно сім'ї усіх куль {B(x,r): xÎV} радіуса r.

В термінах розкладності теореми 1.1 і 2.1 стверджують, що g(Gr,r-1) ³ r для довільних натурального числа r і зв'язного графа Gr, що має принаймні r вершин. Приклад 1.3 показує, що існує скінченний зв'язний граф Gr з як завгодно великим наперед заданим локальним степенем вершин, для якого g (Gr,1)=2. Аналогічно інтерпретується і приклад 2.2. В задачах 2.1, 2.2 і теоремі 2.3 стверджується максимальна розкладність відповідних графів відносно сім'ї куль радіуса 1.