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

Приклад 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)|.

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

pk0+qk1 ³ m,

qk0+pk1 ³ m.

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

px0+qx1 = m,

qx0+px1 = m.

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

Лема 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)|.

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

pk0+qkn-1+qk1 ³ m,

pk1+qk0+qk2 ³ m,

……………………..

pkn-2+qkn-3+qkn-1 ³ m,

pkn-1+qkn-2+qk 0 ³ m.

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

=.

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

x 0=x 1=…=xn-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 2, <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} і позначимо Xi=c -1(i), i Î{0,1,2,3}.За лемою 3.2, |Xi Ç V(0)|= |Xi Ç V(1)| для всіх i Î{0,1,2,3}. За лемою 3.1(іі), |Xi|= . Оскільки V(0)= (X0 Ç V(0))È (X1 Ç V(0))È (X2 Ç V(0))È (X3 Ç 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} і позначимо Xj= c -1 (j), j Î{0,1,2,3,4}. З леми 3.3 випливає

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

За лемою 3.1(іі), |Xj |=, 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) є калейдоскопічним.

Нехай g1,g2,g Î G , g1,g2 Î B(g,1) і c(g1)=c(g2). Переконаємося, що g1=g2. Виберемо x1,x2 Î X , y1,y2 Î Y так, що g1=x1y1, g2=x2y2.Оскільки c(g1)=x1 , c(g2)=x2 і c(g1)=c(g2), то x1=x2. Оскільки g1,g2 Î B(g,1) , то існують елементи z1,z2 Î X, такі що g1=z1g, g2=z2 g. Таким чином, x1y1=z1g, x1y2=z2g і z 1-1 x1 y1=z 2-1 x1 y2. Звідси випливає, що x 1-1 z2 z 1-1 x1 =y2y1-1. З умови (ііі) означення калейдоскопічної пари випливає, що x 1-1 z2 z 1-1 x1 =e. Отже,.z1=z2 і g1=g2.

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

Теорема 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) - Хеммінгова пара;

(іі) якщо g1,g2 Î G , x Î X і c(g1)=c(g2), то c(x g1)=c(x g2).

Доведення. (і)Þ(іі). Виберемо y1,y2 Î Y і a Î X так, що g1=ay1, g2=ay2. Далі виберемо z1,z2 Î Y і b1,b2 Î X так, щоб виконувались рівності xg1=b1z1, xg2=b2z2. Тоді z1=b1-1xay1, z2=b2-1xay2. Оскільки Y - підгрупа групи G, то b1-1xa Î Y , b2-1xa Î Y , b1-1b2 Î Y. З умови (ііі) означення калейдоскопічної пари випливає b1=b2. Отже, c(x g1)=c(x g2).

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

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

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

Приклад 3.7. Нехай G=<a>´<b>, <a>@ Z 5, <b>@ Z 5, S={e,a,a-1,b,b-1}. Покажемо, що Cay(G,S) - Хеммінговий граф. Покладемо H=<a3b>. Тоді H=<a3b, ab2 , a4b3, a2b4> і 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, a2,b2, a-2, b-2, ab, a-1b-1 , a-1b, ab-1}

і покладемо H=<a2b2, a-2, b2>. Безпосередня перевірка дає 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=S1 È S2 È…È Sr, таке що |Si|=r-1, i Î{1,2,…,r} i |Si-1 Ç Sj|=1 для всіх різних індексів i,j Î{1,2,…,r}. Для цього розіб'ємо множину S=A È B так, що B=A-1. Таке розбиття можливе, оскільки S не містить елементів порядку 2. Виберемо довільні елементи x1,x2,…,xr-1 Î A і покладемо S1={x1,x2,…,xr-1}. Віднесемо елементи x1-1,x2-1,…, xr-1-1 до майбутніх підмножин S2, S3,…, Sr.Виберемо довільні елементи y2, y3,…, yr-1 Î A\{x1,x2,…,xr-1}. Покладемо S2={x1-1,y2,y3,…,yr-1} і віднесемо елементи y2-1, y3-1,…, yr-1-1 до майбутніх підмножин S3, S4…, Sr. Виберемо довільні елементи

z3, z4, …, zr-1 Î A\{x1,x2,…, xr-1, y2, y3,…, yr-1 },

покладемо S3={x2-1,y2-1,z3,…,zr-1}, віднесемо елементи z3-1, z4-1, …, zr-1-1 до майбутніх підмножин S4, S5,…, Sr і т. д.

Крок 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 Î Si , s-1 Î Sj . Покладемо c(z)=i , c(t)=j.

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

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

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

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

(ii) якщо (x,y)Î E 1, то (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 1(V 1,E 1) - довільний калейдоскопічним граф степеня s з калейдоскопічним розфарбуванням c 1: V 1®{0,1,…,s}. Тоді існує калейдоскопічний гомоморфізм f: V®V 1.

Доведення. Зафіксуємо довільні вершини x Î V, y Î V 1 для яких c(x)=c 1(y) і покладемо f(x)=y. Для кожного невід'ємного цілого числа m позначимо S m (x)={z Î V: d(x,z)=m}. Припустимо, що відображення f вже визначене на множині S 0(x)È S 1(x)È …È Sm(x). Візьмемо довільну вершину z Î Sm+1(x) і виберемо вершину z'Î Sm(x) так, що d(z,z')=1. Далі виберемо вершину t Î B(f(z'),1), для якої c(z')=c 1(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 1 , w 1 Î KS(X) і v Î V, покладемо w(v)=x(w 1(v)). Зауважимо, що послідовність кольорів вершин на найкоротшому шляху від вершини v 1 Î V до вершини v2 Î V визначає слово w Î KS(X), таке що w(v 1)=v 2. Звідси випливає, що визначена дія транзитивна.

Для кожного 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=x1 x2…xn-1 xn, то позначимо через ũ слово xn xn-1 …x2 x1.

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

w1=x1 x2…xk-1 u, w2 =ũ xk+1 xk+2…xn , u ũ=xk .

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

Нагадаємо, що елемент 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=x1 x2…xk-1 u= ũ xk+1 …xn =x1 x2…xk xk+1 …xn ,

де x1 x2…xn - нескорочуваний запис слова w, u ũ=xk . Звідси випливає що

u= xk xk+1 …xn , ũ =x1 x2…xk

Отже, u= xk xk-1 …x1 і w=x1 .

Припустимо, що 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 x1 x2…xn x, n ³ 2, x ¹ xi, i Î{1,…,n} і серед сусідніх літер слова x1x2…xn немає однакових. Тоді

x x1 x2…xn-1 xn x=(x x1 x2 x)(x x2 x3 x)…(x xn-1 xn x).

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

w1 w2…wn-1 = x…abx.

Якщо c ¹ b, то

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}.

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

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

де j (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 j (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 існує розфарбування 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 кольорів.