Ramsey,s Theorem
المؤلف:
Borwein, J. and Bailey, D
المصدر:
Mathematics by Experiment: Plausible Reasoning in the 21st Century.
الجزء والصفحة:
...
18-5-2022
1948
Ramsey's Theorem
Ramsey's theorem is a generalization of Dilworth's lemma which states for each pair of positive integers 
and 
there exists an integer 
(known as the Ramsey number) such that any graph with 
nodes contains a clique with at least 
nodes or an independent set with at least 
nodes.
Another statement of the theorem is that for integers 
, there exists a least positive integer 
such that no matter how the complete graph 
is two-colored, it will contain a green subgraph 
or a red subgraph 
.
A third statement of the theorem states that for all 
, there exists an 
such that any complete digraph on 
graph vertices contains a complete vertex-transitive subgraph of 
graph vertices.
For example, 
and 
, but 
are only known to lie in the ranges 
and 
.
It is true that
if 
.
REFERENCES
Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century.
Wellesley, MA: A K Peters, pp. 33-34, 2003.
Graham, R. L.; Rothschild, B. L.; and Spencer, J. H. Ramsey Theory, 2nd ed. New York: Wiley, 1990.
Mileti, J. "Ramsey's Theorem." http://www.math.uiuc.edu/~mileti/Museum/ramsey.html.Spencer, J. "Large Numbers and Unprovable Theorems." Amer. Math. Monthly 90, 669-675, 1983.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
