| dc.contributor.advisor | 符麥克 | zh_TW |
| dc.contributor.advisor | Fuchs, Michael | en_US |
| dc.contributor.author (Authors) | 葉益廷 | zh_TW |
| dc.contributor.author (Authors) | Yeh, Yi-Ting | en_US |
| dc.creator (作者) | 葉益廷 | zh_TW |
| dc.creator (作者) | Yeh, Yi-Ting | en_US |
| dc.date (日期) | 2025 | en_US |
| dc.date.accessioned | 2-Oct-2025 11:17:24 (UTC+8) | - |
| dc.date.available | 2-Oct-2025 11:17:24 (UTC+8) | - |
| dc.date.issued (上傳時間) | 2-Oct-2025 11:17:24 (UTC+8) | - |
| dc.identifier (Other Identifiers) | G0112751011 | en_US |
| dc.identifier.uri (URI) | https://nccur.lib.nccu.edu.tw/handle/140.119/159712 | - |
| dc.description (描述) | 碩士 | zh_TW |
| dc.description (描述) | 國立政治大學 | zh_TW |
| dc.description (描述) | 應用數學系 | zh_TW |
| dc.description (描述) | 112751011 | zh_TW |
| dc.description.abstract (摘要) | Ramsey theory 是一門發展已有百年的數學領域，其中與組合學、集合論、圖論及幾何學等多個數學領域都有其交集。然而，要理解這個領域，我們先來思考兩個問題。第一個問題是在一個聚會中要有多少人才能保證存在三個人互相都認識或者是三個人互相都不認識？第二個問題是是否存在一種演算法可以確切求出Ramsey number的數值？以上這兩道問題揭示了Ramsey theory的核心概念及繁雜性，構成了本論文研究的基石。本論文的大綱如下：我們首先回顧Ramsey theory的發展歷史，將其分成三個階段：Pre-Ramsey、Ramsey和Post-Ramsey。接著，我們討論Ramsey number，尤其關注上下界問題。最後，我們介紹兩種尋找Ramsey number反例的演算法：第一種是利用數學最佳化，另一種則是利用機器學習。 | zh_TW |
| dc.description.abstract (摘要) | Ramsey theory, a field of mathematics that has developed over the past century, intersects with various areas including combinatorics, set theory, graph theory, and geometry. To explain the field, we begin with two fundamental questions. First, how many people must be present at a party to guarantee the existence of a group of three individuals who are either all mutual acquaintances or all mutual strangers? Second, is there an algorithm capable of determining the exact value of a Ramsey number? These questions illustrate the essence and complexity of Ramsey theory and serve as the foundation for the research presented in this thesis. An outline of the thesis is as follows: we start with a historical overview of Ramsey theory, which can be categorized into three distinct periods: the Pre-Ramsey, Ramsey, and Post-Ramsey eras. Subsequently, we discuss Ramsey numbers, focusing on their upper and lower bounds. Finally, we present two algorithms: one based on mathematical optimization and the other on machine learning, both aimed at finding counterexamples to Ramsey numbers. | en_US |
| dc.description.tableofcontents | 摘要 1
Abstract 2
1 Introduction to Ramsey Theory 6
1.1 History 6
1.1.1 Pre-Ramsey [8] 6
1.1.2 Ramsey [5] 9
1.1.3 Post-Ramsey [7] 14
1.2 Ramsey Number 19
1.2.1 Asymptotic Upper Bound 24
1.2.2 Asymptotic Lower Bound 28
1.2.3 Construction Methods for Counterexamples of Ramsey Numbers 37
2 Strategies for Discovering Counterexamples to Ramsey Numbers 41
2.1 Mathematical Optimization 41
2.2 Reinforcement Learning 45
3 Conclusion 50
Bibliography 52 | zh_TW |
| dc.format.extent | 406557 bytes | - |
| dc.format.mimetype | application/pdf | - |
| dc.source.uri (資料來源) | http://thesis.lib.nccu.edu.tw/record/#G0112751011 | en_US |
| dc.subject (關鍵詞) | 演算法 | zh_TW |
| dc.subject (關鍵詞) | 拉姆齊理論 | zh_TW |
| dc.subject (關鍵詞) | 拉姆齊定理 | zh_TW |
| dc.subject (關鍵詞) | 拉姆齊數 | zh_TW |
| dc.subject (關鍵詞) | 整數規劃 | zh_TW |
| dc.subject (關鍵詞) | 機器學習 | zh_TW |
| dc.subject (關鍵詞) | Ramsey Theory | en_US |
| dc.subject (關鍵詞) | Ramsey's theorem | en_US |
| dc.subject (關鍵詞) | Ramsey number | en_US |
| dc.subject (關鍵詞) | Algorithm | en_US |
| dc.subject (關鍵詞) | Integer Programming | en_US |
| dc.subject (關鍵詞) | Reinforcement Learning | en_US |
| dc.title (題名) | Ramsey Theory中搜尋反例的演算法 | zh_TW |
| dc.title (題名) | Algorithms for Finding Counterexamples in Ramsey Theory | en_US |
| dc.type (資料類型) | thesis | en_US |
| dc.relation.reference (參考文獻) | [1] The Electronic Journal of Combinatorics. https://www.combinatorics.org/.
[2] Marcelo Campos, Simon Griffiths, Robert Morris, and Julian Sahasrabudhe. An exponential improvement for diagonal Ramsey. Annals of Mathematics, to appear in forthcoming issues, 2025.
[3] David Conlon. A new upper bound for diagonal Ramsey numbers. Annals of Mathematics, second series, Vol. 170, No. 2, pages 941–960, September, 2009.
[4] Paul Erdős and George Szekeres. A combinatorial problem in geometry. Compositio Mathematica, Vol. 2, pages 463-470, 1935.
[5] Ronald Lewis Graham, Joel Spencer, and Bruce Rothschild. Ramsey Theory. Wiley, 1990.
[6] Parth Gupta, Ndiame Ndiaye, Sergey Norin, and Louis Wei. Optimizing the cgms upper bound on ramsey numbers. https://arxiv.org/pdf/2407.19026, 2024.
[7] Ivars Peterson. Planes of Budapest. https://web.archive.org/web/20130627221430/http://www.maa.org/mathland/mathtrek_10_3_00.html, 2000.
[8] Alexander Soifer. Ramsey Theory : Yesterday, Today and Tomorrow. Birkhäuser, 2010.
[9] Steve Vott and Adam Lehavi. RamseyRL: A Framework for Intelligent Ramsey Number Counterexample Searching, 2023. https://arxiv.org/pdf/2308.11943. | zh_TW |
