مبرهنة إيردوس-سيكريس

في الرياضيات، تنص  مبرهنة إيردوس-سيكريس على أنه في كل متتالية مكونة من أعداد حقيقية بطول ، يوجد لها متتالية جزئية متزايدة بطول  أو متتالية جزئية متناقصة بطول . هذه المبرهنة هي مبرهنة مثالية في نظرية رمزي، التي تبحث الانتظام وسط الفوضى.

تمت برهنة المبرهنة على يد بول إيردوس وجورج سيكريس في مقال لهما سنة 1935.

مثال 
لـ r = 1 و s = 2، تخبرنا الصيغة بأنه لأي تبديل من 3 أعداد يوجد متتالية جزئية متزايدة بطون 3 أو متتالية جزئية متناقصة بطول 2. ننظر إلى جميع التبديلات من الأعداد 1,2,3:
 1,2,3 متتالية جزئية متزايدة مكونة من كل الأعداد
 1,3,2 يملك متتالية جزئية متناقصة 3,2
 2,1,3 يملك متتالية جزئية متناقصة 2,1
 2,3,1 يملك متتاليتين متناقصين 2,1 و 3,1
 3,1,2 يملك متتاليتين متناقصين 3,1 و 3,2
 3,2,1 متتالية جزئية متناقصة مكونة من كل الأعداد

برهان 
يمكن برهنة مبرهنة إيردوس-سيكريس بالعديد من الطرق;  عاين ستة براهين مختلفة لمبرهنة إيردوس-سيكريس، بما في ذلك البرهان التالي.

مبدأ برج الحمام 
إذا كانت معطاه متتالية بطول rs + 1، نميز كل عدد ni في المتتالية بالزوج (ai,bi)، بحيث أن ai هو طول أطول متتالية متزايدة تنتهي بـ ni و bi هو طول أطول ممتالية متناقصة تنتهي بـ ,ni.
كل عددين في المتتالية مميزين بزوج مختلف:
 إذا كان i < j و ni < nj إذن ai < aj
 إذا كان i < j و ni > nj إذن bi < bj

ولكن هنالك rs علامة مميّزة بحيث أن ai على الأكثر r و bi على الأكثر s، ولذلك وفقا لمبدأ برج الحمام يجب أن تكون قيمة i بحيث ai أو bi خارج المجال. إذا كانت ai خارج المجال إذن ni هي جزء من متتالية متزايدة بطول 1 + r على الأقل، وإذا كانت bi خارج المجال إذن ni هي جزء من متتالية متناقصة بطول 1 + s على الأقل.

انظر أيضا 
مبرهنة رمزي

مراجع

وصلات خارجية 
 

بول إيردوس
مبرهنات في الرياضيات المتقطعة
مبرهنات في الهندسة المتقطعة
مقالات تحوي براهين
نظرية رامزي