Граф Келі

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

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

Визначення

Види графів за їхніми автоморфізмами
відстанево-транзитивний	$\leftarrow$	сильно регулярний
$\downarrow$
симетричний (дуго-транзитивний)	$\leftarrow$	t-транзитивний, t ≥ 2
$\downarrow$(якщо зв'язний)
Шаблон:Не перекладено	$\to$	реберно-транзитивний і регулярний	$\to$	реберно-транзитивний
$\downarrow$		$\downarrow$
вершинно-транзитивний	$\to$	регулярний
$\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