Đồ thị Turán

Đồ thị Turán  là một đồ thị nhiều phía đầy đủ tạo thành bằng cách chia  đỉnh thành  tập con, với kích thước gần nhau nhất có thể, và nối hai đỉnh bằng một cạnh nếu và chỉ nếu chúng thuộc hai tập con khác nhau. Cụ thể, nếu đặt  thì đồ thị Turán gồm  tập con chứa  đỉnh, và  tập con với  phần tử. Tức là, nó là một đồ thị  phía đầy đủ, với mỗi đỉnh có bậc  hoặc . Tổng số cạnh của  là

Đồ thị Turán là một đồ thị chính quy, nếu  chia hết cho .

Định lý Turán
Đồ thị Turán được đặt tên theo nhà toán học Hungary Pál Turán, người tạo ra chúng để chứng minh định lý Turán, một kết quả quan trọng trong lý thuyết đồ thị cực trị.

Bằng nguyên lý Dirichlet, mỗi tập chứa  đỉnh trong đồ thị Turán chứa hai đỉnh trong một tập con phân hoạch; vì thế, đồ thị Turán không chứa clique nào có kích thước . Theo định lý Turán, đồ thị Turan có số cạnh tối đa trong số tất cả những đồ thị  đỉnh mà không có clique .
Keevash và Sudakov chỉ ra rằng đồ thị Turán cũng là đồ thị bậc  không có clique  duy nhất mà trong đó mọi tập con chứa  đỉnh bao gồm ít nhất

cạnh, nếu  đủ gần với . Định lý Erdős–Stone mở rộng định lý Turán bằng giới hạn số cạnh của một đồ thị không chứa đồ thị con nào là đồ thị Turán. Bằng định lý này, những chặn tương tự trong lý thuyết đồ thị cực trị có thể được chứng minh cho bất kỳ đồ thị con nào, dựa trên sắc số của đồ thị con.

Trường hợp đặc biệt

Một số giá trị của tham số  của đồ thị Turán dẫn đến một số đồ thị nổi bật từng được nghiên cứu độc lập.

Đồ thị Turán  có thể được xây dựng bằng cách bỏ một cặp ghép hoàn hảo từ một đồ thị đầy đủ . Đồ thị này là -bộ khung của một cross-polytope  chiều; ví dụ, đồ thị  là một đồ thị của hình bát diện đều. Nếu  cặp đôi đến một buổi tiệc và mỗi người bắt tay với tất cả người khác trừ bạn trai hay bạn gái của người đó, thì đồ thị biểu diễn những cái bắt tay chính là đồ thị Turán ; vì thế nó còn được gọi là đồ thị tiệc cocktail.

Đồ thị Turán  là một đồ thị hai phía đầy đủ và là một đồ thị Moore nếu  chẵn. Nếu  là ước của , đồ thị Turán là đối xứng và chính quy mạnh, mặc dù một số tác giả xem đồ thị Turán là trường hợp tầm thường của tính chính quy mạnh và loại chúng khỏi định nghĩa của đồ thị chính quy mạnh.

Đồ thị Turán  có  clique cực đại, trong đó  và ; mỗi clique cực đại có thể tạo bằng cách chọn một đỉnh từ mỗi tập phân hoạch. Moon và Moser chứng minh rằng đây là số clique cực đại lớn nhất có thể trong tất cả đồ thị  đỉnh bất kể số cạnh; những đồ thị này còn được gọi là đồ thị Moon–Moser.

Tính chất khác
Mọi đồ thị Turán là một cograph; tức là nó có thể được xây dựng từ các đỉnh bằng một chuỗi các phép hợp rời nhau và phần bù. Cụ thể, ta có thể bắt đầu bằng cách xây dựng mỗi tập riêng biệt của đồ thị như là một hợp rời các đỉnh riêng biệt. Sau đó, đồ thị cần tạo là phần bù của hợp rời của phần bù các tập phân hoạch đó.

Chao và Novacky chứng minh rằng đồ thị Turán là duy nhất về mặt màu sắc: không đồ thị nào khác có cùng đa thức màu. Nikiforov dùng đồ thị Turán để cho ra một chặn dưới cho tổng của trị riêng thứ  của một đồ thị và phần bù của nó.

Một đồ thị  với  đỉnh là một đồ thị con của một đồ thị Turán  khi và chỉ khi  có một cách tô màu công bằng với  màu. Sự phân hoàn đồ thị Turán thành  tập khác nhau tương ứng với sự phân hoạch  theo màu. Cụ thể hơn, đồ thị Turán  là đồ thị  đỉnh cực đại duy nhất với một phép tô màu công bằng với  màu.

Tham khảo

Liên kết ngoài 
 
 
 

Lý thuyết đồ thị
Lý thuyết đồ thị cực trị
Họ đồ thị