Đồ 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:
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 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.
Đồ 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à
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