Ramsey-Turán theory
رمسی-ٹورن نظریہ انتہائی گراف نظریہ کا ایک ذیلی میدان ہے۔ یہ رمسی کے نظریہ اور توران کے نظریہ کی عام عامیوں کا مطالعہ کرتا ہے۔ مختصر طور پر، رمسی-ٹورن نظریہ ایک گراف کے کناروں کی زیادہ سے زیادہ تعداد کا مطالبہ کرتا ہے جو اس کے ذیلی گراف اور ساخت پر موجود رکاوٹوں کو پورا کرتا ہے۔ یہ نظریہ بہت سے قدرتی سوالات کو منظم کرتا ہے جو انتہائی گراف تھیوری میں پیدا ہوتے ہیں۔ نظریہ کے مرکزی نظریات کو باقاعدہ بنانے والے پہلے مصنفین 1969 میں ایرڈس اور سوس تھے، حالانکہ ریاضی دانوں نے اس سے قبل رمسی-ٹورن قسم کے بہت سے مسائل کی تحقیقات کی تھیں۔ رمسی کا نظریہ اور دو رنگوں اور مکمل گراف کے لیے ٹورن کا نظریہ رمسی کا نظریہ، جو 1930 میں اپنی اصل شکل میں ثابت ہوا، کہتا ہے کہ کسی بھی مثبت عدد کے لیے اتنا بڑا عدد موجود ہوتا ہے کہ دو رنگوں کا استعمال کرتے ہوئے مکمل گراف کے کناروں کے کسی بھی رنگ کے لیے اس کی یک رنگ کاپی ہوتی ہے۔ زیادہ عام طور پر، کسی بھی گراف کے لیے، ایک حد ہوتی ہے کہ اگر اور اس کے کناروں کو رنگوں کے ساتھ من مانی طور پر رنگ دیا جائے، تو کچھ کے لیے th رنگ میں a ہوتا ہے۔ ٹورن کا نظریہ، جو 1941 میں ثابت ہوا، اس گراف کی خصوصیت کرتا ہے جس میں عمودی کناروں کی زیادہ سے زیادہ تعداد ہوتی ہے جس میں a نہیں ہوتا ہے۔ خاص طور پر، تھیوریم میں کہا گیا ہے کہ تمام مثبت انٹیجرز کے لیے،-ورٹیکس گراف کے کناروں کی تعداد جو ذیلی گراف کے طور پر نہیں ہوتی ہے زیادہ سے زیادہ ہوتی ہے اور یہ کہ زیادہ سے زیادہ تر تران گراف کے ذریعے منفرد طور پر حاصل کیا جاتا ہے۔ یہ دونوں کلاسیکی نتائج اس بارے میں سوالات پوچھتے ہیں کہ گراف کسی خاص خاصیت کے حامل ہونے سے پہلے کتنا بڑا ہو سکتا ہے۔ تاہم، ایک قابل ذکر طرز کا فرق ہے۔ توران کے نظریہ میں انتہائی گراف کی ایک بہت سخت ساخت ہے، جس میں ایک چھوٹا کرومیٹک نمبر ہوتا ہے اور اس میں بڑی آزاد سیٹوں کی ایک چھوٹی سی تعداد ہوتی ہے۔ دوسری طرف، رمسی کے مسائل میں زیر غور گراف مکمل گراف ہے، جس میں بڑا کرومیٹک نمبر ہوتا ہے اور کوئی غیر معمولی آزاد سیٹ نہیں ہوتا ہے۔ ان دو قسم کے مسائل کو یکجا کرنے کا ایک فطری طریقہ مندرجہ ذیل سوال پوچھنا ہے، جو آندرس فائی نے پیش کیا ہے: مسئلہ 1: کسی دیئے گئے مثبت عدد کے لیے، ایک-ورٹیکس گراف ہونا چاہیے جس میں آزادی نمبر نہ ہو۔ اس طرح کے گراف میں کناروں کی زیادہ سے زیادہ تعداد کتنی ہو سکتی ہے؟ بنیادی طور پر، یہ سوال رمسی کی ترتیب میں توران کے مسئلے کا جواب پوچھتا ہے۔ یہ توران کے مسئلے کو کم منظم، زیادہ بے ترتیب ساخت والے گراف کے ذیلی سیٹ تک محدود کرتا ہے۔ مندرجہ ذیل سوال مسائل کو مخالف سمت میں جوڑتا ہے: مسئلہ 2: طے شدہ گراف ہونے دیں۔ چوٹیوں پر ایک کنارے والے رنگ کے گراف کے کناروں کی زیادہ سے زیادہ تعداد اس شرط کے تحت ہو سکتی ہے کہ اس میں th رنگ میں an نہ ہو؟ عام مسئلہ رامسی-ٹورن تھیوری کی ریڑھ کی ہڈی مندرجہ بالا مسائل کی عام عمومی کاری ہے۔ مسئلہ 3: گراف کو فکسڈ ہونے دیں۔ (1) (2) نویں رنگ کے ذریعہ بیان کردہ ذیلی گراف کو مطمئن کرنے والا-کنارے رنگ کا-ورٹیکس گراف ہونا چاہیے جس میں نمبر ہے۔ کناروں کی زیادہ سے زیادہ تعداد کتنی ہو سکتی ہے؟ ہم زیادہ سے زیادہ کی طرف اشارہ کرتے ہیں۔ رمسی-ٹورن قسم کے مسائل مسئلہ 3 کے خصوصی معاملات ہیں۔ اس مسئلے کے بہت سے معاملات کھلے رہتے ہیں، لیکن کئی دلچسپ معاملات کو عین مطابق غیر علامتی حل کے ساتھ حل کیا گیا ہے۔ قابل ذکر نتائج مسئلہ 3 کو تین مختلف صورتوں میں تقسیم کیا جا سکتا ہے، جو آزادی نمبر پر پابندی پر منحصر ہے۔ وہاں پابندی سے پاک کیس ہے، جہاں، جو کلاسک رمسی کے مسئلے کو کم کرتا ہے۔ "انٹرمیڈیٹ" کیس ہے، جہاں فکسڈ کے لیے ہے۔ آخر میں، ایک معاملہ ہے، جس میں سب سے امیر مسائل شامل ہیں۔ رینج میں سب سے بنیادی غیر معمولی مسئلہ یہ ہے کہ جب ایرڈس اور سوس نے 1969 میں اس صورتحال میں رمسی-ٹورن نمبر کی غیر علامتی قدر کا تعین کیا: عمودی کی یکساں تعداد پر مکمل گراف کا معاملہ بہت زیادہ مشکل ہے، اور اسے ایرڈس، ہجنل، سوس اور زیمیرڈی نے 1983 میں حل کیا تھا: نوٹ کریں کہ دونوں صورتوں میں، اس مسئلے کو ٹورن کے نظریہ میں اضافی شرط شامل کرنے کے طور پر دیکھا جا سکتا ہے۔ دونوں صورتوں میں، یہ دیکھا جا سکتا ہے کہ غیر علامتی طور پر، اثر ایسا ہی ہے جیسے ہم نے یا کے بجائے خارج کر دیا ہو۔ حوالہ جات گراف تھیوری