Đồ 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 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 formula_1 là nhóm và formula_2 là tập sinh của formula_1. Đồ thị Cayley formula_4 là đồ thị có hướng tô màu cạnh được xây dựng như sau:

- Mỗi phần tử formula_5 thuộc formula_1 được gán 1 đỉnh: tập đỉnh của formula_7 đồng nhất với formula_8
- Mỗi phần tử formula_9 thuộc formula_2 được gán màu formula_11.
- Với mọi formula_12 và formula_13, có cạnh có hướng có màu formula_11 từ đỉnh tương ứng với formula_5 tới đỉnh tương ứng với formula_16.

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

Nếu phần tử formula_9 thuộc formula_2 là nghịch đảo của chính nó, tức formula_24 thì ta có thể biểu diễn nó bằng cạnh vô hướng.

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

== Các ví dụ ==
- Gọi formula_29 là nhóm cyclic vô hạn và tập formula_2 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 formula_31 là nhóm cyclic cấp formula_32 và tập formula_2 chỉ chứa hai phần tử là phần tử sinh formula_1 và nghịch đảo của nó, thì đồ thị Cayley là đồ thị chu trình formula_35. 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 formula_36 cùng tập các phần tử sinh formula_37 là lưới vô hạn trên mặt phẳng formula_38, trong khi đó, tích trực tiếp của formula_39 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 formula_40 trên hình xuyến.

- Đồ thị Cayley của nhóm nhị diện formula_41 trên hai phần tử sinh formula_42 và formula_43 đượ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 formula_42. Bởi formula_43 tự nghịch đảo, nên các đường màu xanh của formula_43 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 formula_41 có thể dẫn xuất từ biểu diễn quan hệ của nhóm formula_48 Đồ thị Cayley khác của nhóm formula_41 được biểu diễn ở bên phải. Phần tử formula_43 vẫn là phản xạ ngang và được tô bằng màu xanh, trong khi formula_51 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 formula_52
- Đồ thị Cayley của nhóm tự do trên hai phần tử sinh formula_42 và formula_43 tương ứng với tập formula_55 được biểu diễn ở ngay đầu bài viết, trong đó formula_56 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 formula_57 trong khi đi theo đường phía trên sẽ là phép nhân với formula_58 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 formula_59 nằm trong ảnh phải. Các phần tử sinh trong ảnh này là ba ma trận formula_60 đưa bởi các hoán vị của 1, 0, 0 các mục formula_61. Các phần tử sinh này thoả mãn quan hệ formula_62. Nhóm này là nhóm vô hạn không giao hoán.
== Đặc trưng ==
Nhóm formula_1 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 formula_1 trên đồ thị Cayley của nó. Nói rõ hơn, phần tử formula_65 ánh xạ đỉnh formula_66 sang đỉnh formula_67 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 formula_68 được ánh xạ sang cạnh formula_69, cả hai đều được tô màu formula_11. 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 formula_1 và tập sinh formula_2 từ đồ thị có hướng chưa dán nhãn formula_73 chọn một đỉnh formula_74 và nhãn nó là phần tử đơn vị của nó. Sau đó dán nhãn mỗi phần tử formula_75 thuộc formula_7 bằng phần tử phân biệt thuộc formula_1 ánh xạ formula_78 sang formula_79 Tập sinh formula_2 của formula_1 tạo đồ thị Cayley formula_82 là tập các đỉnh đích của formula_78.

== Các tính chất cơ bản ==
- Đồ thị formula_82 phụ thuộc vào việc chọn tập sinh formula_2. Lấy ví dụ, nếu tập sinh formula_2 có formula_87 phần tử thì mỗi đỉnh của đồ thị Cayley sẽ có formula_87 mũi tên đi vào và formula_87 mũi tên đi ra. Trong trường hợp tập sinh formula_2 đối xứng chứa formula_91 phần tử thì đồ thị Cayley là đồ thị chính quy có hướng bậc formula_92
- 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 formula_93 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 formula_94 tương đương với giải bài toán từ cho formula_94.
- Nếu formula_96 là toàn cấu nhóm và ảnh của các phần tử thuộc tập sinh formula_97 sang formula_98 phân biệt với nhau, thì nó cảm sinh ra phủ các đồ thị formula_99 trong đó formula_100 Cụ thể hơn, nếu nhóm formula_1 có formula_87 phần tử sinh, tất cả đều có bậc khác 2, và tập formula_2 chỉ chứa các phần tử sinh này cùng nghịch đảo của chúng thì đồ thị Cayley formula_82 được phủ bởi cây có bậc formula_105 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ị.
- Nếu formula_106 là biểu diễn chính quy trái cùng dạng ma trận formula_107 được ký hiệu là formula_108, thì ma trận kề formula_82 là formula_110.
- Mọi ký tự nhóm formula_111 của nhóm formula_1 cảm sinh vectơ riêng của ma trận kề của formula_82. Khi formula_1 là nhóm giao hoán, thì các giá trị riêng tương ứng là formula_115 nằm dưới dạng formula_116 cho các số nguyên formula_117

== Đồ 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 formula_118 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 formula_82 được gắn với nhau trực tiếp: xét formula_120 là tập các biểu diễn bất khả quy đầy đủ của formula_121 và formula_122 cùng với các giá trị riêng formula_123. Khi đó tập các giá trị riêng của formula_82 là formula_125 trong đó formula_126 là bội của formula_127 cho mỗi lần formula_126 là giá trị riêng của formula_129

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

== Tính mở rộng ==
Khi formula_26, đồ thị Cayley formula_82 là formula_132-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 formula_133 trong đó giá trị riêng đứng đầu bằng với formula_132, 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 formula_135 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 formula_82 là đồ thị nguyên khi và chỉ khi các giá trị riêng của formula_137 là số nguyên cho mọi biểu diễn formula_138 của formula_1.

=== Nhóm đơn nguyên Cayley ===
Nhóm formula_1 đượ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 formula_82 là đồ thị nguyên khi tập sinh đối xứng formula_2 là phần bù của một nhóm con của formula_1. 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 formula_144, hoặc formula_145 với formula_146 là số nguyên tố. Lưu ý rằng tập formula_2 phải sinh ra toàn bộ nhóm formula_1 để cho đồ thị Cayley có tính liên thông. (Nếu formula_2 không sinh formula_1, đồ thị Cayley vẫn có thể nguyên, nhưng bù của formula_2 không nhất thiết phải là nhóm con.)

Lấy ví dụ formula_152, các tập sinh đối xứng (xê xích đẳng cấu đồ thị) là
- formula_153: formula_82 là chu trình formula_155 có các giá trị riêng formula_156
- formula_157: formula_82 là đồ thị formula_159 cùng với các giá trị riêng formula_160
Các nhóm con duy nhất của formula_161 là nhóm tầm thường và chính nhóm đó, và tập sinh đối xứng duy nhất của formula_2 mà sinh ra đồ thị nguyên là bù của nhóm tầm thường. Do đó formula_161 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.

== Lịch sử ==
Đồ 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. 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

== Xem thêm ==
- Đồ 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ố)

== Liên kết ngoài ==
- Cayley diagrams