Lý thuyết Ramsey
Lý thuyết Ramsey nghiên cứu cách mà sự hỗn loạn hoàn toàn là không thể: bất kỳ cấu trúc đủ lớn nào cũng phải chứa một cấu trúc con có tổ chức cao.
Definition
Nhánh của tổ hợp học đặt câu hỏi về mức độ lớn của một cấu trúc để đảm bảo rằng bất kỳ sự phân hoạch hoặc tô màu nào của nó cũng tạo ra một cấu trúc con đơn sắc hoặc được quy định khác.
Scope
Lĩnh vực này bao gồm định lý Ramsey cho đồ thị và siêu đồ thị cùng với các số Ramsey định lượng của nó, các kết quả phân hoạch cho số nguyên như các định lý của Schur, van der Waerden và Hales-Jewett, và lý thuyết Ramsey cấu trúc trừu tượng của các tập tham số. Nó minh họa nguyên lý tổ hợp cực trị rằng các hệ thống đủ lớn không thể tránh khỏi trật tự.
Sub-topics
Core questions
- Một cấu trúc phải lớn đến mức nào để buộc phải có một cấu trúc con có trật tự không thể tránh khỏi?
- Ngưỡng chính xác hoặc gần đúng, các số Ramsey, cho những đảm bảo này là gì?
- Các định lý phân hoạch cho số nguyên đảm bảo các mẫu số học như thế nào?
- Những họ cấu trúc trừu tượng nào thỏa mãn tính chất Ramsey?
Key concepts
- Định lý Ramsey
- Số Ramsey
- Cấu trúc con đơn sắc
- Định lý Van der Waerden
- Định lý Schur
- Định lý Hales-Jewett
Clinical relevance
Các đảm bảo kiểu Ramsey về cấu trúc không thể tránh khỏi cung cấp thông tin cho các lập luận giới hạn dưới trong khoa học máy tính lý thuyết, phân tích các mạng lớn và lý thuyết số cộng tính, trong khi khoảng cách giữa các giới hạn đã biết thúc đẩy phương pháp xác suất.
History
Định lý của Frank Ramsey năm 1930 về các phân hoạch, ban đầu được chứng minh cho một vấn đề trong logic, đã được Erdos và Szekeres công nhận là hạt giống của một lý thuyết rộng lớn về cấu trúc không thể tránh khỏi, phát triển mạnh mẽ trong suốt thế kỷ 20.
Key figures
- Frank Ramsey
- Paul Erdos
- Bartel van der Waerden
Related topics
Seminal works
- graham1990
- landman2003
Frequently asked questions
- Khẩu hiệu của lý thuyết Ramsey là gì?
- Sự hỗn loạn hoàn toàn là không thể: bất kỳ hệ thống đủ lớn nào, dù được sắp xếp như thế nào, cũng phải chứa một phần có trật tự đáng kể.
- Tại sao các số Ramsey khó tính toán?
- Số lượng các cách tô màu cần kiểm tra tăng lên một cách phi thường, và ngay cả các số Ramsey nhỏ như R(5,5) vẫn chưa được biết mặc dù đã có nhiều nỗ lực.