Hadwiger–Nelson problem
জ্যামিতিক গ্রাফ তত্ত্বে, হুগো হ্যাডউইগার এবং এডওয়ার্ড নেলসনের নামে নামকরণ করা হ্যাডউইগার-নেলসন সমস্যাটি সমতলকে রঙ করার জন্য প্রয়োজনীয় ন্যূনতম রঙের সংখ্যা জিজ্ঞাসা করে যাতে একে অপরের থেকে 1 দূরত্বে কোনও দুটি বিন্দুর একই রঙ না থাকে। উত্তরটি অজানা, তবে 5,6 বা 7 নম্বরের মধ্যে একটিতে সংকুচিত করা হয়েছে। সঠিক মান সেট তত্ত্বের জন্য স্বতঃসিদ্ধগুলির পছন্দের উপর নির্ভর করতে পারে। সীমাবদ্ধ গ্রাফের সাথে সম্পর্ক প্রশ্নটি নিম্নরূপ গ্রাফ তাত্ত্বিক পরিভাষায় তৈরি করা যেতে পারে। G কে সমতলের একক দূরত্বের গ্রাফ হিসাবে ধরা যাকঃ সমতলের সমস্ত বিন্দু শীর্ষ হিসাবে এবং দুটি শীর্ষের মধ্যে একটি প্রান্ত সহ একটি অসীম গ্রাফ যদি এবং শুধুমাত্র যদি দুটি বিন্দুর মধ্যে দূরত্ব 1 হয়। হ্যাডউইগার-নেলসন সমস্যাটি হল জি-এর ক্রোমাটিক সংখ্যা খুঁজে বের করা। ফলস্বরূপ, সমস্যাটিকে প্রায়শই "সমতলের ক্রোমাটিক সংখ্যা খুঁজে বের করা" বলা হয়। ডি ব্রুইন-এর্ডোস উপপাদ্য অনুসারে, সমস্যাটি একটি সীমাবদ্ধ একক দূরত্ব গ্রাফের বৃহত্তম সম্ভাব্য ক্রোমাটিক সংখ্যা খুঁজে পাওয়ার সমতুল্য (পছন্দের স্বতঃসিদ্ধ অনুমানের অধীনে)। ইতিহাস অনুসারে, সমস্যাটি প্রথম 1950 সালে নেলসন দ্বারা প্রণয়ন করা হয়েছিল এবং প্রথম প্রকাশিত হয়েছিল এর আগে একটি সম্পর্কিত ফলাফল প্রকাশ করেছিল, যা দেখায় যে পাঁচটি সঙ্গতিপূর্ণ বদ্ধ সেট দ্বারা সমতলের যে কোনও আবরণ সেটগুলির একটিতে একটি একক দূরত্ব ধারণ করে এবং তিনি পরবর্তী গবেষণাপত্রেও সমস্যাটি উল্লেখ করেছিলেন। সমস্যাটি এবং এর ইতিহাস নিয়ে বিস্তারিত আলোচনা করা হয়েছে। সমস্যার একটি প্রয়োগ এটিকে বেকম্যান-কুয়ার্লেস উপপাদ্যের সাথে সংযুক্ত করে, যার মতে ইউক্লিডীয় সমতলের (বা যে কোনও উচ্চতর মাত্রিক স্থান) যে কোনও মানচিত্র যা একক দূরত্ব সংরক্ষণ করে তা অবশ্যই একটি আইসোমেট্রি হতে হবে, যা সমস্ত দূরত্ব সংরক্ষণ করে। এই স্থানগুলির সীমাবদ্ধ রঙগুলি তাদের থেকে উচ্চ-মাত্রিক স্থানগুলিতে ম্যাপিং তৈরি করতে ব্যবহার করা যেতে পারে যা দূরত্ব সংরক্ষণ করে তবে আইসোমেট্রি নয়। উদাহরণস্বরূপ, ইউক্লিডীয় সমতলকে সাতটি রঙ দিয়ে ছয়-মাত্রিক স্থানে ম্যাপ করা যেতে পারে যাতে দূরত্বের কোনও দুটি বিন্দুর একই রঙ না থাকে এবং তারপরে একক-দৈর্ঘ্যের প্রান্ত সহ ছয়-মাত্রিক নিয়মিত সিমপ্লেক্সের সাতটি শীর্ষে তাদের রঙ দ্বারা পয়েন্টগুলি ম্যাপ করা যায়। এটি একক দূরত্বে যে কোনও দুটি বিন্দুকে স্বতন্ত্র রঙে এবং সেখান থেকে একে অপরের থেকে একক দূরত্বে সিম্প্লেক্সের স্বতন্ত্র শীর্ষে মানচিত্র করে। যাইহোক, এটি অন্যান্য সমস্ত দূরত্বকে শূন্য বা এক-এ ম্যাপ করে, তাই এটি কোনও আইসোমেট্রি নয়। সমতলকে রঙ করার জন্য প্রয়োজনীয় রঙের সংখ্যা যদি সাত থেকে কমিয়ে কম করা যায়, তবে এই নির্মাণে লক্ষ্য স্থানের মাত্রার ক্ষেত্রেও একই হ্রাস প্রযোজ্য হবে। নিম্ন এবং উপরের সীমা সমতলের ক্রোমাটিক সংখ্যা কমপক্ষে চারটি হতে হবে, যা ক্রোমাটিক নম্বর চার সহ সাত-ভার্টেক্স একক দূরত্বের গ্রাফের অস্তিত্ব থেকে অনুসরণ করে, যা 1961 সালে ভাই উইলিয়াম এবং লিও মোজার দ্বারা আবিষ্কারের পরে মোজার স্পিন্ডল নামে নামকরণ করা হয়েছিল। এই গ্রাফটি একটি সাধারণ শীর্ষে যুক্ত দুটি একক সমবাহু ত্রিভুজ নিয়ে গঠিত, x। এই ত্রিভুজগুলির প্রত্যেকটি অন্য প্রান্ত বরাবর আরেকটি সমবাহু ত্রিভুজের সাথে যুক্ত; এই সংযুক্ত ত্রিভুজগুলির y এবং z শীর্ষগুলি একে অপরের থেকে একক দূরত্বে রয়েছে। যদি সমতলটি তিন রঙের হতে পারে, তবে ত্রিভুজের মধ্যে রঙ y এবং z উভয়কেই x-এর মতো একই রঙ রাখতে বাধ্য করবে, তবে, যেহেতু y এবং z একে অপরের থেকে একক দূরত্বে রয়েছে, তাই আমাদের সমতলের একক দূরত্বের গ্রাফের সঠিক রঙ থাকবে না। অতএব, এই গ্রাফ এবং এটি ধারণকারী সমতলকে রঙ করার জন্য কমপক্ষে চারটি রঙের প্রয়োজন। দশ-ভার্টেক্স চার-বর্ণগত একক দূরত্ব গ্রাফের আকারে একটি বিকল্প নিম্ন সীমা, গোলম্ব গ্রাফ, প্রায় একই সময়ে সলোমন ডব্লিউ. গোলম্ব দ্বারা আবিষ্কৃত হয়েছিল। 2018 সালে যখন কম্পিউটার বিজ্ঞানী এবং জীববিজ্ঞানী অব্রে ডি গ্রে একটি 1581-ভার্টেক্স, অ-4-রঙিন একক-দূরত্বের গ্রাফ খুঁজে পান, তখন নিম্ন সীমাটি পাঁচটিতে উন্নীত করা হয়। প্রমাণ হল কম্পিউটারের সাহায্যে। গণিতবিদ গিল কালাই এবং কম্পিউটার বিজ্ঞানী স্কট অ্যারোনসন ডি গ্রে-এর আবিষ্কার নিয়ে আলোচনা পোস্ট করেছেন, অ্যারোনসন স্যাট সমাধানকারী ব্যবহার করে ডি গ্রে-এর ফলাফলের স্বাধীন যাচাইকরণের প্রতিবেদন করেছেন। কালাই জর্ডান এলেনবার্গ এবং নোম এলকিজের অতিরিক্ত পোস্টগুলিকে এলকিজ এবং (পৃথকভাবে) ডি গ্রে-এর নির্মাণের তুলনায় কম শীর্ষযুক্ত অ-4-রঙিন একক দূরত্বের গ্রাফগুলি খুঁজে বের করার জন্য একটি পলিম্যাথ প্রকল্পের প্রস্তাবের সাথে সংযুক্ত করেছিলেন। 2021 সালের হিসাবে, ক্রোমাটিক সংখ্যা 5 সহ ক্ষুদ্রতম পরিচিত একক দূরত্ব গ্রাফের 509টি শীর্ষ রয়েছে। পলিম্যাথ প্রকল্পের পাতায় আরও গবেষণা, গণমাধ্যমের উদ্ধৃতি এবং যাচাইকরণের তথ্য রয়েছে। ক্রোমাটিক সংখ্যায় সাতটির উপরের সীমাটি নিয়মিত ষড়ভুজ দ্বারা সমতলের একটি টেসেলেশনের অস্তিত্ব থেকে অনুসরণ করে, যার ব্যাস একটির চেয়ে সামান্য কম, যা সমতলের 7-রঙের গঠন করার জন্য পুনরাবৃত্ত প্যাটার্নে সাতটি রঙ বরাদ্দ করা যেতে পারে। অনুসারে, এই উপরের সীমাটি প্রথম পর্যবেক্ষণ করেছিলেন জন আর ইসবেল। বৈচিত্র্য সমস্যাটি সহজেই উচ্চতর মাত্রায় প্রসারিত করা যেতে পারে। 3-স্পেসের ক্রোমাটিক সংখ্যা খুঁজে পাওয়া একটি বিশেষ আকর্ষণীয় সমস্যা। বিমানের সংস্করণের মতো, উত্তরটি জানা যায়নি, তবে কমপক্ষে 6 এবং সর্বাধিক 15 হিসাবে দেখানো হয়েছে। সমস্যার এন-ডাইমেনশনাল ক্ষেত্রে, টাইলিং এন-ডাইমেনশনাল কিউব থেকে পাওয়া প্রয়োজনীয় রঙের সংখ্যার উপর একটি সহজ উপরের সীমা হল। সিম্প্লেক্স থেকে একটি নিম্ন সীমা হল। কারণ, মোজার স্পিন্ডলের সাধারণীকরণ ব্যবহার করে এর একটি নিম্ন সীমা পাওয়া যায়ঃ বস্তুর একটি জোড়া (প্রতিটি দুটি সিম্প্লেক্স একটি দিকে একসাথে আঠালো) যা একদিকে একটি বিন্দু এবং অন্যদিকে একটি রেখা দ্বারা যুক্ত হয়। 1981 সালে ফ্রাঙ্কেল এবং উইলসন একটি সূচকীয় নিম্ন সীমা প্রমাণ করেছিলেন। সমতলের রঙগুলিও বিবেচনা করা যেতে পারে যেখানে প্রতিটি রঙের বিন্দুর সেটগুলি নির্দিষ্ট ধরনের সেটের মধ্যে সীমাবদ্ধ থাকে। এই ধরনের বিধিনিষেধের কারণে রঙের প্রয়োজনীয় সংখ্যা বৃদ্ধি পেতে পারে, কারণ এগুলি নির্দিষ্ট কিছু রঙকে গ্রহণযোগ্য বলে বিবেচিত হতে বাধা দেয়। উদাহরণস্বরূপ, যদি সমতলের একটি রঙ জর্ডান বক্ররেখা দ্বারা বেষ্টিত অঞ্চল নিয়ে গঠিত হয়, তবে কমপক্ষে ছয়টি রঙের প্রয়োজন হয়। আরও দেখুন চারটি রঙের উপপাদ্য নোটস রেফারেন্স বাহ্যিক যোগসূত্র গ্রাফ তত্ত্বের অমীমাংসিত সমস্যা জ্যামিতিক গ্রাফ তত্ত্ব গ্রাফের রঙ অসীম গ্রাফ গাণিতিক সমস্যা