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

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

تمت برهنة المبرهنة على يد بول إيردوس وجورج سيكريس في مقال لهما سنة 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 متتالية جزئية متناقصة مكونة من كل الأعداد

برهان

عدل

يمكن برهنة مبرهنة إيردوس-سيكريس بالعديد من الطرق; steele (1995) عاين ستة براهين مختلفة لمبرهنة إيردوس-سيكريس، بما في ذلك البرهان التالي. [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 على الأقل.

انظر أيضا

عدل

مراجع

عدل
  1. ^ Steele، J. Michael (1995)، "Variations on the monotone subsequence theme of Erdős and Szekeres"، في Aldous، David؛ Diaconis، Persi؛ Spencer، Joel؛ Steele، J. Michael (المحررون)، Discrete Probability and Algorithms (PDF)، IMA Volumes in Mathematics and its Applications، Springer-Verlag، ج. 72، ص. 111–131، مؤرشف من الأصل (PDF) في 2019-06-11.

وصلات خارجية

عدل