Câu đố của Ramsay

9

Ở đây chúng tôi hiển thị ba màu của biểu đồ hoàn chỉnh $K_{16}$, nghĩa là một biểu đồ có 16 đỉnh, tất cả các cặp đỉnh của chúng được nối với nhau bằng các cạnh. Màu này được thay thế bằng thực tế là nó không chứa một hình tam giác có một giá trị duy nhất, trong khi bất kỳ màu (tam giác) nào của đồ thị hoàn chỉnh có số đỉnh lớn (ví dụ: $K_{23}$) nhất thiết phải chứa một hình tam giác như vậy. Một biểu đồ hoàn chỉnh có số đỉnh nhỏ nhất, trong đó, khi tô màu, nhất thiết phải gặp phải cấu hình một giá trị bị cấm (trong trường hợp này là hình tam giác), được gọi là “biểu đồ Ramsey” (đối với một tập hợp các cấu hình bị cấm nhất định). Như vậy, đồ thị $K_{17}$ là đồ thị Ramsey tương ứng. Tất nhiên, đối với các số lượng màu khác và các bộ cấu hình khác, đồ thị Ramsey của riêng chúng sẽ xuất hiện; bạn có thể đọc về chúng trong bài viết của M. Gardner trong số này. Mỗi đồ thị Ramsey (có n đỉnh) có một câu đố và một cg gắn liền với nó. Câu đố là tô màu biểu đồ hoàn chỉnh $K_{n-1}$ mà không tạo bất kỳ cấu hình bị cấm nào. (Vì vậy, ở đây là hình - lời giải của câu đố này cho $n=17$). Izra được thực hiện trên biểu đồ Ramsey (giả sử, trên $K_{17}$) bằng hai đường lần lượt cắt ra các cạnh của biểu đồ (ở đây - có ba màu), các cấu hình bị cấm đã biết (ở đây - các hình tam giác có giá trị đơn); Người thua cuộc là người bị buộc phải tạo ra cấu hình như vậy. Không có lễ lạy (tại sao?).