Teori Ramsey
Teori Ramsey mengkaji bagaimana ketidakteraturan total adalah mustahil: setiap struktur yang cukup besar harus mengandung substruktur yang sangat terorganisir.
Definition
Cabang kombinatorika yang menanyakan seberapa besar suatu struktur harus ada untuk menjamin bahwa setiap partisi atau pewarnaan darinya menghasilkan substruktur monokromatik atau substruktur lain yang ditentukan.
Scope
Bidang ini mencakup teorema Ramsey untuk graf dan hipergraf serta bilangan Ramsey kuantitatifnya, hasil partisi untuk bilangan bulat seperti teorema Schur, van der Waerden, dan Hales-Jewett, serta teori Ramsey struktural abstrak dari himpunan parameter. Ini mencontohkan prinsip kombinatorial ekstremal bahwa sistem yang cukup besar tidak dapat menghindari keteraturan.
Sub-topics
Core questions
- Seberapa besar suatu struktur harus ada untuk memaksa substruktur terurut yang tidak dapat dihindari?
- Berapa ambang batas yang tepat atau perkiraan, bilangan Ramsey, untuk jaminan ini?
- Bagaimana teorema partisi untuk bilangan bulat menjamin pola aritmatika?
- Keluarga struktur abstrak mana yang memenuhi sifat Ramsey?
Key concepts
- Teorema Ramsey
- Bilangan Ramsey
- Substruktur monokromatik
- Teorema Van der Waerden
- Teorema Schur
- Teorema Hales-Jewett
Clinical relevance
Jaminan struktur yang tidak dapat dihindari tipe Ramsey menginformasikan argumen batas bawah dalam ilmu komputer teoretis, analisis jaringan besar, dan teori bilangan aditif, sementara kesenjangan antara batas yang diketahui mendorong metode probabilistik.
History
Teorema Frank Ramsey tahun 1930 tentang partisi, yang awalnya dibuktikan untuk pertanyaan dalam logika, diakui oleh Erdos dan Szekeres sebagai benih teori luas tentang struktur yang tidak dapat dihindari yang berkembang sepanjang abad ke-20.
Key figures
- Frank Ramsey
- Paul Erdos
- Bartel van der Waerden
Related topics
Seminal works
- graham1990
- landman2003
Frequently asked questions
- Apa slogan teori Ramsey?
- Ketidakteraturan total adalah mustahil: setiap sistem yang cukup besar, bagaimanapun diatur, harus mengandung bagian yang teratur dan cukup besar.
- Mengapa bilangan Ramsey sulit dihitung?
- Jumlah pewarnaan yang harus diperiksa tumbuh secara astronomis, dan bahkan bilangan Ramsey kecil seperti R(5,5) tetap tidak diketahui meskipun ada upaya intens.