塞邁雷迪定理
在中，塞邁雷迪定理（）是個關於自然數集子集中的等差数列的結論。1936年，艾狄胥·帕爾和圖蘭·帕爾猜想：若整數集 A 具有正的自然密度，則對任意的正整數 k, 都可以在 A 中找出一個 k 項的等差數列。匈牙利數學家塞迈雷迪·安德烈於1975年證明了此結論。 定理敍述 若自然数集的子集 A 滿足 :\limsup_{n \to \infty}\frac{n} > 0, 則稱 A 具有正的上密度。塞邁雷迪定理斷言，若自然數集的一個子集具有…
标签：#拉姆齊理論
共 9 篇文章
拉姆齐定理
在組合數學上，拉姆齐定理（），又称拉姆齐二染色定理，斷言對任意正整數k和l，若一個聚會的人數n足夠大，則無論相识關係如何，必定有k个人相识或l个人互不相识。給定k, l時，保證前述結論的最小n值稱為拉姆齊數R(k,l)，其值取決於k, l。用圖論術語複述：若將足夠大的完全圖各邊染紅藍兩色，則不論如何染，必定有紅色的k階完全圖或藍色的l階完全圖。 拉姆齊定理是組合數學的重要結論，以弗兰克·普伦普顿·拉姆齐命名。他在1930年論文證明此定理…
友誼定理
友誼定理（Friendship Theorem）說明：在一群人数不少於三的人群中，若任意兩人都剛好只有一個共同認識的人，這群人中總有一人是所有人都認識的。 在圖論的角度來說，一幅圖，若每個頂點都跟另一個頂點剛好只有一個共同相鄰的頂點，這幅圖中有一個頂點和其他頂點都相鄰。 參考 *拉姆齐定理
葛立恆數
葛立恆數（）由美国数学家葛立恆（）提出，曾經被視為在正式數學證明中出現過最大的數，它大得連高德納箭號表示法也難以簡單表示，而必須使用64層高德納箭號表示法才表示得出來。馬丁·加德納於1977年11月在美國科學人雜誌的「數學遊戲」專欄將此數刊登出來，1980年被金氏世界紀錄定為在正式數學證明中出現過最大的數。 問題背景 共平面且單色的完全子圖」，子圖繪於三維立方體的下方。注意到若將此子圖的下方改成蓝色，則此例將不再含有「四頂點共平面且單色…
鴿巢原理
鴿籠原理，又名狄利克雷抽屜原理、鴿巢原理。 其中一種簡單的表述法為： 若有n個籠子和n+1隻鴿子，所有的鴿子都被關在鴿籠裡，那麼至少有一個籠子有至少2隻鴿子。 另一種為： 若有n個籠子和kn+1隻鴿子，所有的鴿子都被關在鴿籠裡，那麼至少有一個籠子有至少k+1隻鴿子。 集合论的表述如下： 若A是n+1元集，B是n元集，則不存在從A到B的單射。 拉姆齐定理是此原理的推廣。 例子 雖然鴿巢原理看起來很容易理解，但有時使用鴿巢原理會得到一些有趣…
范德瓦尔登定理
范德瓦尔登定理（）是数论中的一个定理，由荷兰数学家巴特尔·伦德特·范德瓦尔登证明。对于任意给定的正整数 r 和 k，总存在正整数N，使得把数 {1，2，……，N} 染成 r 种颜色时, 对每一种染色方式,都存在k个数组成的等差数列染同一种颜色的。这个最小的N叫做范德瓦尔登数 V(r,k)。这个定理可视作拉姆齊理論领域的一个结果。 例如，V(2,3)=9，因为可以把整数 {1, 2, …, 8} 涂成以下的颜色： 但无论如何，都不能把数{…
幸福結局問題
幸福結局問題（，由保羅·艾狄胥命名，因為這個問題令喬治·塞凱賴什和愛絲特·克萊共諧連理）是問，在平面上，給定一般位置（即平面上任意三點不共線）上的多少點，才令其中必可以找到n點能組成凸n邊形？ 1935年，艾狄胥和塞凱賴什證明：給定任意正整數N，存在正整數M使得給定在平面上一般位置上的M點，其中必可以找到N點能組成凸N邊形。 將f(N)表示為M的最小可能值，已知 f(3)=3：顯然易見 f(4)=5 ：愛絲特·克萊證明；這就是最初的問題…
格林-陶定理
格林-陶定理（）是和陶哲轩于2004年证明的一个关于质数组成的等差数列存在性定理。质数序列包含任意长的等差数列，是格林-陶定理的著名推论。 定理内容 对于任意的素数集合的子集A，若A相对于素数集合的上密度（）为正，即： : \limsup_{N\rightarrow\infty} \dfrac{\pi(N)}>0 : 其中，\pi(N)代表不大于N的素数的个数。 那么： : 对于任意的正整数k，A中的元素可以组成任意多个长度为k的等差数…
拉姆齐理论
拉姆齊理論得名自英國數學家兼哲學家弗蘭克·普倫普頓·拉姆齊，是數學的一支，在大而無迭序的結構中尋找必然出現的有迭序的子結構。拉姆齊理論研究的典型問題形如：「某某結構要何等大，才能保證具有某某性質？」更具體而言，葛立恆稱拉姆齊理論為「組合數學的分支」。 例子 拉姆齊理論的典型例子中，先有某個數學結構，然後該數學結構會切成若干小份，問題是原結構要多大，才能保證不論切法為何，仍有某一份具有指定的性質。此想法帶出的嚴格定義。 例如，考慮n階完全…