Artikel

13.3: Teori Ramsey


13.3: Teori Ramsey

Teorema Ramsey

Dalam matematik gabungan, Teorema Ramsey, dalam salah satu bentuk teori-grafiknya, menyatakan bahawa seseorang akan menemui klise monokromatik di mana-mana pelabelan tepi (dengan warna) graf lengkap yang cukup besar. Untuk menunjukkan teorema untuk dua warna (katakanlah, biru dan merah), biarkan r dan s menjadi dua nombor bulat positif. [1] Teorema Ramsey menyatakan bahawa terdapat bilangan bulat paling positif R(r, s) di mana setiap pewarnaan tepi biru-merah grafik lengkap dihidupkan R(r, sbucu mengandungi klik biru di r bucu atau butang merah di s bucu. (Ini R(r, s) menandakan bilangan bulat yang bergantung pada kedua-duanya r dan s.)

Teorema Ramsey adalah hasil asas dalam penggabungan. Versi pertama hasil ini dibuktikan oleh F. P. Ramsey. Ini memulai teori kombinasi yang sekarang disebut teori Ramsey, yang mencari keteraturan di tengah gangguan: keadaan umum untuk kewujudan substruktur dengan sifat biasa. Dalam aplikasi ini adalah persoalan mengenai keberadaan subset monokromatik, iaitu, subset tepi bersambung hanya satu warna.

Sambungan teorema ini berlaku untuk sebilangan warna yang terbatas, dan bukan hanya dua. Lebih tepat lagi, teorema menyatakan bahawa untuk sebilangan warna, c, dan sebarang bilangan bulat yang diberikan n1, . nc, ada nombor, R(n1, . nc, sedemikian rupa sehingga jika tepi grafik susunan lengkap R(n1, . nc) berwarna dengan c warna yang berbeza, kemudian untuk sebilangan i antara 1 hingga c, mesti mengandungi subgraf pesanan yang lengkap ni yang tepi semuanya berwarna i. Kes khas di atas mempunyai c = 2 (dan n1 = r dan n2 = s).


Hasil khas dalam teori Ramsey bermula dengan beberapa struktur matematik yang kemudiannya dipotong-potong. Seberapa besar struktur asalnya untuk memastikan bahawa sekurang-kurangnya satu kepingan mempunyai harta yang menarik? Idea ini dapat didefinisikan sebagai keteraturan partisi.

Sebagai contoh, pertimbangkan grafik susunan lengkap n iaitu ada n bucu dan setiap bucu dihubungkan ke setiap bucu lain dengan tepi. Graf lengkap urutan 3 dipanggil segitiga. Sekarang warnakan setiap tepi sama ada merah atau biru. Berapa besar mesti n untuk memastikan bahawa terdapat sama ada segitiga biru atau segitiga merah? Ternyata jawapannya adalah 6. Lihat artikel mengenai teorema Ramsey untuk bukti yang tegas.

Cara lain untuk menyatakan hasil ini adalah seperti berikut: di mana-mana pihak dengan sekurang-kurangnya enam orang, ada tiga orang yang semuanya saling kenal (masing-masing mengenali dua yang lain) atau saling tidak dikenali (masing-masing tidak mengenali yang lain dua). Lihat teorema mengenai rakan dan orang asing.

Ini juga merupakan kes khas teorema Ramsey, yang mengatakan bahawa untuk bilangan bulat tertentu c, sebarang bilangan bulat yang diberikan n1. nc, ada nombor, R(n1. nc), sekiranya bahagian tepi grafik susunan lengkap R(n1. nc) berwarna dengan c warna yang berbeza, kemudian untuk sebilangan i antara 1 hingga c, mesti mengandungi subgraf pesanan yang lengkap ni yang tepi semuanya berwarna i. Kes khas di atas mempunyai c = 2 dan n1 = n2 = 3.

Dua teori utama teori Ramsey adalah:

    : Untuk apa-apa yang diberikan c dan n, ada nombor V, jika itu V nombor berturut-turut diwarnai dengan c warna yang berbeza, maka mestilah mengandungi panjang aritmetik n yang unsurnya semuanya sama warna. : Untuk apa-apa yang diberikan n dan c, ada nombor H jika sel-sel sebuah H-dimensi n×n×n×. ×n kiub berwarna dengan c warna, mesti ada satu baris, lajur, dan lain-lain n semua selnya mempunyai warna yang sama. Iaitu: pemain berbilang n-in-a-baris tic-tac-toe tidak boleh berakhir dengan seri, tidak kira seberapa besar n adalah, dan tidak kira berapa orang yang bermain, jika anda bermain di papan dengan cukup banyak dimensi. Teorema Hales – Jewett menyiratkan teorema Van der Waerden.

Teorema yang serupa dengan teorema van der Waerden adalah Teorema Schur: untuk apa-apa yang diberikan c ada nombor N jika nombor 1, 2 ,. N diwarnai dengan c warna yang berbeza, maka mesti ada sepasang bilangan bulat x, y seperti itu x, y, dan x+y semua warna sama. Banyak generalisasi teorema ini ada, termasuk teorema Rado, teorema Rado – Folkman – Sanders, teorema Hindman, dan teorema Milliken – Taylor. Rujukan klasik untuk ini dan banyak hasil lain dalam teori Ramsey adalah Graham, Rothschild, Spencer dan Solymosi, dikemas kini dan diperluas pada tahun 2015 hingga edisi baru pertamanya dalam 25 tahun. [2]

Hasil dalam teori Ramsey biasanya mempunyai dua ciri utama. Pertama, mereka tidak konstruktif: mereka mungkin menunjukkan bahawa ada struktur yang ada, tetapi mereka tidak memberikan proses untuk mencari struktur ini (selain pencarian brute-force). Sebagai contoh, prinsip lubang merpati adalah dalam bentuk ini. Kedua, sementara hasil teori Ramsey mengatakan bahawa objek yang cukup besar semestinya mengandungi struktur tertentu, selalunya bukti hasil ini memerlukan objek ini sangat besar - batas yang tumbuh secara eksponensial, atau bahkan secepat fungsi Ackermann tidak biasa. Dalam beberapa kes ceruk kecil, batas atas dan bawah diperbaiki, tetapi tidak secara umum. Dalam banyak kes, batasan ini adalah artifak bukti, dan tidak diketahui sama ada ia dapat diperbaiki dengan ketara. Dalam kes lain, diketahui bahawa sebarang batas mesti besar, kadang-kadang bahkan lebih besar daripada fungsi rekursif primitif, lihat teorema Paris – Harrington. Nombor Graham, salah satu nombor terbesar yang pernah digunakan dalam bukti matematik yang serius, adalah batas atas masalah yang berkaitan dengan teori Ramsey. Contoh besar lain adalah masalah tiga kali ganda Boolean Pythagoras. [3]

Teorema dalam teori Ramsey umumnya adalah salah satu daripada dua jenis berikut. Banyak teorema seperti itu, yang dimodelkan berdasarkan teorema Ramsey itu sendiri, menegaskan bahawa dalam setiap partisi objek berstruktur besar, salah satu kelas semestinya mengandungi sub-objektif berstruktur besar, tetapi tidak memberikan maklumat mengenai kelas mana ini. Dalam kes lain, alasan di sebalik a Jenis Ramsey hasilnya ialah kelas partisi terbesar selalu mengandungi substruktur yang diinginkan. Hasil dari jenis terakhir ini disebut juga hasil ketumpatan atau Hasil jenis Turán, selepas teorema Turán. Contoh terkenal termasuk teorema Szemerédi, yang merupakan pengukuhan teorema van der Waerden, dan versi kepadatan teorema Hales-Jewett. [4]


13.3: Teori Ramsey

Bagaimana jika anda berusaha mendapatkan graf yang berbeza? Katakan graf lengkap pada empat bucu dalam warna anda, atau kitaran empat tepi?

Teori Ramsey juga membuktikan bahawa tidak kira grafik mana yang anda pilih untuk setiap pemain cuba diwarnakan untuk menang (atau walaupun terdapat graf yang berbeza untuk pemain yang berbeza!) Terdapat sebilangan bucu yang akan menjamin bahawa ada pemenang. Walau bagaimanapun, nombor ini tidak diketahui dalam kebanyakan kes! Kami akan menulis R (k, l) untuk bilangan bucu terkecil sehingga jika kita mewarnai semua tepinya merah dan biru, terdapat grafik lengkap merah pada bucu k atau graf lengkap biru pada bucu l. Kami akan menulis Kn untuk graf lengkap pada n bucu. (Jadi K3 adalah segitiga.)

Di atas kami membuktikan bahawa R (3,3) = 6. Perhatikan juga bahawa R (k, 1) = R (l, k) kerana jika kita dapat mencari sama ada K merahk atau K birul tidak kira bagaimana kita mewarnai bahagian tepi, kita hanya boleh menukar semua warna di tepi dan mempunyai K merahl atau K biruk.

Sekiranya anda perlu menang dengan mewarnai tepi K4, untuk menjamin pemenang, kita memerlukan sekurang-kurangnya R (4,4) bucu. Mari cuba cari anggaran untuk R (4,4). Sekiranya kita dapat menemui sebilangan bucu n yang menjamin sama ada K merah4 atau K biru4 maka kita akan tahu sama ada R (4,4) = n atau R (4,4)

Tetapi bagaimana jika kita tidak mempunyai tepi merah yang cukup untuk ini berlaku? Kemudian kita mahu terdapat tepi biru yang cukup sehingga terdapat K merah4 atau K biru3. Ini sama dengan soalan terakhir, kecuali dengan warna yang ditukar! Oleh itu, jika kita tidak mempunyai tepi merah R (3,4), kita memerlukan tepi biru R (4,3) = R (3,4)! Sekiranya terdapat tepi 2R (3,4) - 1 dari v, maka mesti ada tepi merah R (3,4) atau tepi biru R (3,4) berdasarkan prinsip lubang merpati. Oleh itu, jika kita mempunyai bucu 2R (3,4), maka kita tahu bahawa kita mempunyai pemenang dalam permainan ketika setiap pemain berusaha membuat K4. (Kami menunjukkan R (4,4) = 2R (3,4) atau R (4,4) 8, jadi dengan R (3,4) = 9 atau R (3,4) 8.

Sekarang, mari kita satukan kepingannya! R (3,4) = 9 dan kita tahu bahawa R (4,4) = 2R (3,4) atau R (4,4) <2R (3,4) = 18. Sebenarnya, dapat dibuktikan bahawa R (4,4) = 18. (Bolehkah anda mencari pewarna K17 sehingga tidak ada K merah4 dan tiada K biru4Jadi jika kita mempunyai sekurang-kurangnya 18 bucu, maka mesti ada pemenangnya.

Sekiranya anda bermain yang memerlukan pusingan 4 tepi untuk menang, 6 bucu masih berfungsi untuk menjamin pemenang. Bolehkah anda mengetahui mengapa?


Kursus mini dalam Geometri Terhingga dan Teori Ramsey

Ini adalah kursus mini dalam talian dua minggu yang intensif di mana kita akan mempelajari beberapa aplikasi geometri hingga teori Ramsey. Kami akan merangkumi beberapa terobosan baru-baru ini dalam teori Ramsey grafik dan membincangkan bagaimana geometri terhingga dapat memainkan peranan dalam kemajuan selanjutnya.

Tidak diperlukan latar belakang geometri terhingga atau teori Ramsey. Latar belakang algebra yang kita perlukan dikaji di sini dan perkiraan asimtotik umum yang akan kita gunakan disemak di sini.

Akan ada 6 ceramah (masing-masing 1.5 jam), 2 sesi latihan dan 2 sesi masalah terbuka.

Tarikh: 11-01-2021 hingga 22-01-2021.

Masa: 15:30 & # 8211 17:15 UTC

Minggu Pertama, 11 Jan hingga 15 Jan:

Isnin, Kuliah 1: pengenalan, ruang affine, ruang projektif dan segiempat umum. Video.

Selasa, Kuliah 2: teori segiempat umum dan grafik spektrum. Video.

Rabu, Sesi Latihan 1. Lembaran 1, Penyelesaian.

Khamis, Kuliah 3: Nombor Ramsey, konstruksi eksplisit untuk r (3, t). Video.

Jumaat, Kuliah 4: batas bawah melalui grafik dengan beberapa set bebas, ruang kutub, Video.

Minggu Kedua, 18 Januari hingga 22 Jan:

Isnin, Kuliah + Sesi Latihan: ruang kutub, Lembaran 2. Video.

Selasa, Kuliah 5: grafik pseudorandom bebas clique secara optimum dari bentuk kuadratik. Video.

Rabu, Kuliah 6: nombor Ramsey pepenjuru pelbagai warna, Video.

Khamis, Sesi Masalah Terbuka 1.

Jumaat, Sesi Masalah Terbuka 2.

The Nota kuliah boleh didapati di sini.

  1. Bola Simeon, Geometri Terhingga dan Aplikasi Gabungan
  2. Bart De Bruyn, Pengantar Geometri Kejadian
  3. Chris Godsil dan Gordon Royle, Teori Graf Algebra
  4. Luca Trevisan, Nota Kuliah mengenai Pengembangan, Potongan Sparsest, dan Teori Graf Spektral
  5. Akihiro Munemasa, Geometri kumpulan ortogonal melebihi bidang terhingga.
  6. Yuval Wigderson, nombor Ramsey pelbagai warna.
  7. David Conlon, teori Graf Ramsey.
  8. Michael Krivelevich dan Benny Sudakov, grafik Pseudo-random.
  9. Grafik Jacques Verstraete, Pseudorandom Ramsey.
  1. N. Alon. Graf Ramsey eksplisit dan label ortonormal. Elektron J Comb, halaman # R12, 1994
  2. N. Alon dan M. Krivelevich. Batasan konstruktif untuk masalah jenis Ramsey. Grafs Comb, 13 (3): 217-225,1997
  3. J. Bamberg, A. Bishnoi, dan T. Lesgourgues. Tahap minimum Ramsey grafik minimum untuk cliques.arXiv: 2008.02474, 2020
  4. A. Bishnoi, F. Ihringer, dan V. Pepe. Pembinaan untuk grafik pseudorandom bebas clique. Combinatorica, 40: 307–314, 2020.
  5. D. Conlon. Urutan graf pseudorandom bebas segitiga. Gabungkan. Probab. Komput., 26: 195–200, 2017.
  6. D. Conlon dan A. Ferber. Batas bawah untuk nombor Ramsey pelbagai warna. Lanjutan Math., Diterima, arXiv: 2009.10458, 2020 (Blog).
  7. X. Dia dan Y. Wigderson. Nombor Ramsey pelbagai warna melalui grafik pseudorandom. arXiv: 1910.06287, 2019.
  8. S. Kopparty. Grafik Cayley. 2011. (Blog)
  9. A. Kostochka, P. Pudlák, & amp V. Rödl. Beberapa batas konstruktif pada nombor Ramsey. Jurnal Teori Gabungan, Siri B, 100(5), 439-445, 2010.
  10. Patrick Morris, Clique factor dalam pseudorandom grafik, arXiv: 2101.05092, 2021.
  11. D. Mubayi dan J. Verstraëte. Catatan pada grafik Pseudorandom Ramsey. arXiv: 1909.01461, 2019.
  12. A. Sah. Diagonal Ramsey melalui quasirandomness yang berkesan. arXiv: 2005.09251, 2020.
  13. Y. Wigderson. Had bawah yang lebih baik pada nombor Ramsey pelbagai warna.arXiv: 2009.12020, 2020.

Pensyarah: Anurag Bishnoi

Penganjur: Anurag Bishnoi (TU Delft) dan Jozef Skokan (LSE)

Kursus ini terbuka untuk semua orang. Sila daftar menggunakan pautan berikut: https://forms.gle/oxdDo19Pgbdz7iVU8

Pautan zoom akan dihantar melalui e-mel kepada mereka yang mendaftar.

Ditaja oleh penyelidikan secara berpasangan dari Persatuan Matematik London.


Login Institusi
Log masuk ke Perpustakaan Dalam Talian Wiley

Sekiranya anda sebelum ini memperoleh akses dengan akaun peribadi anda, sila log masuk.

Beli bab tunggal
  • Paparan tanpa had artikel / bab PDF dan apa-apa tambahan dan angka yang berkaitan.
  • Artikel / bab boleh dicetak.
  • Artikel / bab boleh dimuat turun.
  • Artikel / bab boleh tidak diagihkan semula.

Ringkasan

Generalisasi Teorem Ramsey

Nombor, Batas, dan Asimptotik Ramsey


Math 497A - Pengantar Teori Ramsey

Blog kursus: Pautan ke bahan tambahan, petunjuk untuk masalah kerja rumah dan lain-lain akan dipaparkan di http://massramsey2011.wordpress.com.

Kandungan

Kursus ini akan merangkumi beberapa keputusan utama Ramsey Theory. Paradigma asas teori Ramsey adalah bahawa jika strukturnya cukup besar, ia akan mempunyai substruktur biasa dengan ukuran tertentu. Kami akan menerangkan prinsip ini melalui sejumlah hasil dari teori grafik, teori nombor, dan geometri gabungan. Sepanjang perjalanan, kita akan menghadapi fenomena khas teori Ramsey - cukup besar sungguh besar. Kami akan menyiasat fenomena ini dan melihat bahawa ia mempunyai beberapa kesan menarik mengenai asas matematik.

Nota kuliah

Bacaan yang Disyorkan

  • Graham, Rothschild, dan Spencer - Ramsey Theory, 1990
  • Nesetril - Teori Ramsey, dalam: Buku Panduan Gabungan, 1995

Kerja rumah

Kerja rumah akan ditugaskan masing-masing Isnin dan akan dijadualkan masuk kelas pada hari Isnin berikutnya di dalam kelas. Kerja rumah akan dinilai dan dua markah terendah akan dijatuhkan. Kerja rumah yang lewat tidak akan diterima. Akan ada tiada pengecualian kepada peraturan ini. Sudah tentu ia mungkin berlaku bahawa anda tidak dapat menyerahkan kerja rumah kerana anda sakit atau kerana alasan lain yang sah. Inilah sebabnya mengapa dua markah terendah akan dijatuhkan.


Kerja Rumah 1, akan berakhir pada 29 Ogos 2011 (Penyelesaian)
Kerja rumah 2, kerana 7 September, 2011 (Penyelesaian)
Kerja rumah 3, dijadualkan pada 12 September 2011 (Penyelesaian)
Kerja rumah 4, dijadualkan pada 19 September 2011 (Penyelesaian)
Kerja rumah 5, tarikh 26 September 2011 (Penyelesaian)
Kerja rumah 6, dijadualkan pada 3 Oktober 2011 (Penyelesaian)
Kerja rumah 7, dijadualkan pada 24 Oktober 2011
Kerja rumah 8, dijadualkan pada 31 Oktober 2011
Kerja rumah 9, dijadualkan pada 7 November 2011
Kerja rumah 10, dijelaskan pada 14 November 2011 (Penyelesaian)
Kerja rumah 11, dijadualkan pada 5 Disember 2011

Projek penyelidikan

Setiap peserta dikehendaki melengkapkan a projek penyelidikan pada topik tertentu. Ini biasanya merangkumi membaca kertas penyelidikan asal. Sebagai sebahagian daripada peperiksaan akhir, setiap peserta akan memberikan perwakilan selama 20 minit untuk projeknya. Selanjutnya, peserta diminta menyediakan laporan bertulis 5-10 halaman.

Saya akan menyediakan senarai kemungkinan projek pada bulan Oktober. Walau bagaimanapun, saya mengalu-alukan cadangan daripada pelajar. Oleh itu, lihat-lihat, baca sedikit, mungkin anda akan menemui topik yang menarik minat anda.

Ujian

Akan ada satu pertengahan: Isnin, 10 Okt, 10: 10-12.
Lembaran persiapan pertengahan (5 Okt 2011)
Peperiksaan ini akan menjadi peperiksaan buku tertutup. Tanpa curang! Bawa buku biru.


Peperiksaan akhir akan, menurut tradisi MASS, akan menjadi peperiksaan lisan individu 1 jam untuk setiap peserta.

Dasar Penggredan

Gred akhir akan mengambil kira skor kerja rumah, pertengahan semester, projek penyelidikan, dan peperiksaan lisan akhir.

Integriti Akademik

Kerjasama: Kerjasama antara pelajar untuk menyelesaikan tugasan kerja rumah dialu-alukan. Ini adalah kaedah yang baik untuk belajar matematik. Begitu juga dengan perundingan sumber lain seperti buku teks yang lain. Walau bagaimanapun, setiap pelajar harus menyerahkan penyelesaiannya sendiri, dan jika anda menggunakan karya atau idea orang lain anda harus menunjukkan sumber dalam penyelesaian anda.
(Walau apa pun, kerja rumah yang lengkap dan betul mendapat kredit penuh.)

Walau bagaimanapun, dari semasa ke semasa akan ada masalah "terkawal", di mana setiap pelajar harus mencari jalan keluarnya sendiri.


Teorema Ramsey yang stokastik

Kami mewujudkan sambungan stokastik Ramsey & # x27s teorema. Sebarang rantaian Markov menghasilkan penapisan yang berkaitan dengan mana yang menentukan definisi masa berhenti. Pewarnaan stokastik ada k-fungsi warna (k & lt ∞) yang ditentukan pada semua pasangan yang terdiri daripada masa berhenti yang terikat dan sejarah separa yang terbatas dari rantai yang dipotong sebelum waktu berhenti ini. Untuk masa berhenti yang terhad θ dan sebarang sejarah yang tidak terhingga ω rantaian Markov, mari ω | θ menunjukkan sejarah separa hingga hingga dan termasuk masa θ (ω). Diberi k = 2, untuk setiap ϵ & gt 0, kami membuktikan bahawa terdapat urutan yang meningkat θ 1 & lt θ 2 & lt times masa berhenti terikat yang mempunyai harta yang, dengan kebarangkalian lebih besar dari 1 - ϵ, sejarah ω sedemikian rupa sehingga nilai yang diberikan kepada semua pasangan (ω | θ i, θ j), dengan i & lt j, adalah sama. Sama seperti teorema Ramsey klasik, kami juga memperoleh teorem Ramsey stokastik finansial yang serupa. Selanjutnya, dengan andaian kehalusan yang sesuai, masa yang harus ditunggu untuk waktu berhenti terakhir (dalam kes kewangan) dibatasi secara seragam, tanpa bergantung pada peralihan kebarangkalian. Kami menggeneralisasikan hasilnya ke nombor terhingga k warna.


Ahlswede R., Cai N., Zhang Z .: Pewarna yang kaya dengan kekangan tempatan. J. Gabungan. Maklumkan. Syst. Sains. 17(3–4), 203–216 (1992)

Albert, M., Frieze, A., Reed, B.: Komen mengenai: "Kitaran Hamilton pelbagai warna" [Elektron. J. Gabungan. 2 (1995), Research Paper 10, 13 pp. (Elektronik) MR1327570 (96b: 05058)]. Elektron. J. Combin., 2: Kertas Penyelidikan 10, Komen 1, 1 dokumen HTML (elektronik) (1995)

Alon N .: Pada dugaan Erdős, Simonovits, dan Sós mengenai teorema anti-Ramsey. J. Teori Graf 7(1), 91–94 (1983)

Alon N., Caro Y., Tuza Z .: Nombor sub-Ramsey untuk kemajuan aritmetik. Gabungan Graf. 5(4), 307–314 (1989)

Alon N., Jiang T., Miller Z., Pritikin D.: Subgraf berwarna yang betul dan subgraf pelangi dalam pewarnaan tepi dengan kekangan tempatan. Struktur Rawak. Algoritma 23(4), 409–433 (2003)

Alon, N., Krech, A., Szabó, T.: Teorema Turán di hypercube. SIAM J. Bijak. Matematik. 21 (1): 66–72 (2007) (elektronik)

Alon, N., Lefmann, H., Rödl, V .: Pada hasil jenis anti-Ramsey. Dalam: Set, Grafik dan Nombor (Budapest, 1991), Colloq. Matematik. Soc. János Bolyai, jilid 60, hlm.9–22. Belanda Utara, Amsterdam (1992)

Alspach B., Gerson M., Hahn G., Hell P.: Pada nombor sub-Ramsey. Ars Combin. 22, 199–206 (1986)

Axenovich M.: Masalah umum Ramsey. Bijak. Matematik. 222(1–3), 247–249 (2000)

Axenovich, M., Choi, J.: Pada pewarnaan mengelakkan kitaran pelangi dan subgraf monokromatik tetap. Manuskrip

Axenovich, M., Fon-Der-Flaass, D.: Mengenai kemajuan aritmetik pelangi. Elektron. J. Gabungan. 11(1): Kertas Penyelidikan 1, 7 (2004) (elektronik)

Axenovich M., Füredi Z., Mubayi D.: Mengenai teori Ramsey umum: kes bipartit. J. Gabungan. Teori Ser. B 79(1), 66–86 (2000)

Axenovich M., Harborth H., Kemnitz A., Möller M., Schiermeyer I .: Rainbows in the hypercube. Gabungan Graf. 23(2), 123–133 (2007)

Axenovich M., Iverson P.: Pewarnaan tepi mengelakkan subgraf pelangi dan monokromatik. Bijak. Matematik. 308(20), 4710–4723 (2008)

Axenovich M., Jamison R.E .: Corak kanonik nombor Ramsey. Gabungan Graf. 21(2), 145–160 (2005)

Axenovich M., Jiang T.: Nombor Anti-Ramsey untuk graf bipartit lengkap lengkap. Ars Combin. 73, 311–318 (2004)

Axenovich M., Jiang T., Kündgen A.: Bilangan kitaran anti-Ramsey bipartit. J. Teori Graf 47(1), 9–28 (2004)

Axenovich, M., Jiang, T., Tuza, Z .: Nombor grafik anti-Ramsey tempatan. Gabungkan. Probab. Komput. 12 (5–6): 495–511 (2003). Isu khas mengenai teori Ramsey

Axenovich M., Kündgen A.: Mengenai masalah anti-Ramsey yang umum. Gabungan 21(3), 335–349 (2001)

Axenovich M., Martin R.: Nombor Sub-Ramsey untuk kemajuan aritmetik. Gabungan Graf. 22(3), 297–309 (2006)

Balandraud É .: Penyelesaian persamaan berwarna dalam kumpulan terhingga. J. Gabungan. Teori Ser. A 114(5), 854–866 (2007)

Balister P.N., Gyárfás A., Lehel J., Schelp R.H .: Nombor, reka bentuk, dan matriks Mono-multi bipartite. J. Gabungan. Teori Ser. A 113(1), 101–112 (2006)

Ball R.N., Pultr A., ​​Vojtěchovský P.: Grafik berwarna tanpa kitaran berwarna. Gabungan 27(4), 407–427 (2007)

Bialostocki, A., Dierker, P., Voxman, W.: Sama ada graf atau pelengkapnya disambungkan: kisah berterusan. Manuskrip

Bialostocki A., Voxman W.: Generalisasi beberapa teorema jenis Ramsey untuk pemadanan. Bijak. Matematik. 239(1-3), 101–107 (2001)

Bialostocki A., Voxman W.: Pada generalisasi monokromatik-pelangi dua teorema jenis Ramsey. Ars Combin. 68, 131–142 (2003)

Blokhuis A., Faudree R., Gyárfás A., Ruszinkó M .: Pewarna anti-Ramsey dalam beberapa pusingan. J. Gabungan. Teori Ser. B 82(1), 1–18 (2001)

Burr, S.A .: Sama ada grafik atau pelengkapnya mengandungi penyapu yang luas. Manuskrip

Burr S.A., Erdős P., Graham R.L., Sós V.T .: Grafik anti-Ramsey maksimum dan nombor kromatik yang kuat. J. Teori Graf 13(3), 263–282 (1989)

Cameron K., Edmonds J .: Komposisi Lambda. J. Teori Graf 26(1), 9–16 (1997)

Cameron K., Edmonds J., Lovász L.: Catatan pada grafik sempurna. Tempoh. Matematik. Tergantung. 17(3), 173–175 (1986)

Chartrand, G., Lesniak, L.: Grafik & amp Digraph, edisi ke-4. Chapman & amp Hall / CRC, Boca Raton (2005)

Chartrand, G., Zhang, P.: Teori Grafik Kromatik. Chapman & amp Hall / CRC, Boca Raton (2009)

Chen, H., Li, X .: Laluan heterokromatik panjang dalam graf bebas segitiga heterokromatik. Manuskrip

Chen, H., Li, X., Tu, J.: Penyelesaian lengkap untuk bilangan pertandingan pelangi. arXiv: math.CO/0611490

Chudnovsky M., Robertson N., Seymour P., Thomas R.: Teorem grafik sempurna yang kuat. Ann. Matematik. (2) 164(1), 51–229 (2006)

Chung F.R.K., Graham R.L .: Grafik lengkap berwarna tepi dengan subgraf berwarna tepat. Gabungan 3(3–4), 315–324 (1983)

Erdős, P.: Masalah yang diselesaikan dan tidak dapat diselesaikan dalam teori nombor kombinatorik dan kombinatorial. Dalam: Prosiding Persidangan Kedua Belas Tenggara mengenai Kombinatorik, Teori Grafik dan Pengkomputeran, Vol. I (Baton Rouge, La., 1981), jilid. 32, hlm. 49–62 (1981)

Erdős P., Fowler T.: Mencari besar hlm-berwarna berdiameter dua subgraf. Gabungan Graf. 15(1), 21–27 (1999)

Erdős, P., Gallai, T.: Pada jalur maksimum dan litar grafik. Matematik Acta. Acad. Sains. Tergantung. 10: 337–356 (1959) (sisipan tidak terikat)

Erdős P., Gyárfás A.: Varian masalah Ramsey klasik. Combinatorica 17(4), 459–467 (1997)

Erdős P., Rado R.: Teorema gabungan. J. Lond. Matematik. Soc. 25, 249–255 (1950)

Erdős P., Rado R.: Teorema gabungan pada klasifikasi subset bagi satu set tertentu. Pro. Lond. Matematik. Soc. (3) 2, 417–439 (1952)

Erdős P., Simonovits M.: Teorema had dalam teori grafik. Belajar. Sains. Matematik. Kelaparan 1, 51–57 (1966)

Erdős, P., Simonovits, M., Sós, V.T .: Teorema Anti-Ramsey. Dalam: Set tidak terhingga dan terbatas (Colloq., Keszthely, 1973 yang dikhaskan untuk P. Erdős pada hari ulang tahunnya yang ke-60), jilid. II, hlm.663–643. Kolok. Matematik. Soc. János Bolyai, jilid 10. Belanda Utara, Amsterdam (1975)

Erdős, P., Spencer, J .: Kaedah probabilistik dalam kombinatorik, vol. 17. Kebarangkalian dan Statistik Matematik. Akademik Akhbar (Anak syarikat Harcourt Brace Jovanovich, Publishers), New York-London (1974)

Eroh L.: Ramsey terkehadapan bilangan padanan. J. Gabungan. Matematik. Gabungkan. Komput. 51, 175–190 (2004)

Eroh L.: Rainbow Ramsey bilangan bintang dan padanan. Lembu. Inst. Gabungkan. Permohonan 40, 91–99 (2004)

Eroh L., Oellermann O.R .: Nombor Ramsey pelangi bipartit. Bijak. Matematik. 277(1–3), 57–72 (2004)

Faudree, R.J., Gould, R., Jacobson, M., Magnant, C.: Pada nombor gallai-Ramsey. Manuskrip

Fraisse, P., Hahn, G., Sotteau, D.: Nombor sub-Ramsey bintang. Dalam: Teori Reka Bentuk Gabungan. Matematik Belanda Utara. Stud., Jld. 149, hlm. 153–163. Belanda Utara, Amsterdam (1987)

Frieze A., Reed B.: Kitaran Hamilton polikromatik. Bijak. Matematik. 118(1-3), 69–74 (1993)

Fujita, S., Kaneko, A., Schiermeyer, I., Suzuki, K.: Pencocokan pelangi dalam graf lengkap dengan warna r. Elektron. J. Gabungan. 16 (1): Kertas Penyelidikan 51 (2009) (elektronik)

Fujita, S., Magnant, C.: Sambungan hasil pelangi Ramsey. Manuskrip

Fujita, S., Magnant, C .: Gallai-Ramsey nombor untuk kitaran. Manuskrip

Fujita, S., Kaneko, A., Saito, A., Schiermeyer, I., Suzuki, K.: Manuskrip

Füredi Z .: Bahagian atas masalah Zarankiewicz. Gabungkan. Probab. Komput. 5(1), 29–33 (1996)

Gallai T.: Transitiv orientierbare Graphen. Matematik Acta. Acad. Sains. Kelaparan 18, 25–66 (1967)

Galvin F.: Nombor masalah lanjutan 6034. Am. Matematik. Isnin 82, 529 (1975)

Gorgol I: Nombor pelangi untuk kitaran dengan tepi loket. Gabungan Graf. 24(4), 327–331 (2008)

Gorgol, I., Łazuka, E.: Nombor pelangi untuk graf tertentu. Dalam: Persidangan Kelima Cracow mengenai Teori Graf USTRON ’06. Elektron. Nota Discrete Math., Vol. 24, hlm.77–79. Elsevier, Amsterdam, (2006) (elektronik)

Gyárfás, A.: Salad buah. Elektron. J. Gabungan. 4 (1): Kertas Penyelidikan 8, 8 hlm. (1997) (elektronik)

Gyárfás A., Lehel J., Nešetřil J., Rödl V., Schelp R.H., Tuza Zs .: Tempatan k-lukisan grafik dan hipergraf. J. Gabungan. Teori Ser. B 43(2), 127–139 (1987)

Gyárfás A., Lehel J., Schelp R.H .: Mencari subgraf monokromatik atau jalan pelangi. J. Teori Graf 54(1), 1–12 (2007)

Gyárfás A., Lehel J., Schelp R.H., Tuza Zs .: nombor Ramsey untuk pewarna tempatan. Gabungan Graf. 3(3), 267–277 (1987)

Gyárfás, A., Sárközy, G., Sebő, A., Selkow, S.: Hasil jenis Ramsey untuk pewarnaan gallai. Manuskrip

Gyárfás A., Simonyi G.: Pewarnaan tepi graf lengkap tanpa segitiga berwarna tiga. J. Teori Graf 46(3), 211–216 (2004)

Hahn G.: Lebih banyak bilangan sub-Ramsey bintang. Bijak. Matematik. 34(2), 131–139 (1981)

Hahn G., Thomassen C.: Nombor sub-Ramsey jalur dan kitaran dan sangkaan pewarna tepi. Bijak. Matematik. 62(1), 29–33 (1986)

Harborth, H., Kemnitz, A., Krause, S.: Manuskrip

Haxell P.E., Kohayakawa Y .: Pada harta grafik Ramanujan yang anti-Ramsey. Struktur Rawak. Algoritma 6(4), 417–431 (1995)

Hell P., Montellano-Ballesteros J.J .: Klek polikromatik. Bijak. Matematik. 285(1–3), 319–322 (2004)

Jamison R.E., Jiang T., Ling A.C.H .: Terhad Ramsey bilangan graf. J. Teori Graf 42(1), 1–16 (2003)

Jamison R.E., West D.B .: Pada corak Ramsey bilangan graf. Gabungan Graf. 20(3), 333–339 (2004)

Jiang T.: Bilangan grafik anti-Ramsey yang dibahagi. J. Gabungan. Teori Ser. B 85(2), 361–366 (2002)

Jiang T.: Pewarna tepi tanpa bintang polikromatik yang besar. Gabungan Graf. 18(2), 303–308 (2002)

Jiang T., Mubayi D.: Had atas baru untuk masalah Ramsey kanonik. Gabungan 20(1), 141–146 (2000)

Jiang T., Pikhurko O .: Bilangan grafik anti-Ramsey yang mempunyai graf kritikal tepi. J. Teori Graf 61(3), 210–218 (2009)

Jiang, T., Schiermeyer, I., West, D.B .: Sangkaan Erdős-Simonovits-Sós untuk k ≤ 7. Manuskrip

Jiang, T., West, D.B .: Pewarnaan tepi graf lengkap yang mengelakkan pokok polikromatik. Dalam: Persidangan Antarabangsa Quadrennial Kesembilan mengenai Teori Grafik, Gabungan, Algoritma dan Aplikasi. Elektron. Catatan Discrete Math., Hlm. 10. Elsevier, Amsterdam (2002) (elektronik)

Jiang, T., West, D.B .: Mengenai dugaan Erdős-Simonovits-Sós mengenai bilangan kitaran anti-Ramsey. Gabungkan. Probab. Komput. 12 (5–6): 585–598 (2003) (Isu khas mengenai teori Ramsey)

Jin, Z., Li, X: Nombor Anti-Ramsey untuk graf dengan kitaran bebas. Elektron. J. Gabungan. 16: Kertas Penyelidikan 85 (2009)

Jungić V., Král D., Škrekovski R.: Pewarnaan grafik satah tanpa muka pelangi. Gabungan 26(2), 169–182 (2006)

Jungić, V., Licht, J., Mahdian, M., Nešetřil, J., Radoičić, R .: Perkembangan aritmetik pelangi dan hasil anti-Ramsey. Gabungkan. Probab. Comput., 12 (5-6): 599-620, 2003. Isu khas mengenai teori Ramsey

Jungić, V., Nešetřil, J., Radoičić, R.: Teori Rainbow Ramsey. Bilangan bulat 5 (2): A9, 13 (elektronik), (2005)

Jungić, V., Radoičić, R.: Perkembangan aritmetik jangka tiga pelangi. Bilangan bulat 3: A18, 8 (elektronik), (2005)

Kano M., Li X: Subgraf monokromatik dan heterokromatik dalam grafik berwarna tepi — tinjauan. Gabungan Graf. 24(4), 237–263 (2008)

Körner J., Simonyi G.: Trifference. Belajar. Sains. Matematik. Tergantung. 30(1–2), 95–103 (1995)

Kündgen A., Pelsmajer M.J .: Pewarnaan graf yang tidak berulang-ulang dengan lebar pokok yang dibatasi. Bijak. Matematik. 308(19), 4473–4478 (2008)

Lefmann H., Rödl V .: Pada nombor Ramsey kanonik untuk graf lengkap berbanding jalur. J. Gabungan. Teori Ser. B 58(1), 1–13 (1993)

Lefmann H., Rödl V .: Pada nombor Erdős-Rado. Gabungan 15(1), 85–104 (1995)

Lefmann H., Rödl V., Wysocka B.: Subset berwarna-warni dalam hipergrafi berwarna. J. Gabungan. Teori Ser. A 74(2), 209–248 (1996)

Li, X., Xu, Z .: Pelbagai padanan pelangi dalam grafik bipartit biasa. arXiv: math.CO/0711.2846

Li, X., Tu, J., Jin, Z .: Pelbagai nombor pelangi yang sepadan. Bijak. Matematik. 309 (8): 2575–2578 (2009)

Lovász L.: Hiprograf normal dan sangkaan grafik yang sempurna. Bijak. Matematik. 2(3), 253–267 (1972)

Manoussakis Y., Spyratos M., Tuza Zs., Voigt M .: Pewarnaan minimum untuk subgraf berwarna dengan betul. Gabungan Graf. 12(4), 345–360 (1996)

Montellano-Ballesteros J.J .: Teorema anti-Ramsey pada potongan tepi. Bincangkan. Matematik. Teori Grafik 26(1), 19–21 (2006)

Montellano-Ballesteros J.J .: Pada bintang yang berwarna-warni. J. Teori Graf 51(3), 225–243 (2006)

Montellano-Ballesteros, J.J., Neumann-Lara, V .: Kitaran yang sama sekali berwarna. Dalam: Persidangan Antarabangsa ke-6 mengenai Teori Graf (Marseille, 2000). Elektron. Nota Discrete Math., Vol. 5, hlm 4 (elektronik). Elsevier, Amsterdam (2000)

Montellano-Ballesteros J.J., Neumann-Lara V.: Teorema anti-Ramsey. Gabungan 22(3), 445–449 (2002)

Montellano-Ballesteros J.J., Neumann-Lara V.: Bilangan graf heterokromatik linear. Gabungan Graf. 19(4), 533–536 (2003)

Montellano-Ballesteros J.J., Neumann-Lara V.: Teorema anti-Ramsey mengenai kitaran. Gabungan Graf. 21(3), 343–354 (2005)

Montellano-Ballesteros J.J., Neumann-Lara V., Rivera-Campo E.: Pada nombor heterokromatik untuk hypercubes. Bijak. Matematik. 308(16), 3441–3448 (2008)

Mubayi D.: Clik pewarnaan tepi dengan tiga warna pada semua 4-clik. Gabungan 18(2), 293–296 (1998)

Mubayi, D., West, D.B .: Pada pewarnaan tepi basikal yang terhad. Matematik diskrit. 257 (2–3): 513–529, 2002. Kleitman dan kombinatorik: perayaan (Cambridge, MA, 1999)

Pula, K.: Multigraf Gallai. Manuskrip

Radziszowski, S.P .: Nombor Ramsey kecil. Elektron. J. Gabungan. 1 Dyn Surv 1, 30 (elektronik), (1994)

Ramamurthi, R., West, D.B .: Pewarnaan had maksimum bagi graf satah. Dalam: Persidangan Antarabangsa Quadrennial Kesembilan mengenai Teori Grafik, Gabungan, Algoritma dan Aplikasi. Elektron. Nota Discrete Math., Vol. 11, hlm. 8 (elektronik). Elsevier, Amsterdam (2002)

Ramsey F.P .: Mengenai masalah logik formal. Pro. Lond. Matematik. Soc. 30, 264–286 (1930)

Rödl V .: Pada keluarga set Ramsey. Gabungan Graf. 6(2), 187–195 (1990)

Sárközy G.N., Selkow S.: Mengenai masalah Burr, Erdős, Graham, dan T Sós anti-Ramsey. J. Teori Graf 52(2), 147–156 (2006)

Schiermeyer I .: Nombor pelangi untuk padanan dan graf lengkap. Bijak. Matematik. 286(1–2), 157–162 (2004)

Schiermeyer, I .: Pewarna pelangi. 2007. Kertas jemputan dari RIMS, Universiti Kyoto

Serra, O .: Beberapa Ramsey dan anti-Ramsey menghasilkan kumpulan terhingga. Dalam: Simposium Antarabangsa Czech-Slovak ke-6 mengenai Combinatorics, Graph Theory, Algorithms and Applications. Elektron. Catatan Discrete Math., Jilid 28, hlm 437–444. Elsevier, Amsterdam (2007)

Simonovits M., SOS V.T .: Pada pewarnaan terhad dari K n. Combinatorica 4(1), 101–110 (1984)

Turán P.: Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48, 436–452 (1941)


Teori Ramsey

Teori Ramsey adalah arah yang agak & ldquonew, & rdquo kira-kira 100 tahun pemikiran matematik yang menarik yang menyentuh banyak bidang matematik klasik seperti kombinatorik, teori nombor, geometri, teori ergodik, topologi, geometri kombinatori, teori set, dan teori ukuran. Teori Ramsey mempunyai idea penyatuannya sendiri, dan beberapa hasilnya adalah antara teori matematik yang paling indah. Tema yang mendasari teori Ramsey dapat dirumuskan sebagai: warna apa pun yang terbatas dari sistem yang cukup besar mengandungi subsistem monokromatik tahap organisasi yang lebih tinggi daripada sistem itu sendiri, atau sebagai T.S. Motzkin terkenal mengatakan, gangguan mutlak adalah mustahil.

Teori Ramsey: Semalam, Hari Ini, dan Esok meneroka sejarah & sejarah rsquos, perkembangan terkini, dan beberapa petunjuk masa depan yang menjanjikan melalui tinjauan yang dijemput yang ditulis oleh penyelidik terkemuka di lapangan. Tiga tinjauan pertama memberikan latar belakang sejarah mengenai subjek ini yang terakhir membahas teori Euclidean Ramsey dan masalah pewarnaan yang berkaitan. Di samping itu, masalah terbuka yang ditimbulkan di seluruh jilid dan dalam bab masalah terbuka penutup akan menarik minat pelajar siswazah dan ahli matematik.


Penyumbang:
J. Burkert, A. Dudek, R. Graham, A. Gyárfás, P.D. Johnson, Jr., S.P. Radziszowski, V. Rödl, J.H. Spencer, A. Soifer, E. Tressler.

Alexander Soifer adalah seorang ahli matematik Amerika yang dilahirkan dan berpendidikan Rusia, seorang profesor matematik di University of Colorado, pengarang kira-kira 200 artikel mengenai matematik, sejarah matematik, pendidikan matematik, ulasan filem, dan lain-lain. Dia adalah Naib Presiden Kanan Dunia Pertandingan Persekutuan Matematik Kebangsaan, yang pada tahun 2006 memberinya Anugerah Paul Erdos. 26 tahun yang lalu Soifer mengasaskan dan sejak itu mempengerusikan Olimpik Matematik Colorado, dan berkhidmat di kedua-dua jawatankuasa Olimpik Matematik USSR dan USA. Nombor Erdos Soifer adalah 1.

"Semasa kita belajar dari kata pendahuluan, [Teori Ramsey: Semalam, Hari Ini dan Esok] grew out of an intentionally non-traditional conference on Ramsey theory. In accordance with that, the book itself is far from being a traditional textbook or reference book on the subject…We learn far more about the history of Ramsey theory than from other sources…the promise of discussing the future is fulfilled by a very extensive list of open problems contributed by numerous participants. Sometimes it is not even clear what the best way of asking a certain question is, and we are shown the raw form of the problem, just as we would if we participated at a conference…the book is undoubtedly a lot of fun. As one expects from a book on Ramsey theory, it is full of problems that are very easy to formulate, but terribly hard to solve…[the book] could well be used for a course using a seminar format, or for self-study by a graduate student familiarizing himself with the subject.” —MAA Reviews


Tonton videonya: - Геометрия 10 класс Мерзляк (Oktober 2021).