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

 Mỗi phần tử  thuộc  được gán 1 đỉnh: tập đỉnh của  đồng nhất với 
 Mỗi phần tử  thuộc  được gán màu .
 Với mọi  và , có cạnh có hướng có màu  từ đỉnh tương ứng với  tới đỉnh tương ứng với .

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

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

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

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

 Đồ thị Cayley của nhóm nhị diện  trên hai phần tử sinh  và  đượ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 . Bởi  tự nghịch đảo, nên các đường màu xanh của  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  có thể dẫn xuất từ biểu diễn quan hệ của nhóm  Đồ thị Cayley khác của nhóm  được biểu diễn ở bên phải. Phần tử  vẫn là phản xạ ngang và được tô bằng màu xanh, trong khi  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 
 Đồ thị Cayley của nhóm tự do trên hai phần tử sinh  và  tương ứng với tập  được biểu diễn ở ngay đầu bài viết, trong đó  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  trong khi đi theo đường phía trên sẽ là phép nhân với  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   nằm trong ảnh phải. Các phần tử sinh trong ảnh này là ba ma trận  đưa bởi các hoán vị của 1, 0, 0 các mục . Các phần tử sinh này thoả mãn quan hệ . Nhóm này là nhóm vô hạn không giao hoán.

Đặc trưng 
Nhóm  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  trên đồ thị Cayley của nó. Nói rõ hơn, phần tử  ánh xạ đỉnh  sang đỉnh  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  được ánh xạ sang cạnh , cả hai đều được tô màu . 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  và tập sinh  từ đồ thị có hướng chưa dán nhãn  chọn một đỉnh  và nhãn nó là phần tử đơn vị của nó. Sau đó dán nhãn mỗi phần tử  thuộc  bằng phần tử phân biệt thuộc  ánh xạ  sang  Tập sinh  của  tạo đồ thị Cayley  là tập các đỉnh đích của .

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

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

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

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 , đồ thị Cayley  là -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  trong đó giá trị riêng đứng đầu bằng với , 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  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  là đồ thị nguyên khi và chỉ khi các giá trị riêng của  là số nguyên cho mọi biểu diễn  của .

Nhóm đơn nguyên Cayley 

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

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

Nhóm nguyên Cayley

Tập sinh chuẩn tắc và tập sinh Euler

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

Dàn Bethe

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ố)

Tham khảo

Liên kết ngoài 
 Cayley diagrams
 

Lý thuyết nhóm
Nhóm hoán vị
Họ đồ thị
Lý thuyết nhóm hình học