Ramsey's theorem (original) (raw)
En mathématiques, et plus particulièrement en combinatoire, le théorème de Ramsey, dû à Frank Ramsey (en 1930), est un théorème fondamental de la théorie de Ramsey. Il affirme que pour tout n, tout graphe complet suffisamment grand dont les arêtes sont colorées contient des sous-graphes complets de taille n d'une seule couleur. En théorie des ensembles, une de ses généralisations, le théorème de Ramsey infini, permet de définir un type particulier de grand cardinal.
| Property | Value |
|---|---|
| dbo:abstract | في التوافقيات، تنص مبرهنة رامزي على أنه بأي تلوين لأضلاع رسم بياني كامل كبير بما فيه الكفاية ، يوجد رسم بياني فرعي كامل أحادي اللون. للونين ، تنص مبرهنة رامزي على أنه لكل زوج من الأعداد الصحيحة الموجبة (r ،s) ، يوجد على الأقل عدد صحيح موجب (R(r ،s ، حيث أنه لأي رسم بياني كامل على (R(r ،s رؤوس ، ملونة أضلاعة بالأحمر أو الأزرق ، إما يوجد رسم بياني فرعي كامل على r رؤوس أضلاعة ملونة بالأزرق، أو رسم بياني فرعي كامل على s رؤوس أضلاعه ملونة بالأحمر. هنا (R(r ،s تعبر عن عدد صحيح الذي يعتمد على كل من r و s. ومن المفهوم تمثيل أصغر عدد صحيح الذي تنطبق عليه المبرهنة. مبرهنة رامزي هي نتيجة تأساسية في التوافقيات. النسخة الأولى من هذه المبرهنة أثبتت على يد الرياضي الانجيزي فرانك رامزي. بدأت هذه المبرهنة نظرية التوافقيات ، التي يطلق عليها حاليا نظرية رامزي، التي تبحث الانتظام وسط الفوضى: شروط عامة لوجود مبنى فرعي مع خصائص منتظمة. في هذه الحالة هي مسألة وجود مجموعة فرعية أحادية اللون، والتي هي مجموعة فرعية من أضلاع متصلة ملونة بلون واحد فقط. إضافة لهذه المبرهنة ينطبق على عدد محدود من الألوان ، بدلا من لونين. بصورة أدق، تنص المبرهنة على أنه لكل عدد معطى من الألوان c، ولكل أعداد صحيحة معطاه n1 ،... ،nc ، يوجد عدد ، (R(n1 ،... ، nc ، حيث أنه إذا تم تلوين أضلاع رسم بياني كامل على (R(n1 ،... ، nc رؤوس بـ c ألوان مختلفة ، يوجد i بين 1 و c ، حيث يجب أن يشمل الرسم البياني الكامل على ni رؤوس الذي ملونة جميع أضلاعه بالون i. (بالحالة الخاصة أعلاه c == 2 و n1 = r و n2 == s). (ar) Στη συνδυαστική, το Θεώρημα Ράμσεϋ δηλώνει ότι σε οποιεσδήποτε χρωματισμένες από ένα αρκετά μεγάλο , θα βρει κανείς μονοχρωματικό πλήρη υπογράφημα. Για δύο χρώματα, το θεώρημα Ramsey αναφέρει ότι για κάθε ζεύγος θετικών ακεραίων (r, s), υπάρχει ένας μικρότερος θετικός ακέραιος R (R, S) τέτοιος ώστε για κάθε 2-χρωματισμούς του R (r, s) κορυφές, υπάρχει ένα πλήρες μονοχρωματικό υπογράφημα είτε r ή s κορυφές. Εδώ R (R, S) σημαίνει έναν ακέραιο που εξαρτάται τόσο από r και s. Είναι κατανοητό να αντιπροσωπεύει το μικρότερο ακέραιο για την οποία το θεώρημα κατέχει. Το θεώρημα του Ramsey είναι ένα θεμελιώδες αποτέλεσμα της Συνδυαστικής. Η πρώτη εκδοχή αυτού του αποτελέσματος αποδείχθηκε μέσω του . Αυτό, ξεκίνησε τη συνδυαστική θεωρία που σήμερα ονομάζεται ,που επιδιώκει την κανονικότητα μέσα διαταραχή: γενικές προϋποθέσεις για την ύπαρξη υποδομών με τακτικές ιδιότητες. Σε αυτή την εφαρμογή είναι ένα ζήτημα της ύπαρξης μονοχρωματικά υποσύνολα, δηλαδή, υποσύνολα συνδεδεμένα άκρα του ένα μόνο χρώμα. Η επέκταση αυτού του θεωρήματος ισχύει για κάθε πεπερασμένο αριθμό των χρωμάτων, και όχι μόνο για δύο. Ακριβέστερα, το θεώρημα δηλώνει ότι για οποιοδήποτε δεδομένο αριθμό χρωμάτων c, και οποιοδήποτε δεδομένο ακέραιοι n1,...,nc, υπάρχει ένας αριθμός, R(n1, ..., nc), έτσι ώστε όταν οι κορυφές ενός πλήρους γραφήματος R(n1, ..., nc) είναι χρωματισμένες με c διαφορετικά χρώματα, τότε για κάποιο i από 1 έως c,πρέπει να περιέχει ένα πλήρες υπογράφημα της τάξης ni των οποίων οι κορυφές είναι όλες χρώμα i. Η ειδική περίπτωση παραπάνω έχει c = 2 (and n1 = r and n2 = s). (el) Der Satz von Ramsey geht auf Frank Plumpton Ramsey und dessen Veröffentlichung aus dem Jahr 1930 zurück. Er zählt zu den klassischen Theoremen der Kombinatorik und stellt eine Verallgemeinerung des dirichletschen Schubfachprinzips dar. Der Satz behandelt die Frage, ob und unter welchen Bedingungen bei Kantenfärbungen von vollständigen Graphen und Hypergraphen mit zwei (oder mehr) Farben einfarbige Teilgraphen auftreten. Es ergibt sich, dass solche Teilgraphen für hinreichend große vollständige Graphen und Hypergraphen stets auftreten müssen. Das derartige Fragestellungen behandelnde Teilgebiet der Kombinatorik wird Ramseytheorie genannt. Neben der reinen Existenzfrage wird in der Diskreten Mathematik auch ein damit zusammenhängendes Quantifizierungsproblem untersucht. Es handelt sich hier um die Frage, ab welcher Größe ein vollständiger Graph bzw. Hypergraph im genannten Sinne als „hinreichend groß“ zu betrachten ist, und weiter darum, wie die in diesem Sinne zu bestimmenden Ramsey-Zahlen zu berechnen oder wenigstens abzuschätzen sind. Diese Quantifizierungsfrage zu klären oder gar zu lösen, hat sich als außerordentlich schwierig herausgestellt. Mit dem Satz von Ramsey lassen sich Existenzsätze der Diskreten Mathematik ableiten und insbesondere kombinatorische Probleme der Geometrie und Zahlentheorie lösen. Eine praktische Anwendung findet er auch beim Spiel Sim. (de) En combinatoria el teorema de Ramsey establece que en cualquier esquema de color aplicado a un grafo de un grafo completo suficientemente grande, se hallarán subgrafos completos monocromáticos. Para dos colores, el teorema enuncia que para cualquier par de enteros positivos (r,s), existe al menos un entero positivo R(r,s) como aquel para cualquier grafo completo en R(r,s) vértices, cuyas aristas (o ramas) están coloreados de rojo o azul, existe un subgrafo completo de r vértices que es totalmente azul, o un subgrafo completo de s vértices que es totalmente rojo. R(r,s) representa un entero que depende conjuntamente de r y s. Se entiende que representa al entero más pequeño para el que el teorema aplica. A ese número se le llama número de Ramsey. El teorema de Ramsey es fundacional en combinatoria. La primera versión de estos resultados fueron probados por F. P. Ramsey. Esto inició la teoría combinatoria, ahora llamada teoría de Ramsey, que busca regularidad en medio del desorden: condiciones generales para la existencia de subestructuras con propiedades regulares. Una extensión de este teorema se aplica a cualquier número finito de colores, en lugar de solamente dos. Más precisamente, el teorema enuncia que por cualquier número dado de colores «c», y cualquier entero n1,...,nc, existe un número, R(n1, ..., nc), que si las aristas de un grafo completo de orden R(n1, ...,nc) se colorea con c colores diferentes, entonces para algún i entre 1 y c, debe contener un subgrafo completo de orden ni cuyas aristas son de color i. El caso especial de arriba donde c = 2 (y n1 = r y n2 = s). Otra generalización se obtiene al considerar grafos que no sean completos. Son conocidos todos los valores de R(G1,G2) si G1 y G2 tienen a lo más 5 vértices salvo cuando G1 ó G2 es el grafo completo de 5 vértices y el otro es o bien el grafo completo de 5 vértices o bien el grafo completo de 5 vértices menos una arista. (es) In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices. (Here R(r, s) signifies an integer that depends on both r and s.) Ramsey's theorem is a foundational result in combinatorics. The first version of this result was proved by F. P. Ramsey. This initiated the combinatorial theory now called Ramsey theory, that seeks regularity amid disorder: general conditions for the existence of substructures with regular properties. In this application it is a question of the existence of monochromatic subsets, that is, subsets of connected edges of just one colour. An extension of this theorem applies to any finite number of colours, rather than just two. More precisely, the theorem states that for any given number of colours, c, and any given integers n1, …, nc, there is a number, R(n1, …, nc), such that if the edges of a complete graph of order R(n1, …, nc) are coloured with c different colours, then for some i between 1 and c, it must contain a complete subgraph of order ni whose edges are all colour i. The special case above has c = 2 (and n1 = r and n2 = s). (en) En mathématiques, et plus particulièrement en combinatoire, le théorème de Ramsey, dû à Frank Ramsey (en 1930), est un théorème fondamental de la théorie de Ramsey. Il affirme que pour tout n, tout graphe complet suffisamment grand dont les arêtes sont colorées contient des sous-graphes complets de taille n d'une seule couleur. En théorie des ensembles, une de ses généralisations, le théorème de Ramsey infini, permet de définir un type particulier de grand cardinal. (fr) 램지 이론에서 램지의 정리(영어: Ramsey’s theorem)는 충분히 큰 완전 그래프의 변을 색칠할 경우, 동색의 클릭을 찾을 수 있다는 정리이다. (ko) ラムゼーの定理（ラムゼーのていり）とは、数学の組合せ論における次の二つの定理のことである(フランク・ラムゼイ, 1930)。 無限ラムゼーの定理r, sを正の整数とする。相異なるs 個の整数からなる集合全体をどのようにr 個の類に類別しても、ある整数の無限部分集合S が存在し、S に属する相異なる整数s個の集合は全て同一の類に属する。有限ラムゼーの定理s , r , k1, k2, ..., kr をki ≥ s となる非負の整数とする。このとき、次の性質を満たすRが存在する：n≥ Rならば、n 個の元からなる集合Nの s 個の元からなる部分集合全体をr個の類 C1, C2, ..., Crに類別したとき、あるiが存在して、ki個の元からなるNの部分集合で、その中のどの相異なるs 個の元からなる部分集合も類Ciに属するものが存在する。 以下、これを満たす最小のR をRr (s; k1, k2, ..., kr)とおく。 有限ラムゼーの定理は無限ラムゼーの定理から従う。その証明は英語版を参照のこと。 鳩の巣原理から、s=1のとき、Rr (1; k, k, ..., k )=(k -1)r +1ととれる。つまり、ラムゼーの定理は鳩の巣原理の一般化といえる。また、R2 (3, 3)=6は「6人いれば、互いに知り合いである3人組か、互いに知り合いでない3人組が存在する」として有名である。 s=2 とするとき、次の結果が得られる。この結果がラムゼーの定理として言及されることも多い。 r, k1, k2, ..., krを2以上の整数とする。このとき、次の性質を満たすRr (k1, k2, ..., kr)が存在する：n≥ R (k1, k2, ..., kr)ならば、n 個の点からなる完全グラフの辺をどの様にr 色に彩色してもあるi に対して、ki個の点からなる色i の完全グラフが存在する。 ラムゼーの定理に類似した定理として、ファン・デル・ヴェルデンの定理など多くの種類の定理が知られている。最近になって、これらの一般化であるHales-Jewettの定理が発見され、これにより、一連の類似した定理は一つの理論として確立した。 (ja) In combinatoria, il teorema di Ramsey afferma che per ogni colorazione degli archi di un grafo completo con un numero abbastanza elevato di vertici è possibile trovare un sottografo completo monocromatico. Nel caso in cui il grafo sia colorato con soli due colori, per esempio rosso e blu, il teorema di Ramsey afferma che comunque scelti due interi positivi r e s esiste un intero R(r,s) tale per cui in un grafo completo con almeno R(r,s) vertici è sempre possibile, per qualunque colorazione, trovare un sottografo completo totalmente blu con r vertici, o un sottografo completo totalmente rosso con s vertici. Il numero R(r,s) è da intendersi come il più piccolo intero per cui vale questa proprietà, e viene chiamato numero di Ramsey. Il teorema di Ramsey è valido anche per più di due colori: scelto un numero c di colori, per qualunque scelta di interi positivi n1,...,nc esiste un numero R(n1,...,nc) tale per cui in ogni grafo con almeno R(n1,...,nc) vertici è sempre possibile trovare, per un certo i tra 1 e c, un sottografo completo con ni vertici totalmente colorato con il colore i. Il teorema di Ramsey è un risultato fondamentale in combinatoria. La prima versione fu dimostrata da Frank P. Ramsey, e diede inizio a quella che è chiamata teoria di Ramsey. (it) Twierdzenie Ramseya – twierdzenie matematyczne dotyczące teorii grafów, udowodnione przez F. Ramseya. (pl) Em combinatória, o Teorema de Ramsey diz que serão encontrados cliques monocromáticos em qualquer coloração de arestas de um grafo completo suficientemente grande. Para demonstrar o teorema para duas cores (por exemplo azul e vermelho), façamos r e s serem quaisquer inteiros positivos. O Teorema de Ramsey diz que existe um menor inteiro positivo R(r,s) para o qual toda coloração de arestas azul-vermelho de um grafo completo com R(r,s) vértices contem um clique azul em r ou um clique vermelho em s vértices. (Aqui R(r,s) significa um inteiro que depende de ambos r e s.) O Teorema de Ramsey é um resultado fundacional em combinatória. A primeira versão desse resultado foi provada por . Isso iniciou a teoria combinatória agora chamada de Teoria de Ramsey, que busca regularidade em meio a desordem: condições gerais para a existência de subestruturas com propriedades regulares. Nessa aplicação é uma questão da existência de subconjuntos monocromáticos, isto é, subconjuntos de arestas conectadas de apenas uma cor. Uma extensão desse teorema se aplica para qualquer número finito de cores, ao invés de apenas duas. Mais precisamente, o teorema diz que para qualquer número de cores c, e quaisquer inteiros n1,...,nc, existe um número, R(n1, ..., nc), tal que se as arestas de um grafo completo de ordem R(n1, ..., nc) estão coloridas com c cores diferentes, então para algum i entre 1 e c, deve conter um subgrafo completo de ordem ni cujas arestas são todas cores i. O caso especial acima tem c = 2 (e n1 = r e n2 = s). (pt) Теорема Рамсея — теорема, винайдена англійським математиком , стосується комбінаторики, теорії графів та теорії множин. (uk) Теорема Рамсея — теорема комбинаторики о разбиениях множеств, сформулированная и доказанная английским математиком Фрэнком Рамсеем в 1930 году. Встречается в литературе в разных формулировках. Эта теорема положила начало теории Рамсея. (ru) 在組合數學上，拉姆齐定理（英語：Ramsey's theorem），又称拉姆齐二染色定理，斷言對任意正整數和，若一個聚會的人數足夠大，則無論相识關係如何，必定有个人相识或个人互不相识。給定時，保證前述結論的最小值稱為拉姆齊數，其值取決於。用圖論術語複述：若將足夠大的完全圖各邊染紅藍兩色，則不論如何染，必定有紅色的階完全圖或藍色的階完全圖。 拉姆齊定理是組合數學的重要結論，以弗兰克·普伦普顿·拉姆齐命名。他在1930年論文《論形式邏輯的一個問題》證明此定理最初的版本，開創現稱拉姆齊理論的組合理論分支。拉姆齊理論的主題是從「無序」尋找「規律」，希望找出某數學結構中，存在規律子結構的一般條件。在拉姆齊定理的圖論表述中，此「規律子結構」是同色集（monochromatic set），即頂點集的子集，其中各邊皆染成同一顏色。 拉姆齊定理不止一條，前述版本的若干引伸仍稱拉姆齊定理。例如，可以將二染色推廣至更多種色，此時定理斷言：對任意色數，和任意正整數，必有某數，使階的完全圖各邊不論如何染色，仍必可找到某（介於至）和某階完全子圖，其各邊皆染第色。可見拉姆齐二染色定理是的特例（同時取）。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/RamseyTheory_K5_no_mono_K3.svg?width=300 |
| dbo:wikiPageExternalLink | http://ginger.indstate.edu/ge/RAMSEY/index.html https://users.renyi.hu/~p_erdos/1964-22.pdf http://mathworld.wolfram.com/RamseyNumber.html https://web.archive.org/web/20080820012759/http:/www.ramseyathome.com/ramsey/ http://www.numdam.org/article/CM_1935__2__463_0.pdf http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1/pdf |
| dbo:wikiPageID | 184898 (xsd:integer) |
| dbo:wikiPageLength | 56866 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123994962 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Probabilistic_method dbr:Projective_plane dbr:Quantum_Computer dbr:Electronic_Journal_of_Combinatorics dbr:Paris–Harrington_theorem dbr:Tower_of_twos dbr:David_Conlon dbr:Degeneracy_(graph_theory) dbr:András_Hajnal dbr:Annals_of_Mathematics dbr:Paul_Erdős dbr:Peter_Keevash dbr:Reverse_mathematics dbr:Cycle_(graph_theory) dbr:David_Seetapun dbr:Degree_(graph_theory) dbr:Double_counting_(proof_technique) dbr:Independent_set_(graph_theory) dbr:Induced_subgraph dbr:Kőnig's_lemma dbr:Pseudorandom_graph dbc:Articles_containing_proofs dbr:Complete_graph dbr:Countable_set dbr:Mathematical_induction dbr:Endre_Szemerédi dbr:George_Szekeres dbr:Glossary_of_graph_theory dbr:Graph_labeling dbr:Graph_removal_lemma dbr:Erdős–Dushnik–Miller_theorem dbr:Erdős–Rado_theorem dbr:Benny_Sudakov dbr:Star_(graph_theory) dbr:Clebsch_graph dbr:Clique_(graph_theory) dbr:Combinatorics dbr:Compactness_theorem dbr:Compositio_Mathematica dbr:Zermelo–Fraenkel_set_theory dbr:Path_(graph_theory) dbr:Time_complexity dbr:Tree_(graph_theory) dbr:Triangle-free_graph dbr:Distributed_computing dbr:János_Komlós_(mathematician) dbr:Lajos_Pósa_(mathematician) dbr:Large_cardinal dbr:Theorem_on_friends_and_strangers dbr:Brendan_McKay_(mathematician) dbr:Cardinality dbr:Graph_isomorphism dbr:Graph_theory dbr:Proof_by_contradiction dbr:Ramsey_theory dbr:William_Lowell_Putnam_Mathematical_Competition dbc:Theorems_in_graph_theory dbr:Handshaking_lemma dbr:Jacob_Fox dbr:Hypergraph dbc:Ramsey_theory dbr:Jeong_Han_Kim dbr:Joel_Spencer dbr:Big_O_notation dbr:Yoshiharu_Kohayakawa dbr:Burr–Erdős_conjecture dbr:Pigeonhole_principle dbr:Positive_integer dbr:Grover's_algorithm dbr:Miklós_Ajtai dbr:Brute-force_search dbr:Set_(mathematics) dbr:Set_theory dbr:Tom_Bohman dbr:Robert_Morris_(mathematician) dbr:Vojtěch_Rödl dbr:Second-order_arithmetic dbr:Sim_(pencil_game) dbr:Without_loss_of_generality dbr:Ramsey_cardinal dbr:Exponential_growth dbr:Extremal_graph_theory dbr:Stanisław_Radziszowski dbr:Paley_graph dbr:Ramsey_game dbr:Subset dbr:Van_der_Waerden_number dbr:Partition_calculus dbr:Vertex_coloring dbr:Infinite_Ramsey_theory dbr:F._P._Ramsey dbr:File:K_16_partitioned_into_three_Clebsch_graphs.svg dbr:File:RamseyTheory_K5_no_mono_K3.svg dbr:File:Clebsch_graph.svg dbr:File:K_16_partitioned_into_three_Clebsch_graphs_twisted.svg |
| dbp:author | dbr:Joel_Spencer |
| dbp:author1Link | Paul Erdős (en) |
| dbp:first | P. (en) L. (en) |
| dbp:id | p/r077240 (en) |
| dbp:last | Moser (en) Erdős (en) |
| dbp:text | Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for . In that case, he believes, we should attempt to destroy the aliens. (en) |
| dbp:title | Ramsey theorem (en) |
| dbp:wikiPageUsesTemplate | dbt:Springer dbt:Blockquote dbt:Citation dbt:Citation_needed dbt:Efn dbt:Frac dbt:Main dbt:Math dbt:Mvar dbt:Notelist dbt:OEIS dbt:Partial dbt:Reflist dbt:Sfrac dbt:Short_description dbt:Sqrt dbt:Sub dbt:Sup dbt:Tmath dbt:Use_British_English dbt:Wikibooks dbt:Yes dbt:Abs dbt:Harvs dbt:Diagonal_split_header |
| dbp:year | 1964 (xsd:integer) |
| dcterms:subject | dbc:Articles_containing_proofs dbc:Theorems_in_graph_theory dbc:Ramsey_theory |
| rdf:type | yago:WikicatTheoremsInGraphTheory yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| rdfs:comment | En mathématiques, et plus particulièrement en combinatoire, le théorème de Ramsey, dû à Frank Ramsey (en 1930), est un théorème fondamental de la théorie de Ramsey. Il affirme que pour tout n, tout graphe complet suffisamment grand dont les arêtes sont colorées contient des sous-graphes complets de taille n d'une seule couleur. En théorie des ensembles, une de ses généralisations, le théorème de Ramsey infini, permet de définir un type particulier de grand cardinal. (fr) 램지 이론에서 램지의 정리(영어: Ramsey’s theorem)는 충분히 큰 완전 그래프의 변을 색칠할 경우, 동색의 클릭을 찾을 수 있다는 정리이다. (ko) Twierdzenie Ramseya – twierdzenie matematyczne dotyczące teorii grafów, udowodnione przez F. Ramseya. (pl) Теорема Рамсея — теорема, винайдена англійським математиком , стосується комбінаторики, теорії графів та теорії множин. (uk) Теорема Рамсея — теорема комбинаторики о разбиениях множеств, сформулированная и доказанная английским математиком Фрэнком Рамсеем в 1930 году. Встречается в литературе в разных формулировках. Эта теорема положила начало теории Рамсея. (ru) 在組合數學上，拉姆齐定理（英語：Ramsey's theorem），又称拉姆齐二染色定理，斷言對任意正整數和，若一個聚會的人數足夠大，則無論相识關係如何，必定有个人相识或个人互不相识。給定時，保證前述結論的最小值稱為拉姆齊數，其值取決於。用圖論術語複述：若將足夠大的完全圖各邊染紅藍兩色，則不論如何染，必定有紅色的階完全圖或藍色的階完全圖。 拉姆齊定理是組合數學的重要結論，以弗兰克·普伦普顿·拉姆齐命名。他在1930年論文《論形式邏輯的一個問題》證明此定理最初的版本，開創現稱拉姆齊理論的組合理論分支。拉姆齊理論的主題是從「無序」尋找「規律」，希望找出某數學結構中，存在規律子結構的一般條件。在拉姆齊定理的圖論表述中，此「規律子結構」是同色集（monochromatic set），即頂點集的子集，其中各邊皆染成同一顏色。 拉姆齊定理不止一條，前述版本的若干引伸仍稱拉姆齊定理。例如，可以將二染色推廣至更多種色，此時定理斷言：對任意色數，和任意正整數，必有某數，使階的完全圖各邊不論如何染色，仍必可找到某（介於至）和某階完全子圖，其各邊皆染第色。可見拉姆齐二染色定理是的特例（同時取）。 (zh) في التوافقيات، تنص مبرهنة رامزي على أنه بأي تلوين لأضلاع رسم بياني كامل كبير بما فيه الكفاية ، يوجد رسم بياني فرعي كامل أحادي اللون. للونين ، تنص مبرهنة رامزي على أنه لكل زوج من الأعداد الصحيحة الموجبة (r ،s) ، يوجد على الأقل عدد صحيح موجب (R(r ،s ، حيث أنه لأي رسم بياني كامل على (R(r ،s رؤوس ، ملونة أضلاعة بالأحمر أو الأزرق ، إما يوجد رسم بياني فرعي كامل على r رؤوس أضلاعة ملونة بالأزرق، أو رسم بياني فرعي كامل على s رؤوس أضلاعه ملونة بالأحمر. هنا (R(r ،s تعبر عن عدد صحيح الذي يعتمد على كل من r و s. ومن المفهوم تمثيل أصغر عدد صحيح الذي تنطبق عليه المبرهنة. (ar) Der Satz von Ramsey geht auf Frank Plumpton Ramsey und dessen Veröffentlichung aus dem Jahr 1930 zurück. Er zählt zu den klassischen Theoremen der Kombinatorik und stellt eine Verallgemeinerung des dirichletschen Schubfachprinzips dar. Der Satz behandelt die Frage, ob und unter welchen Bedingungen bei Kantenfärbungen von vollständigen Graphen und Hypergraphen mit zwei (oder mehr) Farben einfarbige Teilgraphen auftreten. Es ergibt sich, dass solche Teilgraphen für hinreichend große vollständige Graphen und Hypergraphen stets auftreten müssen. Das derartige Fragestellungen behandelnde Teilgebiet der Kombinatorik wird Ramseytheorie genannt. (de) Στη συνδυαστική, το Θεώρημα Ράμσεϋ δηλώνει ότι σε οποιεσδήποτε χρωματισμένες από ένα αρκετά μεγάλο , θα βρει κανείς μονοχρωματικό πλήρη υπογράφημα. Για δύο χρώματα, το θεώρημα Ramsey αναφέρει ότι για κάθε ζεύγος θετικών ακεραίων (r, s), υπάρχει ένας μικρότερος θετικός ακέραιος R (R, S) τέτοιος ώστε για κάθε 2-χρωματισμούς του R (r, s) κορυφές, υπάρχει ένα πλήρες μονοχρωματικό υπογράφημα είτε r ή s κορυφές. Εδώ R (R, S) σημαίνει έναν ακέραιο που εξαρτάται τόσο από r και s. Είναι κατανοητό να αντιπροσωπεύει το μικρότερο ακέραιο για την οποία το θεώρημα κατέχει. (el) En combinatoria el teorema de Ramsey establece que en cualquier esquema de color aplicado a un grafo de un grafo completo suficientemente grande, se hallarán subgrafos completos monocromáticos. Para dos colores, el teorema enuncia que para cualquier par de enteros positivos (r,s), existe al menos un entero positivo R(r,s) como aquel para cualquier grafo completo en R(r,s) vértices, cuyas aristas (o ramas) están coloreados de rojo o azul, existe un subgrafo completo de r vértices que es totalmente azul, o un subgrafo completo de s vértices que es totalmente rojo. R(r,s) representa un entero que depende conjuntamente de r y s. Se entiende que representa al entero más pequeño para el que el teorema aplica. A ese número se le llama número de Ramsey. (es) In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices. (Here R(r, s) signifies an integer that depends on both r and s.) (en) ラムゼーの定理（ラムゼーのていり）とは、数学の組合せ論における次の二つの定理のことである(フランク・ラムゼイ, 1930)。 無限ラムゼーの定理r, sを正の整数とする。相異なるs 個の整数からなる集合全体をどのようにr 個の類に類別しても、ある整数の無限部分集合S が存在し、S に属する相異なる整数s個の集合は全て同一の類に属する。有限ラムゼーの定理s , r , k1, k2, ..., kr をki ≥ s となる非負の整数とする。このとき、次の性質を満たすRが存在する：n≥ Rならば、n 個の元からなる集合Nの s 個の元からなる部分集合全体をr個の類 C1, C2, ..., Crに類別したとき、あるiが存在して、ki個の元からなるNの部分集合で、その中のどの相異なるs 個の元からなる部分集合も類Ciに属するものが存在する。 以下、これを満たす最小のR をRr (s; k1, k2, ..., kr)とおく。 有限ラムゼーの定理は無限ラムゼーの定理から従う。その証明は英語版を参照のこと。 鳩の巣原理から、s=1のとき、Rr (1; k, k, ..., k )=(k -1)r +1ととれる。つまり、ラムゼーの定理は鳩の巣原理の一般化といえる。また、R2 (3, 3)=6は「6人いれば、互いに知り合いである3人組か、互いに知り合いでない3人組が存在する」として有名である。 (ja) In combinatoria, il teorema di Ramsey afferma che per ogni colorazione degli archi di un grafo completo con un numero abbastanza elevato di vertici è possibile trovare un sottografo completo monocromatico. Il teorema di Ramsey è valido anche per più di due colori: scelto un numero c di colori, per qualunque scelta di interi positivi n1,...,nc esiste un numero R(n1,...,nc) tale per cui in ogni grafo con almeno R(n1,...,nc) vertici è sempre possibile trovare, per un certo i tra 1 e c, un sottografo completo con ni vertici totalmente colorato con il colore i. (it) Em combinatória, o Teorema de Ramsey diz que serão encontrados cliques monocromáticos em qualquer coloração de arestas de um grafo completo suficientemente grande. Para demonstrar o teorema para duas cores (por exemplo azul e vermelho), façamos r e s serem quaisquer inteiros positivos. O Teorema de Ramsey diz que existe um menor inteiro positivo R(r,s) para o qual toda coloração de arestas azul-vermelho de um grafo completo com R(r,s) vértices contem um clique azul em r ou um clique vermelho em s vértices. (Aqui R(r,s) significa um inteiro que depende de ambos r e s.) (pt) |
| rdfs:label | مبرهنة رامزي (ar) Satz von Ramsey (de) Θεώρημα Ράμσεϋ (el) Teorema de Ramsey (es) Teorema di Ramsey (it) Théorème de Ramsey (fr) ラムゼーの定理 (ja) 램지의 정리 (ko) Ramsey's theorem (en) Twierdzenie Ramseya (pl) Teorema Finito de Ramsey (pt) Теорема Рамсея (ru) Теорема Рамсея (uk) 拉姆齐定理 (zh) |
| owl:sameAs | freebase:Ramsey's theorem yago-res:Ramsey's theorem wikidata:Ramsey's theorem dbpedia-ar:Ramsey's theorem dbpedia-de:Ramsey's theorem dbpedia-el:Ramsey's theorem dbpedia-es:Ramsey's theorem dbpedia-fa:Ramsey's theorem dbpedia-fr:Ramsey's theorem dbpedia-he:Ramsey's theorem dbpedia-hu:Ramsey's theorem dbpedia-it:Ramsey's theorem dbpedia-ja:Ramsey's theorem dbpedia-kk:Ramsey's theorem dbpedia-ko:Ramsey's theorem dbpedia-pl:Ramsey's theorem dbpedia-pt:Ramsey's theorem dbpedia-ru:Ramsey's theorem http://ta.dbpedia.org/resource/ராம்சே_தேற்றம் dbpedia-th:Ramsey's theorem dbpedia-uk:Ramsey's theorem dbpedia-zh:Ramsey's theorem https://global.dbpedia.org/id/54Z5S |
| prov:wasDerivedFrom | wikipedia-en:Ramsey's_theorem?oldid=1123994962&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Clebsch_graph.svg wiki-commons:Special:FilePath/K_16_partitioned_into_three_Clebsch_graphs.svg wiki-commons:Special:FilePath/K_16_partitioned_into_three_Clebsch_graphs_twisted.svg wiki-commons:Special:FilePath/RamseyTheory_K5_no_mono_K3.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Ramsey's_theorem |
| is dbo:wikiPageDisambiguates of | dbr:Ramsey |
| is dbo:wikiPageRedirects of | dbr:Ramsey's_Theorem dbr:Ramsey_number dbr:R(5,_5) dbr:Ramsey_Number dbr:Ramsey_numbers dbr:Ramsey_theorem |
| is dbo:wikiPageWikiLink of | dbr:Probabilistic_method dbr:Paris–Harrington_theorem dbr:Binary_logarithm dbr:List_of_graph_theory_topics dbr:Reverse_mathematics dbr:Richard_Rado dbr:Ultrafilter_(set_theory) dbr:David_Seetapun dbr:Dependent_random_choice dbr:Infinitary_combinatorics dbr:List_of_mathematical_proofs dbr:17_(number) dbr:Frank_Ramsey_(mathematician) dbr:Erdős–Dushnik–Miller_theorem dbr:Erdős–Hajnal_conjecture dbr:Erdős–Rado_theorem dbr:Erdős–Szekeres_theorem dbr:Milliken's_tree_theorem dbr:Liu_Lu dbr:Claw-free_graph dbr:Clique_(graph_theory) dbr:Clique_game dbr:Combinatorial_Geometry_in_the_Plane dbr:Combinatorics dbr:János_Komlós_(mathematician) dbr:Theorem_on_friends_and_strangers dbr:Aaron_Robertson_(mathematician) dbr:45_(number) dbr:Edge_coloring dbr:Partition_regularity dbr:Ramsey dbr:Ramsey_theory dbr:Hypergraph dbr:Ehrenfeucht–Mostowski_theorem dbr:Homogeneous_(large_cardinal_property) dbr:Jean_A._Larson dbr:Burr–Erdős_conjecture dbr:Pigeonhole_principle dbr:Miklós_Ajtai dbr:Ramsey's_Theorem dbr:Ramsey_number dbr:Set_theory dbr:Ramsey_cardinal dbr:IP_set dbr:List_of_theorems dbr:Low_(computability) dbr:Milliken–Taylor_theorem dbr:Monochromatic_triangle dbr:Polyadic_space dbr:Packing_in_a_hypergraph dbr:Ramsey-Turán_theory dbr:Ramsey_class dbr:Χ-bounded dbr:Slicing_the_Truth dbr:Strong_positional_game dbr:Structural_Ramsey_theory dbr:R(5,_5) dbr:Ramsey_Number dbr:Ramsey_numbers dbr:Ramsey_theorem |
| is rdfs:seeAlso of | dbr:Ramsey-Turán_theory |
| is foaf:primaryTopic of | wikipedia-en:Ramsey's_theorem |
