In combinatorics, Ramsey's theorem states that in any colouring of the edges of a sufficiently large complete graph (that is, a simple graph in which an edge connects every pair of vertices), one will find monochromatic complete subgraphs.

PropertyValue
dbpprop:abstract
  • In combinatorics, Ramsey's theorem states that in any colouring of the edges of a sufficiently large complete graph (that is, a simple graph in which an edge connects every pair of vertices), one will find monochromatic complete subgraphs. For 2 colours, Ramsey's theorem states that for any pair of positive integers (r,s), there exists a least positive integer R(r,s) such that for any complete graph on R(r,s) vertices, whose edges are coloured red or blue, there exists either a complete subgraph on r vertices which is entirely blue, or a complete subgraph on s vertices which is entirely red. Here R(r,s) signifies an integer that depends on both r and s. It is understood to represent the smallest integer for which the theorem holds. 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).
  • Der Satz von Ramsey beantwortet die Frage, ob in einem Graphen zwingend gewisse Unterstrukturen auftreten. Genauer werden gefärbte vollständige Graphen auf das Auftreten monochromatischer Teilgraphen hin betrachtet, und es stellt sich heraus, dass solche für hinreichend große Graphen tatsächlich auftreten müssen. Eine praktische Anwendung ist das Spiel Sim. Erheblich schwieriger als die reine Existenzaussage gestaltet sich die genaue Quantifizierung, was hierbei als „hinreichend groß“ zu betrachten ist, d. h. die genaue Berechnung oder wenigstens Abschätzung der Ramsey-Zahlen.
  • Ramsey tétele a kombinatorika, de tulajdonképpen a matematika egészének egyik legfontosabb tétele.
  • ラムゼーの定理とは、次の二つの定理である。 （無限ラムゼーの定理）r, sを正の整数とする。s 個の整数の組をどのようにr 通りに類別しても、ある無限集合S が存在し、S に属する整数からなるs個の組は全て同一の類に属する。 （有限ラムゼーの定理）k, s, r をk ≥ s となる非負の整数とする。n 個の元からなる集合の s 個の元からなる部分集合をr 通りに類別する。このとき、次の性質を満たすRが存在する：n≥ Rならば、k個の元からなる部分集合で、その中のどのs 個の元からなる部分集合も同じ類に属するものが存在する。 以下、これを満たす最小のn を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 の完全グラフが存在する。 ラムゼーの定理に類似した定理として、ファン・デル・ヴェルデンの定理など多くの種類の定理が知られている。最近になって、これらの一般化であるが発見され、これにより、一連の類似した定理は一つの理論として確立した。
  • Klasyczne Liczby Ramseya związane są z kolorowaniem krawędzi grafu pełnego:
  • Теорема Рамсея — теорема теории множеств, открытая Франком Рамсеем, которая гласит: Пусть p, q и r — натуральные числа, причем p, q <math>\ge</math> r. Тогда существует число N = N(p, q, r), обладающее следующим свойством: если все r-элементные подмножества N-элементного множества S произвольным образом разбиты на два непересекающихся семейства <math>\alpha</math> и <math>\beta</math>, то либо существует p-элементное подмножество множества S, все r-элементные подмножества которого содержатся в <math>\alpha</math>, либо существует q-элементное подмножество, все r-элементные подмножества которого содержатся в <math>\beta</math>.
  • 在組合數學上，拉姆齐(Ramsey)定理是要解決以下的問題：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。 這個定理以弗兰克·普伦普顿·拉姆齐命名，1930年他在論文On a Problem in Formal Logic（《形式邏輯上的一個問題》）證明了R(3,3)=6。
dbpprop:hasPhotoCollection
dbpprop:reference
dbpprop:wikiPageUsesTemplate
dbpprop:wikibooksProperty
  • Bounds for Ramsey numbers
  • Combinatorics
  • Ramsey numbers
rdfs:comment
  • In combinatorics, Ramsey's theorem states that in any colouring of the edges of a sufficiently large complete graph (that is, a simple graph in which an edge connects every pair of vertices), one will find monochromatic complete subgraphs.
  • Der Satz von Ramsey beantwortet die Frage, ob in einem Graphen zwingend gewisse Unterstrukturen auftreten. Genauer werden gefärbte vollständige Graphen auf das Auftreten monochromatischer Teilgraphen hin betrachtet, und es stellt sich heraus, dass solche für hinreichend große Graphen tatsächlich auftreten müssen. Eine praktische Anwendung ist das Spiel Sim.
  • Ramsey tétele a kombinatorika, de tulajdonképpen a matematika egészének egyik legfontosabb tétele.
  • Klasyczne Liczby Ramseya związane są z kolorowaniem krawędzi grafu pełnego:
  • Теорема Рамсея — теорема теории множеств, открытая Франком Рамсеем, которая гласит: Пусть p, q и r — натуральные числа, причем p, q <math>\ge</math> r.
  • 在組合數學上，拉姆齐(Ramsey)定理是要解決以下的問題：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。 這個定理以弗兰克·普伦普顿·拉姆齐命名，1930年他在論文On a Problem in Formal Logic（《形式邏輯上的一個問題》）證明了R(3,3)=6。
rdfs:label
  • Ramsey's theorem
  • Satz von Ramsey
  • Ramsey-tétel
  • ラムゼーの定理
  • Liczby Ramseya
  • Теорема Рамсея
  • 拉姆齐定理
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of