Граф Келі

Граф Келі — граф, який будується для групи зі скінченною системою породжувальних елементів. Названий на честь англійського математика Артура Келі.

Граф Келі вільної групи на двох генераторах a та b.

Визначення

Види графів за їхніми автоморфізмами
відстанево-транзитивний	$\leftarrow$	сильно регулярний
$\downarrow$
симетричний (дуго-транзитивний)	$\leftarrow$	t-транзитивний, t ≥ 2
$\downarrow$(якщо зв'язний)
вершинно- та реберно-транзитивний	$\rightarrow$	реберно-транзитивний і регулярний	$\rightarrow$	реберно-транзитивний
$\downarrow$		$\downarrow$
вершинно-транзитивний	$\rightarrow$	регулярний
$\uparrow$
граф Келі		кососиметричний		асиметричний

Нехай $G$ — деяка група і $S$ — система її породжувальних (генерувальних) елементів. Визначимо $T=S\cup S^{-1}.$

Тоді граф Келі для даної групи Γ = Γ(G, T) будується таким чином:

• Кожному елементу $g\in G$ відповідає одна вершина графу.
• Кожному елементу $t\in T$ відповідає певний колір c_t
• Для будь-яких $g\in G$ та $t\in T$ вершини g і gt з'єднуються орієнтованим ребром кольору c_t.

Приклади

• Графом Келі для нескінченної циклічної групи Z є нескінченний ланцюг.
• Графом Келі для скінченної циклічної групи Z_n є цикл з n вершинами.
• Графом Келі для прямого добутку двох груп є прямий добуток відповідних графів Келі.

• 
  Граф Келі вільної групи з двома твірними a і b
• 
  Граф Келі вільного добутку $\mathbb {Z} _{2}*\mathbb {Z} _{3}$
• 
  Граф Келі прямого добутку $\mathbb {Z} _{2}\times \mathbb {Z} _{3}$

Див. також

• Гіперболічна група
• Ґратка (геометрія)
• Граф Берлекемпа — ван Лінта — Зейделя

Джерела

• Громов М. Л. Гиперболические группы. 2002. — С.160