Hadwiger–Nelson problem
جیومیٹرک گراف تھیوری میں، ہاڈوگر-نیلسن مسئلہ، جسے ہیوگو ہاڈوگر اور ایڈورڈ نیلسن کے نام سے موسوم کیا گیا ہے، طیارہ کو رنگنے کے لیے درکار کم از کم رنگوں کی تعداد کا مطالبہ کرتا ہے تاکہ ایک دوسرے سے 1 کے فاصلے پر کسی بھی دو نکات کا رنگ ایک جیسا نہ ہو۔ جواب نامعلوم ہے، لیکن اسے 5، 6 یا 7 نمبروں میں سے کسی ایک تک محدود کر دیا گیا ہے۔ صحیح قدر سیٹ تھیوری کے لیے محوریات کے انتخاب پر منحصر ہو سکتی ہے۔ محدود گرافوں سے تعلق سوال کو گراف نظریاتی اصطلاحات میں درج ذیل انداز میں بیان کیا جا سکتا ہے۔ G کو طیارہ کا اکائی فاصلہ گراف ہونے دیں: ایک لامحدود گراف جس میں طیارہ کے تمام نکات عمودی ہوں اور دو عمودی کے درمیان ایک کنارے کے ساتھ اگر اور صرف اس صورت میں جب دونوں نکات کے درمیان فاصلہ 1 ہو۔ ہاڈوگر-نیلسن کا مسئلہ G کا کرومیٹک نمبر تلاش کرنا ہے۔ اس کے نتیجے میں، اس مسئلے کو اکثر "طیارہ کا کرومیٹک نمبر تلاش کرنا" کہا جاتا ہے۔ ڈی بروجن-ایرڈوس تھیوریم کے مطابق، اس کا نتیجہ یہ ہے کہ مسئلہ (انتخاب کے محور کے مفروضے کے تحت) ایک محدود اکائی کے فاصلے کے گراف کی سب سے بڑی ممکنہ رنگین تعداد کو تلاش کرنے کے مساوی ہے۔ تاریخ کے مطابق، یہ مسئلہ سب سے پہلے نیلسن نے 1950 میں وضع کیا تھا، اور اسے سب سے پہلے نیلسن نے شائع کیا تھا۔ اس نے پہلے ایک متعلقہ نتیجہ شائع کیا تھا، جس سے یہ ظاہر ہوتا ہے کہ پانچ ہم آہنگ بند سیٹوں کے ذریعے ہوائی جہاز کے کسی بھی احاطے میں ایک سیٹ میں ایک یونٹ کا فاصلہ ہوتا ہے، اور اس نے بعد کے کاغذ میں بھی اس مسئلے کا ذکر کیا۔ اس مسئلے اور اس کی تاریخ پر وسیع پیمانے پر تبادلہ خیال کرتا ہے۔ اس مسئلے کا ایک اطلاق اسے بیک مین-کوئرلز تھیوریم سے جوڑتا ہے، جس کے مطابق یوکلڈین پلین (یا کسی بھی اعلی جہتی جگہ) کی کوئی بھی نقشہ سازی جو اکائی کے فاصلے کو محفوظ رکھتی ہے، ایک آئسومیٹری ہونی چاہیے، جو تمام فاصلے کو محفوظ رکھتی ہے۔ ان خالی جگہوں کے محدود رنگوں کو ان سے اعلی جہتی خالی جگہوں پر نقشے بنانے کے لیے استعمال کیا جا سکتا ہے جو فاصلے کو محفوظ رکھتے ہیں لیکن آئسومیٹریز نہیں ہیں۔ مثال کے طور پر، یوکلڈین سطح کو سات رنگوں سے رنگ کر کے چھ جہتی خلا میں نقشہ بنایا جا سکتا ہے تاکہ فاصلے پر کوئی دو نکات ایک ہی رنگ کے نہ ہوں، اور پھر پوائنٹس کو ان کے رنگوں سے چھ جہتی باقاعدہ سمپلیکس کے سات عمودی حصوں میں نقشہ بنایا جا سکے۔ یہ کسی بھی دو نکات کو اکائی کے فاصلے پر الگ الگ رنگوں میں نقشہ بناتا ہے، اور وہاں سے ایک دوسرے سے الگ اکائی کے فاصلے پر سمپلیکس کے الگ الگ عمودی حصوں میں۔ تاہم، یہ دوسرے تمام فاصلے کو صفر یا ایک پر نقشہ بناتا ہے، لہذا یہ آئسومیٹری نہیں ہے۔ اگر ہوائی جہاز کو رنگنے کے لیے درکار رنگوں کی تعداد کو سات سے کم کر کے کم کیا جا سکتا ہے، تو وہی کمی اس تعمیر میں ہدف کی جگہ کے طول و عرض پر لاگو ہوگی۔ نچلی اور اوپری حدود یہ حقیقت کہ طیارہ کا کرومیٹک نمبر کم از کم چار ہونا چاہیے، کرومیٹک نمبر چار کے ساتھ سات ورٹیکس یونٹ کے فاصلے کے گراف کے وجود کی پیروی کرتا ہے، جسے 1961 میں بھائیوں ولیم اور لیو موزر کے ذریعہ دریافت کرنے کے بعد موزر اسپنڈل کا نام دیا گیا تھا۔ یہ گراف دو اکائی مساوی مثلثوں پر مشتمل ہے جو ایک مشترکہ سرے x پر جڑے ہوئے ہیں۔ ان مثلثوں میں سے ہر ایک دوسرے کنارے کے ساتھ دوسرے مساوی مثلث میں جڑا ہوا ہے۔ ان جڑے ہوئے مثلثوں کے عمودی y اور z ایک دوسرے سے اکائی فاصلے پر ہیں۔ اگر طیارہ تین رنگ کا ہو سکتا ہے، تو مثلث کے اندر کا رنگ y اور z دونوں کو x کے برابر رنگ رکھنے پر مجبور کرے گا، لیکن پھر، چونکہ y اور z ایک دوسرے سے اکائی فاصلے پر ہیں، اس لیے ہمارے پاس طیارہ کے اکائی فاصلے کے گراف کا مناسب رنگ نہیں ہوگا۔ لہذا، اس گراف اور اس پر مشتمل سطح کو رنگنے کے لیے کم از کم چار رنگوں کی ضرورت ہوتی ہے۔ دس ورٹیکس چار کرومیٹک یونٹ ڈسٹنس گراف کی شکل میں ایک متبادل نچلی باؤنڈ، گولمب گراف، تقریبا اسی وقت سولومن ڈبلیو گولمب نے دریافت کیا تھا۔ 2018 میں نچلی حد کو بڑھا کر پانچ کر دیا گیا تھا، جب کمپیوٹر سائنسدان اور ماہر حیاتیات آبری ڈی گرے نے 1581-ورٹیکس، غیر 4-رنگین یونٹ فاصلے کا گراف پایا۔ ثبوت کمپیوٹر کی مدد سے ہے۔ ریاضی دان گل کالائی اور کمپیوٹر سائنسدان اسکاٹ ایرونسن نے ڈی گرے کی دریافت پر بحث پوسٹ کی، جس میں ایرونسن نے ایس اے ٹی حل کرنے والوں کا استعمال کرتے ہوئے ڈی گرے کے نتائج کی آزاد تصدیق کی اطلاع دی۔ کالائی نے جورڈن ایلن برگ اور نوم ایلکیز کی اضافی پوسٹوں کو ایلکیز کے ساتھ منسلک کیا اور (علیحدہ طور پر) ڈی گرے نے ڈی گرے کی تعمیر کے مقابلے میں کم عمودی کے ساتھ غیر-4 رنگین یونٹ فاصلے کے گراف تلاش کرنے کے لیے پولی میتھ پروجیکٹ کی تجویز پیش کی۔ 2021 تک، کرومیٹک نمبر 5 کے ساتھ سب سے چھوٹے معلوم یونٹ فاصلے کے گراف میں 509 عمودی ہیں۔ پولی میتھ پروجیکٹ کے صفحہ میں مزید تحقیق، میڈیا حوالہ جات اور تصدیق کے اعداد و شمار شامل ہیں۔ کرومیٹک نمبر پر سات کی اوپری حد باقاعدہ ہیکساگون کے ذریعہ جہاز کے ٹیسیلیشن کے وجود سے ملتی ہے، جس کا قطر ایک سے قدرے کم ہوتا ہے، جسے ہوائی جہاز کے 7 رنگ بنانے کے لیے دہرائے جانے والے نمونے میں سات رنگ تفویض کیے جا سکتے ہیں۔ کے مطابق، اس اوپری حد کا مشاہدہ سب سے پہلے جان آر اسبل نے کیا تھا۔ تغیرات مسئلہ کو آسانی سے اعلی جہتوں تک بڑھایا جا سکتا ہے۔ 3-اسپیس کا کرومیٹک نمبر تلاش کرنا ایک خاص طور پر دلچسپ مسئلہ ہے۔ جیسا کہ ہوائی جہاز کے ورژن کے ساتھ، جواب معلوم نہیں ہے، لیکن کم از کم 6 اور زیادہ سے زیادہ 15 دکھایا گیا ہے۔ مسئلہ کے n-جہتی معاملے میں، ٹائلنگ n-جہتی کیوب سے پائے جانے والے مطلوبہ رنگوں کی تعداد پر ایک آسان اوپری باؤنڈ ہے۔ سمپلیکس سے ایک نچلی حد ہے۔ کیونکہ، موزر اسپنڈل کی عمومی کاری کا استعمال کرتے ہوئے کی ایک نچلی حد دستیاب ہے: اشیاء کا ایک جوڑا (ہر دو سمپلیکس ایک پہلو پر ایک ساتھ چپکے ہوئے ہیں) جو ایک طرف ایک نقطہ سے اور دوسری طرف ایک لکیر سے جڑے ہوئے ہیں۔ 1981 میں فرینکل اور ولسن نے ایک متغیر نچلی حد ثابت کی تھی۔ ہوائی جہاز کے رنگوں پر بھی غور کیا جا سکتا ہے جس میں ہر رنگ کے پوائنٹس کے سیٹ کسی خاص قسم کے سیٹوں تک محدود ہوتے ہیں۔ اس طرح کی پابندیاں رنگوں کی مطلوبہ تعداد میں اضافے کا سبب بن سکتی ہیں، کیونکہ وہ بعض رنگوں کو قابل قبول سمجھے جانے سے روکتی ہیں۔ مثال کے طور پر، اگر سطح کا رنگ اردن کے منحنی خطوط سے محصور علاقوں پر مشتمل ہے، تو کم از کم چھ رنگوں کی ضرورت ہے۔ چار رنگین تھیوریم نوٹ حوالہ جات بیرونی روابط گراف تھیوری جیومیٹرک گراف تھیوری گراف کلرنگ لامحدود گراف ریاضیاتی مسائل میں حل شدہ مسائل