Đồ thị Turán
Bản mẫu:Infobox graph Đồ thị Turán Bản mẫu:Math là một đồ thị nhiều phía đầy đủ tạo thành bằng cách chia Bản mẫu:Mvar đỉnh thành Bản mẫu:Mvar 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 Bản mẫu:Math thì đồ thị Turán gồm Bản mẫu:Mvar tập con chứa Bản mẫu:Math đỉnh, và Bản mẫu:Math tập con với Bản mẫu:Math phần tử.[1] Tức là, nó là một đồ thị Bản mẫu:Mvar phía đầy đủ, với mỗi đỉnh có bậc Bản mẫu:Math hoặc Bản mẫu:Math. Tổng số cạnh của Bản mẫu:Math là
Đồ thị Turán là một đồ thị chính quy, nếu Bản mẫu:Mvar chia hết cho Bản mẫu:Mvar.
Đị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ị.[2]
Bằng nguyên lý Dirichlet, mỗi tập chứa Bản mẫu:Math đỉ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 Bản mẫu:Math. Theo định lý Turán, đồ thị Turan có số cạnh tối đa trong số tất cả những đồ thị Bản mẫu:Mvar đỉnh mà không có clique Bản mẫu:Math. Keevash và Sudakov chỉ ra rằng đồ thị Turán cũng là đồ thị bậc Bản mẫu:Mvar không có clique Bản mẫu:Math duy nhất mà trong đó mọi tập con chứa Bản mẫu:Math đỉnh bao gồm ít nhất
cạnh, nếu Bản mẫu:Math đủ gần với Bản mẫu:Math.[3] Đị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ố Bản mẫu:Mvar 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 Bản mẫu:Math 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 đủ Bản mẫu:Math. Đồ thị này là Bản mẫu:Math-bộ khung của một cross-polytope Bản mẫu:Mvar chiều; ví dụ, đồ thị Bản mẫu:Math là một đồ thị của hình bát diện đều. Nếu Bản mẫu:Mvar 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 Bản mẫu:Math; vì thế nó còn được gọi là đồ thị tiệc cocktail.
Đồ thị Turán Bản mẫu:Math là một đồ thị hai phía đầy đủ và là một đồ thị Moore nếu Bản mẫu:Mvar chẵn. Nếu Bản mẫu:Mvar là ước của Bản mẫu:Mvar, đồ 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 Bản mẫu:Math có Bản mẫu:Math clique cực đại, trong đó Bản mẫu:Math và Bản mẫu:Math; 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ị Bản mẫu:Mvar đỉnh bất kể số cạnh; những đồ thị này còn được gọi là đồ thị Moon–Moser.[4]
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.[1] Nikiforov dùng đồ thị Turán để cho ra một chặn dưới cho tổng của trị riêng thứ Bản mẫu:Mvar của một đồ thị và phần bù của nó.[5]
Một đồ thị Bản mẫu:Mvar với Bản mẫu:Mvar đỉnh là một đồ thị con của một đồ thị Turán Bản mẫu:Math khi và chỉ khi Bản mẫu:Mvar có một cách tô màu công bằng với Bản mẫu:Mvar màu. Sự phân hoàn đồ thị Turán thành Bản mẫu:Mvar tập khác nhau tương ứng với sự phân hoạch Bản mẫu:Mvar theo màu. Cụ thể hơn, đồ thị Turán Bản mẫu:Math là đồ thị Bản mẫu:Mvar đỉnh cực đại duy nhất với một phép tô màu công bằng với Bản mẫu:Mvar màu.