Erdős–Szekeres theorem
ریاضی میں، ایرڈس-زیکیرس تھیوریم اس بات پر زور دیتا ہے کہ، r، s دیئے جانے پر، کم از کم (r−1) (s−1) + 1 لمبائی والے مختلف حقیقی اعداد کی کسی بھی ترتیب میں لمبائی r کا یکسانیت سے بڑھتا ہوا تسلسل یا لمبائی s کا یکسانیت سے کم ہوتا ہوا تسلسل ہوتا ہے۔ ثبوت اسی 1935 کے مقالے میں شائع ہوا جس میں خوشی کے خاتمے کے مسئلے کا ذکر کیا گیا ہے۔ یہ ایک حتمی نتیجہ ہے جو رمسی کے نظریہ کے عین مطابق نتائج میں سے ایک بناتا ہے۔ اگرچہ رمسی کا نظریہ یہ ثابت کرنا آسان بناتا ہے کہ مختلف حقیقی اعداد کی ہر لامحدود ترتیب میں یکسوئی سے بڑھتی ہوئی لامحدود تسلسل یا یکسوئی سے کم ہوتی ہوئی لامحدود تسلسل ہوتی ہے، لیکن پال ایرڈس اور جارج زیکیرس کے ذریعہ ثابت کردہ نتیجہ مزید آگے جاتا ہے۔ مثال r = 3 اور s = 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 کی تین کم ہوتی ہوئی لمبائی-2 کے تسلسل ہیں، 3,2,3,1 اور 2,1۔ جیومیٹرک تشریح کوئی بھی ایک ترتیب میں اعداد کی پوزیشنوں کی تشریح یوکلڈین سطح میں پوائنٹس کے x-کوآرڈینیٹس کے طور پر کر سکتا ہے، اور اعداد خود y-کوآرڈینیٹس کے طور پر ؛ اس کے برعکس، سطح میں مقرر کردہ کسی بھی نقطہ کے لیے، پوائنٹس کے y-کوآرڈینیٹس، جو ان کے x-کوآرڈینیٹس کے ذریعے ترتیب دیے جاتے ہیں، اعداد کی ترتیب بناتے ہیں (جب تک کہ دو پوائنٹس کے مساوی x-کوآرڈینیٹس نہ ہوں)۔ ترتیبات اور پوائنٹ سیٹوں کے درمیان اس ترجمہ کے ساتھ، ایرڈس-زیکیرس تھیوریم کی تشریح اس طرح کی جا سکتی ہے کہ کم از کم rs−r−s + 2 پوائنٹس کے کسی بھی سیٹ میں ہم r−1 مثبت-ڈھلوان کناروں یا s−1 منفی-ڈھلوان کناروں کا کثیر الاضحی راستہ تلاش کر سکتے ہیں۔ خاص طور پر (r = s لیتے ہوئے)، کم از کم n پوائنٹس کے کسی بھی سیٹ میں ہم ایک ہی نشان والی ڈھلوانوں کے ساتھ کم از کم θ θ کناروں کا کثیر الاضحی راستہ تلاش کر سکتے ہیں۔ مثال کے طور پر، r = s = 5 لیتے ہوئے، کم از کم 17 نکات کے کسی بھی سیٹ میں چار کنارے والا راستہ ہوتا ہے جس میں تمام ڈھلوانوں کی علامت ایک جیسی ہوتی ہے۔ اس طرح کے راستے کے بغیر rs−r−s + 1 پوائنٹس کی ایک مثال، جس سے یہ ظاہر ہوتا ہے کہ یہ باؤنڈ تنگ ہے، ایک (r−1) بائی (s−1) گرڈ پر ایک چھوٹی سی گردش لگا کر تشکیل دی جا سکتی ہے۔ ترتیب کے نمونوں کی تشریح ایرڈس-زیکیرس تھیوریم کی تشریح ترتیب کے نمونوں کی زبان میں بھی کی جا سکتی ہے جس میں کہا گیا ہے کہ کم از کم rs + 1 لمبائی کے ہر ترتیب میں یا تو نمونہ 1، 2، 3،.، r + 1 یا نمونہ s + 1، s،.، 2، 1 ہونا چاہیے۔ ثبوت ایردوس زیکیرس تھیوریم کو کئی مختلف طریقوں سے ثابت کیا جا سکتا ہے۔ ایردوس زیکریس تھیوریم کے چھ مختلف ثبوتوں کا جائزہ لیتے ہیں، جن میں درج ذیل دو شامل ہیں۔ اسٹیل کے ذریعہ سروے کیے گئے دیگر شواہد میں ایرڈس اور زیکیرس کے ساتھ ساتھ، اور کے اصل ثبوت شامل ہیں۔ کبوتر سوراخ کا اصول لمبائی (r−1) (s−1) + 1 کی ترتیب کو دیکھتے ہوئے، ہر نمبر ni کو جوڑے (एआइ، بی) کے ساتھ ترتیب میں لیبل کریں، جہاں اے آئی سب سے طویل یک سنگی طور پر بڑھتے ہوئے تسلسل کی لمبائی ہے جو این آئی کے ساتھ ختم ہوتی ہے اور بی آئی سب سے طویل یک سنگی طور پر کم ہونے والے تسلسل کی لمبائی ہے جو این آئی کے ساتھ ختم ہوتی ہے۔ ترتیب میں ہر دو نمبروں کو ایک مختلف جوڑے کے ساتھ لیبل کیا جاتا ہے: اگر اور پھر، اور دوسری طرف اگر پھر۔ لیکن صرف (r−1) (s−1) ممکنہ لیبل ہوتے ہیں اگر ai زیادہ سے زیادہ r−1 ہو اور b زیادہ سے زیادہ s−1 ہو، تو کبوتر کے سوراخ کے اصول کے مطابق i کی ایک قیمت موجود ہونی چاہیے جس کے لیے ai یا b اس حد سے باہر ہو۔ اگر اے آئی حد سے باہر ہے تو این آئی کم از کم آر لمبائی کی بڑھتی ہوئی ترتیب کا حصہ ہے، اور اگر بی آئی حد سے باہر ہے تو این آئی کم از کم ایس لمبائی کی گھٹتی ہوئی ترتیب کا حصہ ہے۔ اس ثبوت کو ایک صفحے کے کاغذ کو کریڈٹ کرتا ہے اور اسے اپنے سروے کے ثبوتوں میں "سب سے تیز اور منظم" کہتا ہے۔ دل ورتھ تھیوریم ثبوتوں میں سے ایک جزوی ترتیب میں زنجیر کے سڑنے پر دل ورتھ کے تھیوریم کا استعمال کرتا ہے، یا اس کا آسان ڈوئل (مرسکی کا تھیوریم)۔ نظریہ کو ثابت کرنے کے لیے، ترتیب کے ممبروں پر جزوی ترتیب کی وضاحت کریں، جس میں x جزوی ترتیب میں y سے کم یا برابر ہے اگر x ≤ y اعداد کے طور پر اور x ترتیب میں y سے بعد میں نہیں ہے۔ اس جزوی ترتیب میں ایک سلسلہ یک سنگی طور پر بڑھتا ہوا تسلسل ہے، اور ایک اینٹیچین یک سنگی طور پر کم ہوتا ہوا تسلسل ہے۔ مرسکی کے نظریہ کے مطابق، یا تو لمبائی r کا ایک سلسلہ ہوتا ہے، یا ترتیب کو زیادہ سے زیادہ r−1 اینٹی چینز میں تقسیم کیا جا سکتا ہے۔ لیکن اس صورت میں اینٹی چینز میں سے سب سے بڑے کو کم از کم لمبائی کے ساتھ کم ہوتے ہوئے تسلسل کی تشکیل کرنی چاہیے۔ متبادل طور پر، خود دل ورتھ کے نظریہ کے مطابق، یا تو لمبائی s کا ایک اینٹی چین ہے، یا ترتیب کو زیادہ سے زیادہ s−1 زنجیروں میں تقسیم کیا جا سکتا ہے، جن میں سے سب سے طویل کی لمبائی کم از کم r ہونی چاہیے۔ رابنسن-شینسٹڈ خط و کتابت کا اطلاق نتیجہ رابنسن-شینسٹڈ خط و کتابت کے نتیجہ کے طور پر بھی حاصل کیا جا سکتا ہے۔ یاد رکھیں کہ رابنسن-شینسٹڈ خط و کتابت ہر ترتیب کو ایک نوجوان جھانکی پی سے جوڑتا ہے جس کی اندراجات ترتیب کی اقدار ہیں۔ جھانکی P میں درج ذیل خصوصیات ہیں: سب سے طویل بڑھتے ہوئے تسلسل کی لمبائی P کی پہلی قطار کی لمبائی کے برابر ہے۔ سب سے طویل گھٹتے ہوئے تسلسل کی لمبائی P کے پہلے کالم کی لمبائی کے برابر ہے۔ اب، سائز کے مربع خانے (r−1) (s−1) میں (r−1) (s−1) + 1 اندراجات کو فٹ کرنا ممکن نہیں ہے، تاکہ یا تو پہلی صف کم از کم r کی لمبائی کی ہو یا آخری صف کم از کم s کی لمبائی کی ہو۔ سب سے طویل بڑھتے ہوئے تسلسل کے مسئلے کو بھی دیکھیں۔ بیرونی روابط رمسی تھیوری پرموٹیشن پیٹرن کے حوالہ جات غیر متزلزل جیومیٹری میں قطعات ثبوت زیکیرس تھیوریم پر مشتمل مضامین مجرد ریاضی میں نظریات