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

[[ملف:Monotone-subseq-17-5.svg|تصغير|240بك]]

في [[رياضيات|الرياضيات]]، تنص ''' مبرهنة إيردوس-سيكريس''' على أنه في كل [[متتالية]] مكونة من [[عدد حقيقي|أعداد حقيقية]] بطول <math> rs + 1</math>، يوجد لها متتالية جزئية متزايدة بطول <math> r + 1</math> أو متتالية جزئية متناقصة بطول <math> s + 1</math>. هذه المبرهنة هي مبرهنة مثالية في [[نظرية رامزي|نظرية رمزي]]، التي تبحث الانتظام وسط الفوضى.

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

== برهان ==

يمكن برهنة مبرهنة إيردوس-سيكريس بالعديد من الطرق; {{Harvard citation text|steele|1995}} عاين ستة براهين مختلفة لمبرهنة إيردوس-سيكريس، بما في ذلك البرهان التالي.
<ref name="steele">{{استشهاد
 | الأخير = Steele | الأول = J. Michael
 | الفصل = Variations on the monotone subsequence theme of Erdős and Szekeres
 | محرر1-الأخير = Aldous | محرر1-الأول = David
 | محرر2-الأخير = Diaconis | محرر2-الأول = Persi
 | محرر3-الأخير = Spencer | محرر3-الأول = Joel 
 | محرر4-الأخير = Steele | محرر4-الأول = J. Michael
 | صفحات = 111–131
 | ناشر = Springer-Verlag
 | سلسلة = IMA Volumes in Mathematics and its Applications
 | عنوان = Discrete Probability and Algorithms
 | مسار = http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/VOTMSTOEAS.pdf
 | المجلد = 72
 | سنة = 1995|مسار أرشيف= https://web.archive.org/web/20190611133100/http://www-stat.wharton.upenn.edu/%7Esteele/Publications/PDF/VOTMSTOEAS.pdf|تاريخ أرشيف=2019-06-11}}.</ref>

=== مبدأ برج الحمام ===
إذا كانت معطاه متتالية بطول rs + 1، نميز كل عدد n<sub>i</sub> في المتتالية بالزوج (a<sub>i</sub>,b<sub>i</sub>)، بحيث أن a<sub>i</sub> هو طول أطول متتالية متزايدة تنتهي بـ n<sub>i</sub> و b<sub>i</sub> هو طول أطول ممتالية متناقصة تنتهي بـ ,n<sub>i</sub>.
كل عددين في المتتالية مميزين بزوج مختلف:
* إذا كان i < j و n<sub>i</sub> < n<sub>j</sub> إذن a<sub>i</sub> < a<sub>j</sub>
* إذا كان i < j و n<sub>i</sub> > n<sub>j</sub> إذن b<sub>i</sub> < b<sub>j</sub>

ولكن هنالك rs علامة مميّزة بحيث أن a<sub>i</sub> على الأكثر r و b<sub>i</sub> على الأكثر s، ولذلك وفقا ل[[مبدأ برج الحمام]] يجب أن تكون قيمة i بحيث a<sub>i</sub> أو b<sub>i</sub> خارج المجال. إذا كانت a<sub>i</sub> خارج المجال إذن n<sub>i</sub> هي جزء من متتالية متزايدة بطول 1 + r على الأقل، وإذا كانت b<sub>i</sub> خارج المجال إذن n<sub>i</sub> هي جزء من متتالية متناقصة بطول 1 + s على الأقل.

== انظر أيضا ==

* [[مبرهنة رامزي|مبرهنة رمزي]]

== مراجع ==

{{مراجع}}

== وصلات خارجية ==

* {{ماثوورلد | urlname = Erdos-SzekeresTheorem | title = Erdős-Szekeres Theorem}}
{{شريط بوابات|رياضيات|علوم}}

{{بذرة رياضيات}}

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