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

e(Y, G=XY;

x-1XXx ( YY-1=e для всіх x(X.

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

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

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

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

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

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

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

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

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

(іі) якщо g1,g2 (G , x(X і ((g1)=((g2), то ((x g1)=((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. Отже, ((x g1)=((x g2).

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

Приклад 5. Нехай G=((…(, ( (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) - Хеммінговий граф.

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

Приклад 7. Нехай G=(, ( (5, ( (5, S={e,a,a-1,b,b-1}. Покажемо, що Cay(G,S) - Хеммінговий граф. Покладемо H=. Тоді H= і S-1S(H={e}, SH=G.

Приклад 8. Нехай G=(, ( (, ( (, 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=. Безпосередня перевірка дає SH=G, SS(H={e}.

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

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

Крок 1. Нехай G - група з одиницею e, S - скінченна підмножина групи, G=, 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
Крок 3. Визначимо розфарбування (: W(G({1,2,…,r} за таким правилом. Покладемо ((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 . Покладемо ((z)=i , ((t)=j.

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

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

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