Burr–Erdős conjecture
ریاضی میں، بر-ایرڈس قیاس آرائی کم گرافوں کی رمسی تعداد سے متعلق ایک مسئلہ تھا۔ قیاس آرائی کا نام اسٹیفن بر اور پال ایردوس کے نام پر رکھا گیا ہے، اور یہ ایردوس کے نام پر رکھے گئے بہت سے قیاس آرائیوں میں سے ایک ہے۔ اس میں کہا گیا ہے کہ گراف کے کسی بھی غیر معمولی خاندان میں گراف کی رمسی تعداد کو گراف کے عمودی حصوں کی تعداد میں لکیری طور پر بڑھنا چاہیے۔ اس قیاس کو چونگ بوم لی نے ثابت کیا۔ اس طرح یہ اب ایک نظریہ ہے۔ تعریفیں اگر G ایک غیر ہدایت شدہ گراف ہے، تو G کی انحطاط کم از کم نمبر p ہے جس میں G کے ہر ذیلی گراف میں ڈگری p یا اس سے چھوٹے کا ایک ورٹیکس ہوتا ہے۔ ڈیجینریسی پی والے گراف کو پی-ڈیجینریٹ کہا جاتا ہے۔ مساوی طور پر، پی-ڈیجینریٹ گراف ایک ایسا گراف ہے جسے بار بار ڈگری پی یا اس سے چھوٹے کے سرے کو ہٹا کر خالی گراف تک کم کیا جا سکتا ہے۔ یہ رمسی کے نظریہ کے مطابق ہے کہ کسی بھی گراف G کے لیے کم از کم عدد موجود ہوتا ہے، رمسی نمبر G، اس طرح کہ کم از کم عمودی پر کوئی بھی مکمل گراف جس کے کنارے سرخ یا نیلے رنگ کے ہوتے ہیں، G کی یک رنگ نقل پر مشتمل ہوتا ہے۔ مثال کے طور پر، مثلث کا رمسی نمبر 6 ہوتا ہے: اس بات سے کوئی فرق نہیں پڑتا کہ چھ عمودی پر مکمل گراف کے کنارے سرخ یا نیلے رنگ کے ہوں، ہمیشہ سرخ مثلث یا نیلا مثلث ہوتا ہے۔ قیاس 1973 میں، اسٹیفن بر اور پال ایرڈس نے مندرجہ ذیل قیاس کیا: ہر عدد p کے لیے ایک مستقل cp موجود ہے تاکہ n عمودی پر کسی بھی p-ڈی جنریٹ گراف G میں زیادہ سے زیادہ cp n پر رمسی نمبر ہو۔ یعنی، اگر n-ورٹیکس گراف G، p-ڈی جنریٹ ہے، تو G کی یک رنگ نقل ہر دو کنارے والے مکمل گراف میں موجود ہونی چاہیے۔ معلوم نتائج مکمل قیاس آرائی ثابت ہونے سے پہلے، اسے پہلے کچھ خاص معاملات میں طے کیا گیا تھا۔ یہ باؤنڈ ڈگری گراف کے لیے ثابت کیا گیا تھا ؛ ان کے ثبوت سی پی کی بہت زیادہ قیمت کا باعث بنے، اور اس مستقل میں بہتری اور کے ذریعے کی گئی۔ زیادہ عام طور پر، یہ قیاس پی-ترتیب دینے والے گرافوں کے لیے درست معلوم ہوتا ہے، جس میں محدود زیادہ سے زیادہ ڈگری والے گراف، پلانر گراف اور گراف شامل ہوتے ہیں جن میں کے پی کی ذیلی تقسیم نہیں ہوتی ہے۔ یہ ذیلی تقسیم شدہ گرافوں کے لیے بھی جانا جاتا ہے، گراف جن میں دو ملحقہ عمودی دو سے زیادہ ڈگری نہیں رکھتے ہیں۔ صوابدیدی گرافوں کے لیے، رمسی نمبر کو ایک فنکشن سے منسلک ہونے کے لیے جانا جاتا ہے جو صرف قدرے سپر لائنر طور پر بڑھتا ہے۔ خاص طور پر، یہ ظاہر ہوا کہ ایک مستقل سی پی موجود ہے جیسے کہ، کسی بھی پی-ڈی جنریٹ این-ورٹیکس گراف جی کے لیے، حوالہ جات نوٹ کریں۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ گراف تھیوری رمسی تھیوری قیاس آرائیاں جو ثابت ہو چکی ہیں بر-ایرڈوس قیاس آرائیاں گراف تھیوری میں نظریات