Định lý Ramsey và các số Ramsey

Định lý Ramsey đảm bảo rằng bất kỳ đồ thị đầy đủ hai màu đủ lớn nào cũng chứa một clique đơn sắc, và các số Ramsey định lượng mức độ lớn đủ đó.

Definition

Số Ramsey R(s,t) là số nguyên nhỏ nhất n sao cho mọi cách tô màu đỏ-xanh các cạnh của đồ thị đầy đủ trên n đỉnh đều chứa một clique đỏ trên s đỉnh hoặc một clique xanh trên t đỉnh.

Scope

Chủ đề này bao gồm dạng đồ thị của định lý Ramsey, định nghĩa các số Ramsey R(s,t), các trường hợp nhỏ cổ điển như R(3,3)=6, cận trên Erdos-Szekeres và cận dưới xác suất của Erdos, và sự mở rộng sang số Ramsey đa màu và siêu đồ thị. Đây là trọng tâm định lượng của lý thuyết Ramsey.

Core questions

• Một đồ thị đầy đủ phải lớn đến mức nào để buộc phải có một clique đơn sắc với kích thước cho trước?
• Các giá trị chính xác và cận của số Ramsey đã biết là gì?
• Các lập luận xác suất đưa ra cận dưới cho số Ramsey như thế nào?
• Định lý tổng quát hóa như thế nào đối với nhiều màu và siêu đồ thị?

Key concepts

• Định lý Ramsey cho đồ thị
• Số Ramsey R(s,t)
• Clique đơn sắc
• Cận Erdos-Szekeres
• Cận dưới xác suất
• Số Ramsey đa màu và siêu đồ thị

Key theories

Cận trên Erdos-Szekeres

Các số Ramsey là hữu hạn và bị chặn bởi R(s,t) không quá hệ số nhị thức của s+t-2 chọn s-1, một cận dựa trên công thức truy hồi chứng minh định lý Ramsey với các ước tính rõ ràng.

Cận dưới xác suất của Erdos

Bằng cách đếm số clique đơn sắc kỳ vọng trong một phép tô màu ngẫu nhiên, Erdos đã chỉ ra vào năm 1947 rằng số Ramsey đường chéo R(s,s) tăng ít nhất theo cấp số nhân, một ứng dụng nền tảng của phương pháp xác suất.

Clinical relevance

Phương pháp xác suất được giới thiệu thông qua các cận dưới của số Ramsey đã trở thành một công cụ trung tâm trong tổ hợp và khoa học máy tính lý thuyết, và các đảm bảo kiểu Ramsey củng cố các cận dưới trong truyền thông và cấu trúc dữ liệu.

History

Erdos và Szekeres đã khám phá lại và định lượng định lý Ramsey vào năm 1935 khi nghiên cứu các đa giác lồi; cận dưới tô màu ngẫu nhiên năm 1947 của Erdos đã khởi xướng phương pháp xác suất.

Key figures

• Frank Ramsey
• Paul Erdos
• George Szekeres

Seminal works

• graham1990

Frequently asked questions

Tại sao R(3,3) bằng sáu?

Trong số sáu người bất kỳ, có ba người quen biết lẫn nhau hoặc ba người hoàn toàn xa lạ, trong khi năm người có thể được sắp xếp để tránh cả hai trường hợp, vì vậy sáu là ngưỡng chính xác.

Các số Ramsey chính xác có được biết không?

Chỉ một số ít được biết chính xác; ngay cả R(5,5) vẫn chưa được xác định, với kiến thức hiện tại chỉ thu hẹp nó vào một khoảng, vì không gian tìm kiếm tăng quá nhanh để giải quyết bằng tính toán.