✨Đồ 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à :$\backslash frac\{1\}\{2\}(n^2\; -\; s\backslash lceil\; n/r\backslash rceil^2\; -\; (r-s\backslash lfloor\; n/r\backslash rfloor^2)=\backslash frac\{(r-1)(n^2-s^2)\}\{2r\}+\backslash binom\{s\}\{2\}\; \backslash leq\; \backslash frac\{(r-1)n^2\}\{2r\}.$

Đồ 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 :$\backslash frac\{r\backslash ,\{-\}\backslash ,1\}\{3r\}(2\backslash alpha\; -1)n^2$ 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

thumb|Một [[bát diện đều, có các cạnh và đỉnh tạo thành , là một đồ thị Turán . Những đỉnh không được nối nằm trong cùng một tập phân hoạch và được tô cùng màu trong hình chiếu này.]] 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.

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.