Math Labs

Bài toán mở, Tổ hợp và Toán rời rạc, nêu năm 1930

Giá trị của số Ramsey R(5,5)

Còn mở

Xác định giá trị chính xác của số Ramsey đường chéo R(5,5)R(5, 5): số nguyên dương nhỏ nhất nn sao cho mọi phép tô 22 màu các cạnh của đồ thị đầy đủ KnK_n đều chứa một bản sao đơn sắc của K5K_5 (tương đương, mọi đồ thị đơn trên nn đỉnh đều chứa một clique cỡ 55 hoặc một tập độc lập cỡ 55).

Hiện trạng nghiên cứu tính đến năm 2026

Tính đến năm 2026, các cận tốt nhất hiện biết là 43≤R(5,5)≤4643 \le R(5, 5) \le 46. Cận dưới 4343 đến từ 656656 đồ thị (5,5,42)(5, 5, 42) đã biết (gồm 328328 đồ thị và các phần bù của chúng), và vì các tìm kiếm heuristic quy mô lớn chưa bao giờ tìm thấy đồ thị (5,5,43)(5, 5, 43) nào, McKay và Radziszowski phỏng đoán rằng R(5,5)=43R(5, 5) = 43. Cận trên R(5,5)≤46R(5, 5) \le 46 là kết quả của Angeltveit và McKay (preprint năm 2024), kết hợp quy hoạch tuyến tính trên mật độ cạnh-tam giác-bộ bốn đỉnh với tính toán song song quy mô lớn mở rộng các đồ thị con (4,5,k)(4, 5, k).

Kết quả tốt nhất đã biết

  • Giá trị chính xác thỏa mãn 43≤R(5,5)≤4643 \le R(5, 5) \le 46 (cận dưới của Exoo năm 1989; cận trên theo preprint năm 2024 của Angeltveit và McKay).
  • Có đúng 350,904350,904 đồ thị (4,5,24)(4, 5, 24) đôi một không đẳng cấu, và các quy tắc dán lân cận của chúng ràng buộc chặt mọi đồ thị (5,5,n)(5, 5, n) giả định với n≥43n \ge 43.

Công cụ và chỗ dừng

Công cụĐạt đượcChỗ dừng
Quy hoạch tuyến tính mật độ đồ thị con và mở rộng lân cận (McKay–Radziszowski, Angeltveit–McKay)Sử dụng tính chất tập đỉnh kề và không kề của mọi đỉnh trong đồ thị (5,5,n)(5, 5, n) phải là các đồ thị (4,5,d)(4, 5, d) và (5,4,n−1−d)(5, 4, n - 1 - d) để loại trừ n=49,48,47n = 49, 48, 47.Khi nn tiến gần về 4343, bậc đỉnh dd rơi vào khoảng 19≤d≤2219 \le d \le 22, nơi danh mục các đồ thị (4,5,d)(4, 5, d) bùng nổ lên hàng nghìn tỷ lớp đẳng cấu.

Câu hỏi còn mở

  • Liệu R(5,5)=43R(5, 5) = 43 đúng như phỏng đoán của McKay và Radziszowski hay không?
  • Liệu 656656 đồ thị (5,5,42)(5, 5, 42) đã biết có phải là toàn bộ các đồ thị cực trị 4242 đỉnh tránh được K5K_5 đơn sắc hay không?

Tài liệu tham khảo

  1. Geoffrey Exoo (1989). A lower bound for r(5, 5) · DOI:10.1002/jgt.3190130113
  2. Brendan D. McKay, Stanisław P. Radziszowski (1997). Subgraph counting identities and Ramsey numbers · DOI:10.1006/jctb.1996.1741
  3. Vigleik Angeltveit, Brendan D. McKay (2024). R(5,5) <= 46 · arXiv:2409.15709 [preprint, chưa bình duyệt]