Đồ thị Cayley

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^[1] 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.

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

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

Không phải mọi tác giả đều yêu cầu rằng ${\displaystyle S}$ phải sinh nhóm. Nếu ${\displaystyle S}$ không phải tập sinh của nhóm ${\displaystyle G}$, thì ${\displaystyle \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 ${\displaystyle S}$.

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

Nếu tập ${\displaystyle S}$ được coi là tập đối xứng (tức là ${\displaystyle 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 ${\displaystyle S}$ thường mặc định là hữu hạn, tương ứng với ${\displaystyle \Gamma }$ hữu hạn địa phương.

• Gọi ${\displaystyle G=\mathbb {Z} }$ là nhóm cyclic vô hạn và tập ${\displaystyle 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 ${\displaystyle G=\mathbb {Z} _{n}}$ là nhóm cyclic cấp ${\displaystyle n}$ và tập ${\displaystyle S}$ chỉ chứa hai phần tử là phần tử sinh ${\displaystyle G}$ và nghịch đảo của nó, thì đồ thị Cayley là đồ thị chu trình ${\displaystyle 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.^[3] Do đó, đồ thị Cayley của nhóm Abel ${\displaystyle \mathbb {Z} ^{2}}$ cùng tập các phần tử sinh ${\displaystyle (\pm 1,0),(0,\pm 1)}$ là lưới vô hạn trên mặt phẳng ${\displaystyle \mathbb {R} ^{2}}$, trong khi đó, tích trực tiếp của ${\displaystyle \mathbb {Z} _{n}\times \mathbb {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 ${\displaystyle n\times m}$ trên hình xuyến.

• Đồ thị Cayley của nhóm nhị diện ${\displaystyle D_{4}}$ trên hai phần tử sinh ${\displaystyle a}$ và ${\displaystyle 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 ${\displaystyle a}$. Bởi ${\displaystyle b}$ tự nghịch đảo, nên các đường màu xanh của ${\displaystyle 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 ${\displaystyle D_{4}}$ có thể dẫn xuất từ biểu diễn quan hệ của nhóm $${\displaystyle \langle a,b\mid a^{4}=b^{2}=e,ab=ba^{3}\rangle .}$$ Đồ thị Cayley khác của nhóm ${\displaystyle D_{4}}$ được biểu diễn ở bên phải. Phần tử ${\displaystyle b}$ vẫn là phản xạ ngang và được tô bằng màu xanh, trong khi ${\displaystyle 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 $${\displaystyle \langle b,c\mid b^{2}=c^{2}=e,bcbc=cbcb\rangle .}$$
• Đồ thị Cayley của nhóm tự do trên hai phần tử sinh ${\displaystyle a}$ và ${\displaystyle b}$ tương ứng với tập ${\displaystyle S=\{a,b,a^{-1},b^{-1}\}}$ được biểu diễn ở ngay đầu bài viết, trong đó ${\displaystyle 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 ${\displaystyle a,}$ trong khi đi theo đường phía trên sẽ là phép nhân với ${\displaystyle 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.

• Đồ thị Cayley của nhóm Heisenberg rời rạc $${\displaystyle \left\{{\begin{pmatrix}1&x&z\\0&1&y\\0&0&1\\\end{pmatrix}},\ x,y,z\in \mathbb {Z} \right\}}$$ nằm trong ảnh phải. Các phần tử sinh trong ảnh này là ba ma trận ${\displaystyle X,Y,Z}$ đưa bởi các hoán vị của 1, 0, 0 các mục ${\displaystyle x,y,z}$. Các phần tử sinh này thoả mãn quan hệ ${\displaystyle Z=XYX^{-1}Y^{-1},XZ=ZX,YZ=ZY}$. Nhóm này là nhóm vô hạn không giao hoán.

Nhóm ${\displaystyle 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 ${\displaystyle G}$ trên đồ thị Cayley của nó. Nói rõ hơn, phần tử ${\displaystyle h\in G}$ ánh xạ đỉnh ${\displaystyle g\in V(\Gamma )}$ sang đỉnh ${\displaystyle hg\in V(\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 ${\displaystyle (g,gs)}$ được ánh xạ sang cạnh ${\displaystyle (hg,hgs)}$, cả hai đều được tô màu ${\displaystyle 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 ${\displaystyle G}$ và tập sinh ${\displaystyle S}$ từ đồ thị có hướng chưa dán nhãn ${\displaystyle \Gamma ,}$ chọn một đỉnh ${\displaystyle v_{1}\in V(\Gamma )}$ và nhãn nó là phần tử đơn vị của nó. Sau đó dán nhãn mỗi phần tử ${\displaystyle v}$ thuộc ${\displaystyle \Gamma }$ bằng phần tử phân biệt thuộc ${\displaystyle G}$ ánh xạ ${\displaystyle v_{1}}$ sang ${\displaystyle v.}$ Tập sinh ${\displaystyle S}$ của ${\displaystyle G}$ tạo đồ thị Cayley ${\displaystyle \Gamma (G,S)}$ là tập các đỉnh đích của ${\displaystyle v_{1}}$.

• Đồ thị ${\displaystyle \Gamma (G,S)}$ phụ thuộc vào việc chọn tập sinh ${\displaystyle S}$. Lấy ví dụ, nếu tập sinh ${\displaystyle S}$ có ${\displaystyle k}$ phần tử thì mỗi đỉnh của đồ thị Cayley sẽ có ${\displaystyle k}$ mũi tên đi vào và ${\displaystyle k}$ mũi tên đi ra. Trong trường hợp tập sinh ${\displaystyle S}$ đối xứng chứa ${\displaystyle r}$ phần tử thì đồ thị Cayley là đồ thị chính quy có hướng bậc ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle {\mathcal {P}}}$ tương đương với giải bài toán từ cho ${\displaystyle {\mathcal {P}}}$.^[1]
• Nếu ${\displaystyle f:G'\to G}$ là toàn cấu nhóm và ảnh của các phần tử thuộc tập sinh ${\displaystyle S'}$ sang ${\displaystyle G'}$ phân biệt với nhau, thì nó cảm sinh ra phủ các đồ thị $${\displaystyle {\bar {f}}:\Gamma (G',S')\to \Gamma (G,S),}$$ trong đó ${\displaystyle S=f(S').}$ Cụ thể hơn, nếu nhóm ${\displaystyle G}$ có ${\displaystyle k}$ phần tử sinh, tất cả đều có bậc khác 2, và tập ${\displaystyle S}$ chỉ chứa các phần tử sinh này cùng nghịch đảo của chúng thì đồ thị Cayley ${\displaystyle \Gamma (G,S)}$ được phủ bởi cây có bậc ${\displaystyle 2k}$ tương ứng với nhóm tự do được sinh bởi cùng tập sinh đó.
• Đối với bất kỳ đồ thị Cayley hữu hạn và vô hướng, giá trị liên thông đỉnh phải lớn hơn hoặc bằng 2/3 của bậc của đồ thị. Nếu tập sinh tối thiểu (tức là nếu bỏ đi bất kỳ phần tử nào trong tập hợp, và nghịch đảo của phần tử đó nếu có, thì tập đó sẽ không còn là tập sinh), thì giá trị liên thông đường sẽ bằng với bậc của đồ thị. Giá trị liên thông cạnh trong mọi trường hợp đều bằng với bậc của đồ thị.^[5]
• Nếu ${\displaystyle \rho _{\text{reg}}(g)(x)=gx}$ là biểu diễn chính quy trái cùng dạng ma trận ${\displaystyle |G|\times |G|}$ được ký hiệu là ${\displaystyle [\rho _{\text{reg}}(g)]}$, thì ma trận kề ${\displaystyle \Gamma (G,S)}$ là ${\textstyle A=\sum _{s\in S}[\rho _{\text{reg}}(g)]}$.
• Mọi ký tự nhóm ${\displaystyle \chi }$ của nhóm ${\displaystyle G}$ cảm sinh vectơ riêng của ma trận kề của ${\displaystyle \Gamma (G,S)}$. Khi ${\displaystyle G}$ là nhóm giao hoán, thì các giá trị riêng tương ứng là $${\displaystyle \lambda _{\chi }=\sum _{s\in S}\chi (s),}$$ nằm dưới dạng $${\displaystyle \sum _{s\in S}e^{2\pi ijs/|G|}}$$ cho các số nguyên ${\displaystyle j=0,1,\dots ,|G|-1.}$

Nếu thay vì đó ta lấy đỉnh là lớp ghép phải của nhóm con cố định ${\displaystyle 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.

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 ${\displaystyle \Gamma (G,S)}$ được gắn với nhau trực tiếp: xét ${\displaystyle \rho _{1},\dots ,\rho _{k}}$ là tập các biểu diễn bất khả quy đầy đủ của ${\displaystyle G,}$ và ${\textstyle \rho _{i}(S)=\sum _{s\in S}\rho _{i}(s)}$ cùng với các giá trị riêng ${\displaystyle \Lambda _{i}(S)}$. Khi đó tập các giá trị riêng của ${\displaystyle \Gamma (G,S)}$ là ${\textstyle \bigcup _{i}\Lambda _{i}(S),}$ trong đó ${\displaystyle \lambda }$ là bội của ${\displaystyle \dim(\rho _{i})}$ cho mỗi lần ${\displaystyle \lambda }$ là giá trị riêng của ${\displaystyle \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 đó.^[6]

Khi ${\displaystyle S=S^{-1}}$, đồ thị Cayley ${\displaystyle \Gamma (G,S)}$ là ${\displaystyle |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 ${\textstyle \lambda _{\chi }=\sum _{s\in S}\chi (s)}$ trong đó giá trị riêng đứng đầu bằng với ${\displaystyle |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:^[7]

Nếu nhóm rời rạc ${\displaystyle G}$ có tính chất Kazhdan (T), và ${\displaystyle S}$ là tập sinh hữu hạn và đối xứng của ${\displaystyle G}$, thì tồn tại hằng số ${\displaystyle c>0}$ chỉ dựa trên trên ${\displaystyle G,S}$ sao cho với bất kỳ thương hữu hạn ${\displaystyle Q}$của ${\displaystyle G}$ đồ thị Cayley ${\displaystyle Q}$ tương ứng với ảnh của ${\displaystyle S}$ là đồ thị giãn ${\displaystyle c}$.

Lấy ví dụ, nhóm ${\displaystyle G=\mathrm {SL} _{3}(\mathbb {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.

Đồ 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 ${\displaystyle \Gamma (G,S)}$ là đồ thị nguyên khi và chỉ khi các giá trị riêng của ${\displaystyle \rho (S)}$ là số nguyên cho mọi biểu diễn ${\displaystyle \rho }$ của ${\displaystyle G}$.

Nhóm ${\displaystyle 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 ${\displaystyle \Gamma (G,S)}$ là đồ thị nguyên khi tập sinh đối xứng ${\displaystyle S}$ là phần bù của một nhóm con của ${\displaystyle 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 ${\displaystyle \mathbb {Z} /p\mathbb {Z} ,\mathbb {Z} /p^{2}\mathbb {Z} }$, hoặc ${\displaystyle \mathbb {Z} _{2}\times \mathbb {Z} _{2}}$ với ${\displaystyle p}$ là số nguyên tố.^[8] Lưu ý rằng tập ${\displaystyle S}$ phải sinh ra toàn bộ nhóm ${\displaystyle G}$ để cho đồ thị Cayley có tính liên thông. (Nếu ${\displaystyle S}$ không sinh ${\displaystyle G}$, đồ thị Cayley vẫn có thể nguyên, nhưng bù của ${\displaystyle S}$ không nhất thiết phải là nhóm con.)

Lấy ví dụ ${\displaystyle G=\mathbb {Z} /5\mathbb {Z} }$, các tập sinh đối xứng (xê xích đẳng cấu đồ thị) là

• ${\displaystyle S=\{1,4\}}$: ${\displaystyle \Gamma (G,S)}$ là chu trình ${\displaystyle 5}$ có các giá trị riêng ${\displaystyle 2,{\tfrac {{\sqrt {5}}-1}{2}},{\tfrac {{\sqrt {5}}-1}{2}},{\tfrac {-{\sqrt {5}}-1}{2}},{\tfrac {-{\sqrt {5}}-1}{2}}}$
• ${\displaystyle S=\{1,2,3,4\}}$: ${\displaystyle \Gamma (G,S)}$ là đồ thị ${\displaystyle K_{5}}$ cùng với các giá trị riêng ${\displaystyle 4,-1,-1,-1,-1}$

Các nhóm con duy nhất của ${\displaystyle \mathbb {Z} /5\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 ${\displaystyle S}$ mà sinh ra đồ thị nguyên là bù của nhóm tầm thường. Do đó ${\displaystyle \mathbb {Z} /5\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.^[8]

Đồ thị Cayley được lần đầu nghiên cứu và sử dụng cho các nhóm hữu hạn bởi Arthur Cayley trong 1878.^[2] Max Dehn trong các bài giảng chưa xuất bản của ông cho lý thuyết nhóm từ năm 1909–10 đã giới thiệu lại đồ thị Cayley dưới tên Gruppenbild (biểu đồ nhóm), dẫn tới phát triển của lý thuyết nhóm hình học ngày nay. Ứng dụng quan trọng nhất của ông là lời giải của bài toán từ cho các nhóm cơ bản của các phẳng có giống ≥ 2^[9]

• Đồ thị bắc cầu đỉnh
• Tập sinh của nhóm
• Giả thuyết Lovász
• Lý thuyết đồ thị đại số
• Đồ thị chu trình (đại số)

• Cayley diagrams
• Weisstein, Eric W., "Cayley graph", MathWorld.