Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/159712
|
| Title: | Ramsey Theory中搜尋反例的演算法
Algorithms for Finding Counterexamples in Ramsey Theory |
| Authors: | 葉益廷
Yeh, Yi-Ting |
| Contributors: | 符麥克
Fuchs, Michael
葉益廷
Yeh, Yi-Ting |
| Keywords: | 演算法
拉姆齊理論
拉姆齊定理
拉姆齊數
整數規劃
機器學習
Ramsey Theory
Ramsey's theorem
Ramsey number
Algorithm
Integer Programming
Reinforcement Learning |
| Date: | 2025 |
| Issue Date: | 2025-10-02 11:17:24 (UTC+8) |
| Abstract: | Ramsey theory 是一門發展已有百年的數學領域，其中與組合學、集合論、圖論及幾何學等多個數學領域都有其交集。然而，要理解這個領域，我們先來思考兩個問題。第一個問題是在一個聚會中要有多少人才能保證存在三個人互相都認識或者是三個人互相都不認識？第二個問題是是否存在一種演算法可以確切求出Ramsey number的數值？以上這兩道問題揭示了Ramsey theory的核心概念及繁雜性，構成了本論文研究的基石。本論文的大綱如下：我們首先回顧Ramsey theory的發展歷史，將其分成三個階段：Pre-Ramsey、Ramsey和Post-Ramsey。接著，我們討論Ramsey number，尤其關注上下界問題。最後，我們介紹兩種尋找Ramsey number反例的演算法：第一種是利用數學最佳化，另一種則是利用機器學習。
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. |
| 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. |
| Description: | 碩士
國立政治大學
應用數學系
112751011 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0112751011 |
| Data Type: | thesis |
| Appears in Collections: | [應用數學系] 學位論文
|
Files in This Item:
| File |
Size | Format | |
|---|
| 101101.pdf | 397Kb | Adobe PDF | 0 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
