§3. Калейдоскопічні графи

Однорідний граф Gr(V,E) скінченного степеня s називається калейдоскопічним, якщо існує розфарбування c: V®{0,1,¼,s}, таке що |c(B(x,1))|=s+1 для будь-якого xÎV. В цьому разі розфарбування c теж називається калейдоскопічним. Отже, калейдоскопічні графи – це графи, що допускають калейдоскопічне розфарбування. Дамо рівносильне означення: розфарбування c: V®{0,1,¼,s} називається калейдоскопічним, якщо в кожній кулі одиничного радіуса немає двох однокольорових вершин.

З точки зору розкладності калейдоскопічні графи – це однорідні графи скінченого степеня, максимально розкладні відносно сім’ї всіх одиничних куль.

Розпочнемо дослідження калейдоскопічних графів з їх елементарних властивостей та прикладів. Далі запис a|b означає, що ціле число a є дільником цілого числа b.

Лема 3.1. Нехай Gr(V,E) – скінченний калейдоскопічний граф степеня s, c: V®{0,1,¼,s} – калейдоскопічне розфарбування. Тоді справедливі такі твердження:

(i) s+1/n;

(ii) |c^--1(0)|=|c^--1(1)|=…=|c^--1(s)|.

Доведення. Для кожного iÎ{0,1,¼,s} сім’я куль {B(x,1): xÎc^--1(i)} утворює розбиття множини вершин V. Оскільки |B(x,1)Çc^--1(i)|=1 , то

(s+1)|c^--1(i)|=|V|.

З цієї рівності випливають обидва твердження леми.

Приклад 3.1. Нехай Gr_n(V_n,E_n) – циклічний граф з n>2 вершинами. Припустимо що Gr_n(V_n,E_n) калейдоскопічний. Оскільки Gr_n – однорідний граф степеня 2, то 3|n за лемою 3.1(і). З іншого боку, якщо 3/n, то періодичне 3-розфарбування множини V_n є калейдоскопічним.

Приклад 3.2. Розглянемо п’ять правильних многогранників у просторі як скінченні графи і покажемо, що серед них калейдоскопічними є лише тетраедр, куб та ікосаедр. Очевидно, що кожне 4-розфарбування множини вершин тетраедра є калейдоскопічним. Зафіксуємо довільну вершину x куба і довільне 4-розфарбування кулі B(x,1). Далі, кожну вершину y' куба, симетричну до деякої вершини yÎB(x,1) відносно центра куба пофарбуємо кольором вершини y. Одержимо калейдоскопічне розфарбування куба. Аналогічне розфарбування виявляється калейдоскопічним і для ікосаедра. Оскільки октаедр має 6 вершин і є однорідним степеня 4, то він не є калейдоскопічним за лемою 3.1(і). Нарешті, додекаедр є однорідним графом степеня 3. Візьмемо довільний п’ятикутник, що є гранню додекаедра. Для будь-якого 4-розфарбування множини вершин додекаедра, знайдуться принаймні дві однокольорові точки на вказаній грані. Отже, одинична куля з центром в деякій вершині грані містить дві однокольорові вершини.

Лема 3.2. Нехай Gr(V,E) – скінчений однорідний граф степеня s, |V|=2m, XÍV. Припустимо, що існують розбиття V=V(0)ÈV(1), |V(0)|=|V(1)|=m і натуральні числа p, q, для яких виконуються такі умови:

(i) È{B(x,1): xÎX} =V;

(ii) (s+1)|X|=2m;

(iii) s+1=p+q, p>q;

(iv) якщо xÎV(i), iÎ{0,1}, то |B(x,1)ÇV(i)|=p, |B(x,1)Ç(V\V(i)|=q.

Тоді |XÇV(0)|=|XÇV(1)|.

Доведення. Позначимо k₀=|XÇV(0)|, k₁=|XÇV(1)|. З умов (і), (іv) випливають такі нерівності

pk₀+qk₁ ³ m,

qk₀+pk₁ ³ m.

Додамо ці нерівності і отримаємо p|X|+q|X| ³ 2m. З умов (іі), (ііі) випливає, що (p+q)|X|=2m. Отже, числа k₀, k₁ задовольняють систему лінійних рівнянь.

px₀+qx₁ = m,

qx₀+px₁ = m.

Оскільки p>q, ця система має єдиний розв’язок. З іншого боку, система має очевидний розв’язок x₀=x₁=.

Лема 3.3. Нехай Gr(V,E) – скінченний однорідний граф степеня s, |V|=nm, m, n – натуральні числа ³ 2, XÍV. Припустимо, що існують розбиття V=V(0)È V(1)È…È V(n-1), |V(0)|=|V(1)|=…=|V(n-1)|=m і натуральні числа p, q для яких виконуються умови:

(i) È {B(x,1): xÎX} =V;

(ii) (s+1)|X|=nm;

(iii) s+1=p+2q, p>2q;

(iv) якщо xÎV(i), iÎ{0,1,..,n-1}, то

B(x,1)Í V((i-1) mod n)È V(i mod n)È V((i+1) mod n),

|B(x,1)Ç V(i mod n)|=p,

|B(x,1)Ç V((i-1) mod n)|= |B(x,1)Ç V((i+1) mod n)|=q.

Тоді |XÇ V(0)|=|XÇ V(1)|=…=|XÇ V(n-1)|.

Доведення. Позначимо k_i=|XÇ V(i)|, iÎ{0,1,…,n-1}. З умов (і), (іv) випливають такі нерівності

pk₀+qk_n-1+qk₁³ m,

pk₁+qk₀+qk₂³ m,

……………………..

pk_n-2+qk_n-3+qk_n-1³ m,

pk_n-1+qk_n-2+qk₀³ m.

Додамо всі ці нерівності і отримаємо p|X|+2q|X|³ nm . З умов (іі), (ііі) випливає, що (p+2q)|X|=nm. Звідси випливає, що числа k₀, k₁,…, k_n-1 задовольняють систему лінійних рівнянь

=.

Помітимо, що визначник D матриці системи є циркулянтом. Отже D=f(e₀) f(e₁)…f(e_n-1), де e₀ , e₁,…, e_n-1 - комплексні корені рівняння zⁿ=1, f(x)=p+qx+qx^n-1. Оскільки p>2q, то f(e_i)¹ 0 для всіх iÎ{0,1,…,n-1}. Отже, ця система має єдиний розв’язок.. З іншого боку, система має очевидний розв’язок

x₀=x₁=…=x_n-1=.

Нагадаємо означення неорієнтованого графа Келі групи. Для довільної непорожньої підмножини А групи G позначимо через <A> найменшу підгрупу групи G, що містить A. Нехай G – група з одиницею e, SÍG, S=S^-1 і G=<S>. Графом Келі Cay(G,S) групи G, визначеним системою твірних S називається граф з множиною вершин G і множиною ребер E, де x,yÎE тоді і тільки тоді, коли x¹ y і x^-1yÎS. Якщо множина S скінченна eÎS і |S|-1=s, то Cay(G,S) - однорідний граф степеня s.

Приклад 3.3. Нехай

G=<a>´ <b>, <a>@ Z₂, <b>@ Z_m , m>2, S={a,b,b^-1,e}.

З геометричної точки зору граф Cay(G,S) є призмою з 2m вершинами. Припустимо, що граф Cay(G,S) калейдоскопічний і покажемо, що 4|m. Згодом (приклад 3.6) ми доведемо і обернене твердження.

Для того, щоб застосувати лему 3.2 покладемо s=3, p=3, q=1, V=G, <a>={0,1}, V(0)={(0,x): xÎ<b>}, V(1)={(1,x): xÎ<b>}. Зафіксуємо калейдоскопічне розфарбування c: V®{0,1,2,3} і позначимо X_i=c ^-1(i), iÎ{0,1,2,3}.За лемою 3.2, |X_iÇ V(0)|= |X_iÇ V(1)| для всіх iÎ{0,1,2,3}. За лемою 3.1(іі), |X_i|= . Оскільки V(0)= (X₀ Ç V(0))È (X₁Ç V(0))È (X₂Ç V(0))È (X₃Ç V(0)) , то 4|m.

Приклад 3.4. Нехай

G=<a>´ <b>, <a>@ Z_n, <b>@ Z_m , n, m>2, S={a, a^-1, b, b^-1,e}.

Припустимо, що граф Cay(G,S) калейдоскопічний і покажемо, що 5|m, 5|n.

Для того, щоб застосувати лему 3.3 покладемо

s=4, p=3, q=1, V=G, <a>={0,1,…,n-1}, V(i)={(i,x): xÎ<b>}, iÎ{0,1,…,n-1}. Зафіксуємо калейдоскопічне розфарбування c: V®{0,1,2,3,4} і позначимо X_j= c ^-1 (j), jÎ{0,1,2,3,4}. З леми 3.3 випливає

|X_j Ç V(0)|=|X_j Ç V(1)|=…=|X_j Ç V(n-1)|, jÎ{0,1,2,3,4}.

За лемою 3.1(іі), |X_j |=, jÎ{0,1,2,3,4}. Оскільки V(0)=, то 5|m. Аналогічно доводиться, що 6|n.

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

Розглянемо групу G з одиницею e. Нехай X, Y Í G. За означенням (X,Y) називається калейдоскопічною парою, якщо множина X скінченна і виконуються такі умови

(i) eÎX, X=X^-1, G=<X>;

(ii) eÎY, G=XY;

(iii) x^-1XXx Ç YY^-1=e для всіх xÎX.

З умов (іі), (ііі) випливає, що XX Ç YY^-1={e}. Враховуючи умову (іі), можна стверджувати, що кожен елемент gÎG однозначно розкладається у добуток g=xy, xÎX, yÎY.

Для калейдоскопічної пари (X,Y) визначимо стандартне розфарбування c: G®X за таким правилом. Для кожного xÎX покладемо c(x)=x. Візьмемо довільний елемент gÎG і виберемо xÎX, yÎY так, що g=xy. Покладемо c(g)=x. Переконаємось у тому, що стандартне розфарбування множини вершин графу Cay(G,X) є калейдоскопічним.

Нехай g₁,g₂,g ÎG , g₁,g₂Î B(g,1) і c(g₁)=c(g₂). Переконаємося, що g₁=g₂. Виберемо x₁,x₂ÎX , y₁,y₂ÎY так, що g₁=x₁y₁, g₂=x₂y₂.Оскільки c(g₁)=x₁ , c(g₂)=x₂ і c(g₁)=c(g₂), то x₁=x₂. Оскільки g₁,g₂Î B(g,1) , то існують елементи z₁,z₂ÎX, такі що g₁=z₁g, g₂=z₂ g. Таким чином, x₁y₁=z₁g, x₁y₂=z₂g і z₁^-1 x₁ y₁=z₂^-1 x₁ y₂. Звідси випливає, що x₁^-1 z₂ z₁^-1 x₁ =y₂y₁^-1. З умови (ііі) означення калейдоскопічної пари випливає, що x₁^-1 z₂ z₁^-1 x₁ =e. Отже,.z₁=z₂ і g₁=g_2.

Таким чином, ми довели таке твердження.

Теорема 3.1. Якщо (X,Y) - калейдоскопічна пара в групі G, то Cay(G,X) - калейдоскопічний граф.

Калейдоскопічна пара (X,Y) називається Хеммінговою парою, якщо Y - підгрупа групи G. В цьому випадку граф Cay(G,X) називається Хеммінговим графом.

Це означення обґрунтовується в прикладі 3.5.

Теорема 3.2. Нехай (X,Y) - калейдоскопічна пара в групі G, c - стандартне розфарбування групи G. Тоді такі два твердження рівносильні

(і) (X,Y) - Хеммінгова пара;

(іі) якщо g₁,g₂ ÎG , xÎX і c(g₁)=c(g₂), то c(x g₁)=c(x g₂).

Доведення. (і)Þ(іі). Виберемо y₁,y₂ÎY і aÎX так, що g₁=ay₁, g₂=ay₂. Далі виберемо z₁,z₂ÎY і b₁,b₂ÎX так, щоб виконувались рівності xg₁=b₁z₁, xg₂=b₂z₂. Тоді z₁=b₁^-1xay₁, z₂=b₂^-1xay₂. Оскільки Y - підгрупа групи G, то b₁^-1xa ÎY , b₂^-1xa ÎY , b₁^-1b₂ÎY. З умови (ііі) означення калейдоскопічної пари випливає b₁=b₂. Отже, c(x g₁)=c(x g₂).

(іі)Þ(і). Нехай y₁,y₂ÎY . Тоді c(y₁)=c(y₂)=c(e)=e. З умови (іі) випливає, що c (y₁y₂)=c (y₁e)=e, c (y₁^-1y₁)=c (e)=c (y₁^-1e)=c (y₁^-1). Отже, y₁y₂ÎY , y₁^-1ÎY .

Приклад 3.5. Нехай G=<a₁>´<a₂>´…´<a_n>, <a_i>@ Z₂, iÎ{1,…,n}, S={e, x₁,a₂,…,a_n}. Припустимо, що куб Cay(G,S) є калейдоскопічним графом. За лемою 3.1(і), n+1|2ⁿ . З іншого боку, якщо n+1|2ⁿ , то існує підгрупа H групи G, така що сім'я {Sh: hÎH} є розбиттям групи G [2, §8.7]. Ця підгрупа H називається кодом Хеммінга. Очевидно, що (S,H)- Хеммінгова пара, а отже, Cay(G,S) - Хеммінговий граф.

Приклад 3.6. Нехай G=<a>´<b>, <a>@ Z₂, <b>@ Z_m, m>2. Припустимо, що 4|m і покажемо, що Cay(G,S) є Хеммінговим графом, де S={e, a, b, b^-1}. Покладемо H=<ab²>. Тоді H=<b⁴>È{a^kb^2k: kÎ{1,3,…,m-1}}. Значить, (S,H) - Хеммінгова пара.

Приклад 3.7. Нехай G=<a>´<b>, <a>@ Z₅, <b>@ Z₅, S={e,a,a^-1,b,b^-1}. Покажемо, що Cay(G,S) - Хеммінговий граф. Покладемо H=<a³b>. Тоді H=<a³b, ab² , a⁴b³, a²b⁴> і S^-1SÇH={e}, SH=G.

Приклад 3.8. Нехай G=<a>´<b>, <a>@ Z, <b>@ Z, S={e,a,a^-1,b,b^-1}. Покажемо, що Cay(G,S) - Хеммінговий граф. Помітимо, що

SS={e,a,a^-1,b,b^-1, a²,b², a^-2, b^-2, ab, a^-1b^-1 , a^-1b, ab^-1}

і покладемо H=<a²b², a^-2, b²>. Безпосередня перевірка дає SH=G, SSÇH={e}.

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

Викладемо другий метод побудови калейдоскопічних графів на основі графів Келі Cay(G,S) груп при деяких обмеженнях на множину твірних S.

Крок 1. Нехай G - група з одиницею e, S - скінченна підмножина групи, G=<S>, eÏS, S=S^-1. Припустимо також, що |S|=r(r-1) для деякого натурального числа r>1 і S не містить елементів порядку 2. Побудуємо розбиття S=S₁ÈS₂È…ÈS_r, таке що |S_i|=r-1, iÎ{1,2,…,r} i |S_i^-1 Ç S_j|=1 для всіх різних індексів i,jÎ{1,2,…,r}. Для цього розіб'ємо множину S=AÈ B так, що B=A^-1. Таке розбиття можливе, оскільки S не містить елементів порядку 2. Виберемо довільні елементи x₁,x₂,…,x_r-1ÎA і покладемо S₁={x₁,x₂,…,x_r-1}. Віднесемо елементи x₁^-1,x₂^-1,…, x_r-1^-1 до майбутніх підмножин S₂, S₃,…, S_r.Виберемо довільні елементи y₂, y₃,…, y_r-1 ÎA\{x₁,x₂,…,x_r-1}. Покладемо S₂={x₁^-1,y₂,y₃,…,y_r-1} і віднесемо елементи y₂^-1, y₃^-1,…, y_r-1^-1 до майбутніх підмножин S₃, S₄…, S_r. Виберемо довільні елементи

z₃, z₄, …, z_r-1 ÎA\{x₁,x₂,…, x_r-1, y₂, y₃,…, y_r-1 },

покладемо S₃={x₂^-1,y₂^-1,z₃,…,z_r-1}, віднесемо елементи z₃^-1, z₄^-1, …, z_r-1^-1 до майбутніх підмножин S₄, S₅,…, S_r і т. д.

Крок 2. Впорядкуємо групу G лінійно і ототожнимо кожне ребро графа Келі Cay(G,S) з парою (x,y), x<y. Позначимо через N потужність множини ребер графа Cay(G,S) . Візьмемо довільну множину W потужності 2N, WÇG=Æ і побудуємо допоміжний граф Gr(GÈ W, E). Для кожного ребра (x,y) графа Cay(G,S) виберемо різні елементи z,tÎW і замінимо ребро (x,y) на шлях x,z,t,y. Занесемо ребра (x,zy), (z,t), (t,y) до E. При цьому, якщо (x,y) і (x¢,y¢) різні ребра графа Cay(G,S) і (x,y), (x¢,y¢) замінимо шляхами x,z,t,y і x¢,z¢,t¢,y¢ то {z,t}Ç{z¢,t¢}=Æ.

Крок 3. Визначимо розфарбування c: WÈG®{1,2,…,r} за таким правилом. Покладемо c(g)=0 для всіх gÎG. Нехай x,yÎG і ребро (x,y) графа Cay(G,S) замінено на шлях x,z,t,y. Тоді x^-1y=s, sÎG . Виберемо i,jÎ{1,2,…,r} так, що sÎS_i , s^-1ÎS_j . Покладемо c(z)=i , c(t)=j.

Крок 4. Для кожного xÎG і кожного iÎ{1,2,…,r} існує рівно r-1 вершин z₁, z₂, …, z_r-1 ÎW, для яких (x,z₁), (x,z₂), …, (x,z_r-1)ÎE і c(z₁)=c(z₂)= …=c(z_r-1)=i. Склеїмо ці вершини в одну вершину, а ребра (x,z₁), (x,z₂), …, (x,z_r-1) - в одне ребро. Після такої факторизації ми отримаємо калейдоскопічний граф.

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

Нехай Gr₁(V₁,E₁), Gr₂(V₂,E₂) - калейдоскопічні графи степеня s>1, c₁: V₁®{0,1,…,s}, c₂: V₂®{0,1,…,s}- їх калейдоскопічні розфарбування. Відображення f множини V₁ на множину V₂ називається калейдоскопічним гомоморфізмом, якщо

(i) c₁ (x) = c₂ (f(x)) для всіх xÎV₁;

(ii) якщо (x,y)ÎE₁, то (f(x), f(y))ÎE_2.

Однорідне дерево Tr(V,E) степеня s з визначеним калейдоскопічним розфарбуванням c: V®{0,1,…,s} множини його вершин називається вільним калейдоскопічним деревом степеня s.

Теорема 3.3. Нехай Tr(V,E) - вільне калейдоскопічне дерево степеня s з калейдоскопічним розфарбуванням c: V®{0,1,…,s}, Gr₁(V₁,E₁) - довільний калейдоскопічним граф степеня s з калейдоскопічним розфарбуванням c₁: V₁®{0,1,…,s}. Тоді існує калейдоскопічний гомоморфізм f: V®V₁.

Доведення. Зафіксуємо довільні вершини x ÎV, yÎV₁ для яких c(x)=c₁(y) і покладемо f(x)=y. Для кожного невід'ємного цілого числа m позначимо S_m (x)={zÎV: d(x,z)=m}. Припустимо, що відображення f вже визначене на множині S₀(x)È S₁(x)È …È S_m(x). Візьмемо довільну вершину zÎS_m+1(x) і виберемо вершину z'ÎS_m(x) так, що d(z,z')=1. Далі виберемо вершину tÎB(f(z'),1), для якої c(z')=c₁(t). Покладемо f(z)=t. За побудовою f - калейдоскопічний гомоморфізм.

Нехай s - натуральне число >1, X={0,1,…,s}. Калейдоскопічна напівгрупа KS(X) в алфавіті X - це напівгрупа, визначена співвідношеннями xx=x, xyx=x для всіх x,yÎX. Напівгрупу KS(X) зручно розглядати як множину усіх непорожніх слів в алфавіті X без факторів xx, xyx для всіх x,yÎX.

Покажемо, що напівгрупа KS(X) діє транзитивно на множині вершин кожного калейдоскопічного графа Gr(V,E) степеня s з калейдоскопічним розфарбуванням c: V®{0,1,…,s}. Візьмемо довільні xÎX, vÎV . Виберемо вершину uÎB(v,1), для якої c(u)=x, і покладемо x(v)=u. Далі продовжимо індуктивно дію з множини X на KS(X) за таким правилом. Якщо wÎKS(X), w=xw₁ , w₁ÎKS(X) і vÎV, покладемо w(v)=x(w₁(v)). Зауважимо, що послідовність кольорів вершин на найкоротшому шляху від вершини v₁ÎV до вершини v₂ÎV визначає слово wÎKS(X), таке що w(v₁)=v₂. Звідси випливає, що визначена дія транзитивна.

Для кожного xÎX підмножина KG(X,x) усіх слів з KS(X), що начинаються і закінчуються літерою x, є підгрупою напівгрупи KS(X) з одиницею x. Для того щоб одержати обернений елемент до слова wÎKG(X,x) досить записати це слово у зворотному порядку. Назвемо KG(X,x) калейдоскопічною групою.

Для дослідження структури калейдоскопічних груп та напівгруп введемо допоміжні позначення.

Для нескорочуваного слова uÎKS(X) позначимо через l (u) та r (u) першу та останню літери слова u. Якщо u=x₁ x₂…x_n-1 x_n, то позначимо через ũ слово x_n x_n-1 …x₂ x₁.

Лема 3.4. Нехай w₁ w₂ÎKS(X), l (w₂) =r (w₁), w=w₁ w₂ і x₁ x₂…x_n-1 x_n - нескорочуваний запис слова w. Тоді знайдуться такі слово uÎKS(X) і число k, що

w₁=x₁ x₂…x_k-1 u, w₂ =ũ x_k+1 x_k+2…x_n , u ũ=x_k .

Доведення. Оскільки l (w₂) =r (w₁), то w₁ =w₁^' x, w₂ =x w₂^' для деякої літери xÎX. Якщо r (w₁^' ) ¹l (w₂^' ) то покладемо u=x. Якщо r (w₁^' ) =l (w₂^' ), то w₁^' = w₁^'' y, w₂^'= y w₂^'' для деякої літери yÎX. Застосуємо скорочення yxy=y і замінимо слова w_{1 ,} w₂ словами w₁^' _, w₂^' . Оскільки ці слова нескорочувані, то можна застосувати до них індуктивні міркування.

Нагадаємо, що елемент s напівгрупи S називається ідемпотентом, якщо ss=s.

Лема 3.5. Ідемоптентами напівгрупи KS(X) є всі слова x, xy, де x, yÎX, x¹y, і тільки вони.

Доведення. Очевидно, що всі слова x, xy є ідемпотентами. Нехай w - довільний ідемпотент напівгрупи KS(X). Припустимо, що l (w)=r (w). За лемою 3.4

w=x₁ x₂…x_k-1 u= ũ x_k+1 …x_n =x₁ x₂…x_k x_k+1 …x_{n ,}

де x₁ x₂…x_n - нескорочуваний запис слова w, u ũ=x_k . Звідси випливає що

u= x_k x_k+1 …x_n , ũ =x₁ x₂…x_k

Отже, u= x_k x_k-1 …x₁ і w=x₁ .

Припустимо, що l (w)¹r (w). Нехай l (w)=x, w'=wx. Тоді

w'w'=wxwx=wwx=wx=w'.

Отже, w' - ідемпотент і l (w')=r (w'). За доведеним вище w'=x. Значить, w=xy для деякого yÎX.

Теорема 3.4. Група KG(X,x) є вільною групою з множиною вільних твірних

W={xyzx: y,zÎX, x¹ y, x¹ z, y¹ z}.

Доведення. Нагадаємо, що одиницею групи KG(X,x) є x. Спочатку покажемо, що кожен неодиничний елемент g групи KG(X,x) можна записати у вигляді добутку елементів із W. Зауважимо, що W=W^-1. Очевидно, що нескорочуваний запис елемента g факторизується на співмножники x x₁ x₂…x_n x, n³2, x¹ x_i, iÎ{1,…,n} і серед сусідніх літер слова x₁x₂…x_n немає однакових. Тоді

x x₁ x₂…x_n-1 x_n x=(x x₁ x₂ x)(x x₂ x₃ x)…(x x_n-1 x_n x).

Візьмемо довільне нескорочуване групове слово w₁ w₂…w_n , n³1 в алфавіті і покажемо, що w₁ w₂…w_n ¹ x. Для цього індукцією по числу n покажемо, що останні три літери в нескорочуваному записі слова w₁ w₂…w_n як елемента напівгрупи KS(X) співпадають з останніми трьома літерами слова w_n. Нехай w_n-1=xabx, w_n=xcdx. За припущенням індукції

w₁ w₂…w_n-1 = x…abx.

Якщо c ¹ b, то

w₁ w₂…w_n-1 w_n= x…abxcdx

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

w₁ w₂…w_n-1 w_n= x…acdx.

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

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

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

(l₁, g₁, r₁)(l₂, g₂, r₂)=(l₁, g₁j (r₁, l₂) g₂, r₂),

де j (r₁, l₂)=r₁, l₂ .

Доведення. Кожен елемент x₁ x₂…x_nÎKS(X) можна записати у вигляді

x₁ x₂…x_n = x₁ x ( x₁ x₂…x_n) x x_n= x₁ x (x x₁ x₂…x_nx) x x_n .

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

f (x₁ x₂…x_n )=( x₁ x, x x₁ x₂…x_nx, x x_n).

Для довільних елементів x₁ x₂…x_n, y₁ y₂…y_m ÎKS(X) маємо

f (x₁ x₂…x_n ) f(y₁ y₂…y_m)=( x₁ x, x x₁ x₂…x_nx, x x_n).

(y₁ x, x y₁ y₂…y_m x, xy_m)=( x₁ x, x x₁ …x_nx j (x x_n , y₁ x) xy₁ …y_m x, xy_m)=

= f(x₁ x₂…x_n y₁ y₂…y_m ).

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

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

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

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

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

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

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

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