Ramsey Theory

The mathematical study of combinatorial objects in which a certain degree of order must occur as the scale of the object becomes large. Ramsey theory is named after Frank Plumpton Ramsey, who did seminal work in this area before his untimely death at age 26 in 1930. The theory was subsequently developed extensively by Erdős.

The classical problem in Ramsey theory is the party problem, which asks the minimum number of guests  that must be invited so that at least  will know each other (i.e., there exists a clique of order ) or at least  will not know each other (i.e., there exists an independent set of order . Here,  is called a Ramsey number.

A typical result in Ramsey theory states that if some mathematical object is partitioned into finitely many parts, then one of the parts must contain a subobject of an interesting kind. For example, it is known that if  is large enough and  is an -dimensional vector space over the field of integers (mod ), then however  is partitioned into  pieces, one of the pieces contains an affine subspace of dimension .

---

REFERENCES

Burr, S. A. "Generalized Ramsey Theory for Graphs--A Survey." In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). New York: Springer-Verlag, pp. 52-75, 1974.

Erdős, P. and Szekeres, G. "On Some Extremum Problems in Elementary Geometry." Ann. Univ. Sci. Budapest Eőtvős Soc. Math. 3-4, 53-62, 1961.

Graham, R. L. and Nešetril, J. "Ramsey Theory in the Work of Paul Erdős." In The Mathematics of Paul Erdős (Ed. R. L. Graham and J. Nešetril). Heidelberg, Germany: Springer-Verlag, 1996.

Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, pp. 51-57, 1998.

اخر الاخبار

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

مجموعة العميد التربوية تعقد اجتماعًا لمناقشة الاستعدادات الخاصة بالموسم التدريبي الصيفي

قسم الإعلام ينظم ورشة تدريبية حول تطبيق (إعلامي) لعدد من منتسبي قسم حفظ النظام

قسم الشؤون الخدمية ينفذ حملة لتنظيف الشوارع المحيطة بصحن مرقد أبي الفضل العباس (عليه السلام)

وفد العتبة العباسية المقدسة يزور شعبة الإعداد البدني للاطّلاع على برنامج تأهيل المنتسبين الجدد

المزيد

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

ماذا يحدث إذا تناولنا الطعام مرة واحدة فقط في اليوم

اكتشاف عوامل خطر غير متوقعة لمرض الكبد الدهني

فيروس هانتا والسفينة الموبوءة.. تحديث من الصحة العالمية

طبيب يحسم الجدل السجائر الإلكترونية وعلاقتها بالسرطان

المزيد

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

لأول مرة في الولايات المتحدة.. تشغيل مفاعل مصغر نووي يغذي الذكاء الاصطناعي بالطاقة

الكشف عن تفاصيل أول عملية ناجحة لاستعادة انتاج الحيوانات المنوية

أطلس يكشف خفايا الجسم البشري بدقة أرفع بـ50 مرة من شعر الإنسان

المتحف المصري الكبير يتحول إلى "أيقونة خضراء" بدعم ياباني

المزيد

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

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