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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم صناعة الشبابيك يستعرض أعماله للمشاركين في البرنامج المركزي الأسبوعي

جامعة الكفيل تنظم حملة للتبرع بالدم للأطفال المصابين بالثلاسيميا والأورام السرطانية

قسم الشؤون الفكرية يصدر العدد 55 من مجلة العميد المحكمة

المجمع العلمي يجري اختبار القبول للمتقدمين إلى دورة ربيع القرآن في كربلاء

المزيد

الآخبار الصحية

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

الآخبار التكنلوجية

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength