Граф Келі

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

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

Визначення

Види графів за їхніми автоморфізмами
відстанево-транзитивний	$\rightarrow$	відстанево-регулярний	$\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

• 

  Граф Келі вільного добутку $\Z_2*\Z_3$

• 

  Граф Келі прямого добутку $\Z_2\times\Z_3$

Див. також

• Гіперболічна група

Джерела

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