✨Đồ thị Cayley

right|thumb|Đồ thị Cayley của [[nhóm tự do trên hai phần tử sinh a và b]]

Trong toán học, đồ thị Cayley, hay còn gọi là đồ thị tô màu Cayley, biểu đồ Cayley, biểu đồ nhóm, hay nhóm màu là đồ thị mô tả cấu trúc trừu tượng của nhóm. Định nghĩa của nó được lấy từ định lý Cayley (được đặt tên theo nhà toán học Arthur Cayley), và sử dụng một tập các phần tử sinh của nhóm. Nó là một trong những công cụ quan trọng trong lý thuyết nhóm tổ hợp và lý thuyết nhóm hình học.

Định nghĩa

Gọi $G$ là nhóm và $S$ là tập sinh của $G$. Đồ thị Cayley $\backslash Gamma\; =\; \backslash Gamma(G,S)$ là đồ thị có hướng tô màu cạnh được xây dựng như sau:

• Mỗi phần tử $g$ thuộc $G$ được gán 1 đỉnh: tập đỉnh của $\backslash Gamma$ đồng nhất với $G.$
• Mỗi phần tử $s$ thuộc $S$ được gán màu $c\_s$.
• Với mọi $g\; \backslash in\; G$ và $s\; \backslash in\; S$, có cạnh có hướng có màu $c\_s$ từ đỉnh tương ứng với $g$ tới đỉnh tương ứng với $gs$.

Không phải mọi tác giả đều yêu cầu rằng $S$ phải sinh nhóm. Nếu $S$ không phải tập sinh của nhóm $G$, thì $\backslash Gamma$ là đồ thị không liên thông và mỗi thành phần liên thông biểu diễn lớp kề của nhóm con sinh bởi $S$.

Nếu phần tử $s$ thuộc $S$ là nghịch đảo của chính nó, tức $s\; =\; s^\{-1\},$ thì ta có thể biểu diễn nó bằng cạnh vô hướng.

Nếu tập $S$ được coi là tập đối xứng (tức là $S\; =\; S^\{-1\}$) và không chứa phần tử đơn vị của nhóm, thì đồ thị Cayley không tô màu của nó có thể biểu diễn bằng đồ thị vô hướng.

Trong lý thuyết nhóm hình học, tập $S$ thường mặc định là hữu hạn, tương ứng với $\backslash Gamma$ hữu hạn địa phương.

Các ví dụ

• Gọi $G=\backslash Z$ là nhóm cyclic vô hạn và tập $S$ chỉ chứa 1 và nghịch đảo của nó, −1 (trong ký hiệu phép cộng); thì đồ thị Cayley của nó có đường đi vô hạn.
• Tương tự, nếu $G=\backslash Z\_n$ là nhóm cyclic cấp $n$ và tập $S$ chỉ chứa hai phần tử là phần tử sinh $G$ và nghịch đảo của nó, thì đồ thị Cayley là đồ thị chu trình $C\_n$. Tổng quát hơn, đồ thị Cayley của nhóm cyclic hữu hạn cấp luôn là đồ thị đường tròn.
• Đồ thị Cayley của tích trực tiếp của nhóm (cùng với tích Descartes của các tập sinh làm tập sinh) là tích Descartes của các đồ thị Cayley tương ứng. Do đó, đồ thị Cayley của nhóm Abel $\backslash Z^2$ cùng tập các phần tử sinh $(\backslash pm\; 1,0),(0,\backslash pm\; 1)$ là lưới vô hạn trên mặt phẳng $\backslash R^2$, trong khi đó, tích trực tiếp của $\backslash Z\_n\; \backslash times\; \backslash Z\_m$ cùng với các phần tử sinh tương tự có đồ thị Cayley là lưới hữu hạn kích thước $n\backslash times\; m$ trên hình xuyến.

left|thumb|Đồ thị Cayley của nhóm nhị diện $D\_4$ trên hai phần tử sinh a và b right|thumb|Đồ thị Cayley của nhóm $D\_4$ trên hai phần tử sinh tự nghịch đảo

• Đồ thị Cayley của nhóm nhị diện $D\_4$ trên hai phần tử sinh $a$ và $b$ được biểu diễn trong ảnh bên. Các mũi tên màu đỏ biểu diễn phép hợp với $a$. Bởi $b$ tự nghịch đảo, nên các đường màu xanh của $b$ là các đường vô hướng. Do đó, đồ thị hỗn hợp giữa mũi tên và cạnh: nó có 8 đỉnh, 8 mũi tên và 4 cạnh. Bảng Cayley của nhóm $D\_4$ có thể dẫn xuất từ biểu diễn quan hệ của nhóm $$\backslash langle\; a,\; b\; \backslash mid\; a^4\; =\; b^2\; =\; e,\; a\; b\; =\; b\; a^3\; \backslash rangle.$$ Đồ thị Cayley khác của nhóm $D\_4$ được biểu diễn ở bên phải. Phần tử $b$ vẫn là phản xạ ngang và được tô bằng màu xanh, trong khi $c$ là phản xạ chéo và được tô bằng màu hồng. Bởi cả hai phản xạ này đều tự nghịch đảo nên đồ thị Cayley ở bên phải hoàn toàn vô hướng. Đồ thị này tương ứng với trình diễn sau $$\backslash langle\; b,\; c\; \backslash mid\; b^2\; =\; c^2\; =\; e,\; bcbc\; =\; cbcb\; \backslash rangle.$$
• Đồ thị Cayley của nhóm tự do trên hai phần tử sinh $a$ và $b$ tương ứng với tập $S\; =\; \{a,\; b,\; a^\{-1\},\; b^\{-1\}\}$ được biểu diễn ở ngay đầu bài viết, trong đó $e$ là phần tử đơn vị. Đi theo đường bên phải sẽ là phép nhân bên phải với $a,$ trong khi đi theo đường phía trên sẽ là phép nhân với $b.$ Bởi nhóm tự do không có quan hệ giữa các phần tử sinh nên đồ thị Cayley của nó không có chu trình. Đồ thị Cayley này là cây vô hạn 4-chính quy và là yếu tố quan trọng trong bài chứng minh nghịch lý Banach–Tarski.

thumb|right|Một phần của đồ thị Cayley cho nhóm Heisenberg.)

• Đồ thị Cayley của nhóm Heisenberg rời rạc nằm trong ảnh phải. Các phần tử sinh trong ảnh này là ba ma trận $X,\; Y,\; Z$ đưa bởi các hoán vị của 1, 0, 0 các mục $x,\; y,\; z$. Các phần tử sinh này thoả mãn quan hệ $Z\; =\; XYX^\{-1\}Y^\{-1\},\; XZ\; =\; ZX,\; YZ\; =\; ZY$. Nhóm này là nhóm vô hạn không giao hoán. thumb|link=|Đồ thị Cayley cho nhóm $Q\_8$ biểu diễn các chu trình phép nhân [[quaternion của , và ]]

Đặc trưng

Nhóm $G$ tự tác động lên chính nó bằng phép nhân trái (xem định lý Cayley). Ta có thể xem đây là tác động của $G$ trên đồ thị Cayley của nó. Nói rõ hơn, phần tử $h\backslash in\; G$ ánh xạ đỉnh $g\backslash in\; V(\backslash Gamma)$ sang đỉnh $hg\backslash in\; V(\backslash Gamma).$ Tập các cạnh và màu của đỉnh được bảo toàn bởi tác động này: cạnh $(g,gs)$ được ánh xạ sang cạnh $(hg,hgs)$, cả hai đều được tô màu $c\_s$. Tác động nhân trái của nhóm lên chính nó có tính bắc cầu đơn, và cụ thể hơn, đồ thị Cayley có tính bắc cầu đỉnh. Từ đây, ta có định lý gần như ngược lại như sau:

Để thu về nhóm $G$ và tập sinh $S$ từ đồ thị có hướng chưa dán nhãn $\backslash Gamma,$ chọn một đỉnh $v\_1\backslash in\; V(\backslash Gamma)$ và nhãn nó là phần tử đơn vị của nó. Sau đó dán nhãn mỗi phần tử $v$ thuộc $\backslash Gamma$ bằng phần tử phân biệt thuộc $G$ ánh xạ $v\_1$ sang $v.$ Tập sinh $S$ của $G$ tạo đồ thị Cayley $\backslash Gamma(G,S)$ là tập các đỉnh đích của $v\_1$.

Các tính chất cơ bản

• Đồ thị $\backslash Gamma(G,S)$ phụ thuộc vào việc chọn tập sinh $S$. Lấy ví dụ, nếu tập sinh $S$ có $k$ phần tử thì mỗi đỉnh của đồ thị Cayley sẽ có $k$ mũi tên đi vào và $k$ mũi tên đi ra. Trong trường hợp tập sinh $S$ đối xứng chứa $r$ phần tử thì đồ thị Cayley là đồ thị chính quy có hướng bậc $r.$
• Chu trình trong đồ thị Cayley biểu diễn mối quan hệ giữa các phần tử sinh trong tập $S.$ Trong xây dựng phức Cayley của nhóm, các chu trình này tương ứng với quan hệ "đổ đầy" bằng các đa giác. Nghĩa là bài toán xây đồ thị Cayley cho tập quan hệ cho trước $\backslash mathcal\{P\}$ tương đương với giải bài toán từ cho $\backslash mathcal\{P\}$.
• Nếu $\backslash rho${\text{reg(g)(x) = gx là biểu diễn chính quy trái cùng dạng ma trận $|G|\backslash times\; |G|$ được ký hiệu là $[\backslash rho${\text{reg(g)], thì ma trận kề $\backslash Gamma(G,S)$ là $A\; =\; \backslash sum${s\in S} [\rho{\text{reg(g)].
• Mọi ký tự nhóm $\backslash chi$ của nhóm $G$ cảm sinh vectơ riêng của ma trận kề của $\backslash Gamma(G,S)$. Khi $G$ là nhóm giao hoán, thì các giá trị riêng tương ứng là $$\backslash lambda$$\chi=\sum{s\in S}\chi(s), nằm dưới dạng $$\backslash sum\_\{s\backslash in\; S\}\; e^\{2\backslash pi\; ijs/|G|\}$$ cho các số nguyên $j\; =\; 0,1,\backslash dots,|G|-1.$

Đồ thị lớp ghép Schreier

Nếu thay vì đó ta lấy đỉnh là lớp ghép phải của nhóm con cố định $H,$ thì ta thu về được đồ thị có cấu trúc tương tự, được đặt tên là đồ thị lớp ghép Schreier. Đồ thị này là nền tảng cho liệt kê lớp ghép trong tiến trình Todd-Coxeter.

Liên hệ với lý thuyết nhóm

Các thông tin của nhóm có thể thu về được bằng cách nghiên cứu ma trận kề của đồ thị và áp dụng các định lý trong lý thuyết phổ đồ thị. Ngược lại, đối với các tập sinh đối xứng, lý thuyết phổ và lý thuyết biểu diễn của $\backslash Gamma(G,S)$ được gắn với nhau trực tiếp: xét $\backslash rho\_1,\backslash dots,\backslash rho\_k$ là tập các biểu diễn bất khả quy đầy đủ của $G,$ và $\backslash rho$i(S) = \sum{s \in S} \rho_i(s) cùng với các giá trị riêng $\backslash Lambda\_i(S)$. Khi đó tập các giá trị riêng của $\backslash Gamma(G,S)$ là $\backslash bigcup\_i\; \backslash Lambda\_i(S),$ trong đó $\backslash lambda$ là bội của $\backslash dim(\backslash rho\_i)$ cho mỗi lần $\backslash lambda$ là giá trị riêng của $\backslash rho\_i(S).$

Giống của nhóm là giống tối thiểu của các đồ thị Cayley của nhóm đó.

Lý thuyết nhóm hình học

Tính mở rộng

Khi $S\; =\; S^\{-1\}$, đồ thị Cayley $\backslash Gamma(G,S)$ là $|S|$-chính quy, nên các kỹ thuật phổ có thể được dùng được phân tích các tính chất mở rộng của đồ thị. Lấy cụ thể như nhóm giao hoán, các giá trị riêng của đồ thị Cayley dễ tính hơn so với trường hợp không giao hoán và được xác định bởi công thức $\backslash lambda$\chi = \sum{s\in S} \chi(s) trong đó giá trị riêng đứng đầu bằng với $|S|$, do đó ta có thể dùng bất đẳng thức Cheeger để chặn tỷ lệ mở rộng cạnh sử dụng khoảng cách phổ.

Lý thuyết biểu diễn có thể dùng để xây dựng các đồ thị giãn Cayley, dưới dạng tính chất Kazhdan (T). Mệnh đề sau được thoả mãn:

Lấy ví dụ, nhóm $G\; =\; \backslash mathrm\{SL\}\_3(\backslash Z)$ có tính chất (T) và được sinh bởi các ma trận sơ cấp là một trong những ví dụ cụ thể của đồ thị giãn.

Phân loại đồ thị nguyên

Đồ thị nguyên là đồ thị mà các giá trị riêng của nó đều là số nguyên. Mặc dù bài toán phân loại toàn bộ các đồ thị nguyên vẫn là bài toán mở, đồ thị Cayley của một số nhóm được biết luôn là đồ thị nguyên. Sử dụng các đặc trưng của phổ của các đồ thị Cayley, lưu ý rằng $\backslash Gamma(G,S)$ là đồ thị nguyên khi và chỉ khi các giá trị riêng của $\backslash rho(S)$ là số nguyên cho mọi biểu diễn $\backslash rho$ của $G$.

Nhóm đơn nguyên Cayley

Nhóm $G$ được gọi là nhóm đơn nguyên Cayley hay còn gọi là nhóm CIS nếu đồ thị Cayley liên thông $\backslash Gamma(G,S)$ là đồ thị nguyên khi tập sinh đối xứng $S$ là phần bù của một nhóm con của $G$. Một kết quả từ Ahmady, Bell, và Mohar đã chứng minh rằng tất cả các nhóm CIS đều đẳng cấu với $\backslash mathbb\{Z\}/p\backslash mathbb\{Z\},\; \backslash mathbb\{Z\}/p^2\backslash mathbb\{Z\}$, hoặc $\backslash mathbb\{Z\}\_2\; \backslash times\; \backslash mathbb\{Z\}\_2$ với $p$ là số nguyên tố. Lưu ý rằng tập $S$ phải sinh ra toàn bộ nhóm $G$ để cho đồ thị Cayley có tính liên thông. (Nếu $S$ không sinh $G$, đồ thị Cayley vẫn có thể nguyên, nhưng bù của $S$ không nhất thiết phải là nhóm con.)

Lấy ví dụ $G=\backslash mathbb\{Z\}/5\backslash mathbb\{Z\}$, các tập sinh đối xứng (xê xích đẳng cấu đồ thị) là $S\; =\; \{1,4\}$: $\backslash Gamma(G,S)$ là chu trình $5$ có các giá trị riêng $2,\; \backslash tfrac\{\backslash sqrt\{5\}-1\}\{2\},\backslash tfrac\{\backslash sqrt\{5\}-1\}\{2\},\backslash tfrac\{-\backslash sqrt\{5\}-1\}\{2\},\backslash tfrac\{-\backslash sqrt\{5\}-1\}\{2\}$ $S\; =\; \{1,2,3,4\}$: $\backslash Gamma(G,S)$ là đồ thị $K\_5$ cùng với các giá trị riêng $4,\; -1,-1,-1,-1$ Các nhóm con duy nhất của $\backslash mathbb\{Z\}/5\backslash mathbb\{Z\}$ là nhóm tầm thường và chính nhóm đó, và tập sinh đối xứng duy nhất của $S$ mà sinh ra đồ thị nguyên là bù của nhóm tầm thường. Do đó $\backslash mathbb\{Z\}/5\backslash mathbb\{Z\}$ là nhóm CIS.

Phân loại các nhóm CIS lợi dụng tính chất sau: các nhóm con và ảnh đồng cấu của nhóm CIS cũng là nhóm CIS.

Dàn Bethe