Розкладність графів. Калейдоскопічні графи, Детальна інформація

w1 w2…wn-1 wn= x…abxcdx

і це слово нескорочуване. Якщо b=c, то

w1 w2…wn-1 wn= x…acdx.

Оскільки b=c, то a(c. Отже, якщо a(d, то це слово нескорочуване. У випадку a=d маємо wn-1 = xdcx і wn= wn-1 -1, що суперечить припущенню про нескорочуваність w1 w2…wn-1 wn як групового слова в алфавіті W.

Для фіксованого елемента x(X, X={0,1,…,s} позначимо L(x)={yx: y(X}, R(x)={xy: y(X}.

Теорема 5. Калейдоскопічна напівгрупа KS(X) ізоморфна сендвіч-добутку L(x)(KG(X,x)(R(x), в якому множення визначене за правилом

(l1, g1, r1)(l2, g2, r2)=(l1, g1( (r1, l2) g2, r2),

де ( (r1, l2)=r1, l2 .

Доведення. Кожен елемент x1 x2…xn(KS(X) можна записати у вигляді

x1 x2…xn = x1 x ( x1 x2…xn) x xn= x1 x (x x1 x2…xnx) x xn .

Визначимо відображення f: KS(X) ( L(x)(KG(X,x)(R(x) за таким правилом

f (x1 x2…xn )=( x1 x, x x1 x2…xnx, x xn).

Для довільних елементів x1 x2…xn, y1 y2…ym (KS(X) маємо

f (x1 x2…xn ) f(y1 y2…ym)=( x1 x, x x1 x2…xnx, x xn).

(y1 x, x y1 y2…ym x, xym)=( x1 x, x x1 …xnx ( (x xn , y1 x) xy1 …ym x, xym)=

= f(x1 x2…xn y1 y2…ym ).

Отже, бієкція f є ізоморфізмом між KS(X) та L(x)(KG(X,x)(R(x).

Розглянемо довільний однорідний граф Gr(V,E) нескінченного степеня k. За теоремою 2.3 існує розфарбування (: V( k, таке що кожна куля одиничного радіуса містить точки усіх k кольорів. Це означає, що буквальне поширення означення калейдоскопічності з однорідних графів скінченного степеня на однорідні графи нескінченного степеня беззмістовне. Одне із можливих означень таке.

Однорідний граф Gr(V,E) нескінченного степеня k називається калейдоскопічним, якщо існує розфарбування (: V( k, таке що

(і) кожна одинична куля містить точки усіх k кольорів;

(іі) в кожній одиничній кулі немає двох однокольорових точок.

Задача 1. Вказати приклад однорідного графа зліченного степеня, що не є калейдоскопічним.

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

Проблема 1. Нехай X - нескінченна підмножина потужності k, ( - деяка сім'я її підмножин потужності k, |(|( k. Знайти умови, необхідні і достатні для існування розфарбування (: V( k, такого що кожна підмножина F( ( містить і тільки одну точку кожного з k кольорів.