Hadwiger–Nelson problem
ભૌમિતિક આલેખ સિદ્ધાંતમાં, હ્યુગો હેડવિગર અને એડવર્ડ નેલ્સનના નામ પરથી નામ આપવામાં આવેલી હેડવિગર-નેલ્સન સમસ્યા, સમતલને રંગવા માટે જરૂરી ઓછામાં ઓછા રંગોની સંખ્યા પૂછે છે, જેથી એકબીજાથી 1 અંતરે કોઈ પણ બે બિંદુઓ સમાન રંગ ધરાવતા ન હોય. જવાબ અજ્ઞાત છે, પરંતુ તેને 5,6 અથવા 7 નંબરોમાંથી એક સુધી સંકુચિત કરવામાં આવ્યો છે. સાચું મૂલ્ય સમૂહ સિદ્ધાંત માટે સ્વયંસિદ્ધોની પસંદગી પર આધારિત હોઈ શકે છે. મર્યાદિત આલેખ સાથેનો સંબંધ આ પ્રશ્નને આલેખ સૈદ્ધાંતિક શબ્દોમાં નીચે પ્રમાણે રજૂ કરી શકાય છે. ધારો કે G એ સમતલનો એકમ અંતર આલેખ છેઃ સમતલના તમામ બિંદુઓને શિરોબિંદુઓ તરીકે અને બે શિરોબિંદુઓ વચ્ચેનું અંતર 1 હોય તો જ બે શિરોબિંદુઓ વચ્ચેની ધાર સાથેનો અનંત આલેખ. હેડવિગર-નેલ્સનની સમસ્યા જીની રંગીન સંખ્યા શોધવાની છે. પરિણામે, સમસ્યાને ઘણીવાર "સમતલની રંગીન સંખ્યા શોધવી" કહેવામાં આવે છે. ડી બ્રુઇજન-એર્ડોસ પ્રમેય અનુસાર, સમસ્યાનું પરિણામ (પસંદગીના સ્વયંસિદ્ધ સિદ્ધાંતની ધારણા હેઠળ) મર્યાદિત એકમ અંતર આલેખની સૌથી મોટી શક્ય રંગીન સંખ્યા શોધવાની સમકક્ષ છે. ઇતિહાસ અનુસાર, આ સમસ્યા સૌપ્રથમ 1950 માં નેલ્સન દ્વારા ઘડવામાં આવી હતી, અને સૌપ્રથમ દ્વારા પ્રકાશિત કરવામાં આવી હતી. અગાઉ સંબંધિત પરિણામ પ્રકાશિત કર્યું હતું, જે દર્શાવે છે કે પાંચ એકરૂપ બંધ સેટ દ્વારા વિમાનના કોઈપણ આવરણમાં એક સેટમાં એકમ અંતર હોય છે, અને તેમણે પછીના પેપરમાં પણ સમસ્યાનો ઉલ્લેખ કર્યો હતો. આ સમસ્યા અને તેના ઇતિહાસની વિસ્તૃત ચર્ચા કરે છે. સમસ્યાનો એક ઉપયોગ તેને બેકમેન-કવાર્લ્સ પ્રમેય સાથે જોડે છે, જે મુજબ યુક્લિડિયન સમતલ (અથવા કોઈપણ ઉચ્ચ પરિમાણીય જગ્યા) નું કોઈ પણ મેપિંગ કે જે એકમ અંતરને જાળવી રાખે છે તે આઇસોમેટ્રી હોવું જોઈએ, જે તમામ અંતરને જાળવી રાખે છે. આ જગ્યાઓના મર્યાદિત રંગોનો ઉપયોગ તેમની પાસેથી ઉચ્ચ-પરિમાણીય જગ્યાઓ પર મેપિંગ બનાવવા માટે થઈ શકે છે જે અંતર જાળવી રાખે છે પરંતુ આઇસોમેટ્રી નથી. દાખલા તરીકે, યુક્લિડિયન સમતલને સાત રંગોથી રંગીને છ-પરિમાણીય અવકાશમાં મેપ કરી શકાય છે જેથી અંતર પર કોઈ બે બિંદુઓ એક જ રંગ ધરાવતા ન હોય, અને પછી તેમના રંગો દ્વારા બિંદુઓને એકમ-લંબાઈ ધાર સાથે છ-પરિમાણીય નિયમિત સિમ્પ્લેક્સના સાત શિરોબિંદુઓ પર મેપ કરી શકાય છે. આ એકમ અંતર પર કોઈપણ બે બિંદુઓને અલગ-અલગ રંગોમાં અને ત્યાંથી એકબીજાથી અલગ એકમ અંતર પર સિમ્પ્લેક્સના અલગ-અલગ શિરોબિંદુઓ પર નકશો બનાવે છે. જો કે, તે અન્ય તમામ અંતરને શૂન્ય અથવા એક સાથે મેપ કરે છે, તેથી તે આઇસોમેટ્રી નથી. જો સમતલને રંગવા માટે જરૂરી રંગોની સંખ્યા સાતથી ઘટાડીને ઓછી કરી શકાય, તો આ જ ઘટાડો આ બાંધકામમાં લક્ષ્ય જગ્યાના પરિમાણને લાગુ પડશે. નીચલા અને ઉપલા સીમાઓ વિમાનની રંગીન સંખ્યા ઓછામાં ઓછી ચાર હોવી જોઈએ તે હકીકત રંગીન સંખ્યા ચાર સાથે સાત-વર્ટેક્સ એકમ અંતર આલેખના અસ્તિત્વને અનુસરે છે, જેને 1961માં ભાઈઓ વિલિયમ અને લીઓ મોઝર દ્વારા તેની શોધ પછી મોઝર સ્પિન્ડલ નામ આપવામાં આવ્યું હતું. આ આલેખમાં સામાન્ય શિરોબિંદુ x પર જોડાયેલા બે એકમ સમબાહુ ત્રિકોણનો સમાવેશ થાય છે. આ દરેક ત્રિકોણ બીજી ધાર સાથે બીજા સમબાહુ ત્રિકોણ સાથે જોડાયેલા છે; આ જોડાયેલા ત્રિકોણના શિરોબિંદુઓ y અને z એકબીજાથી એકમ અંતરે છે. જો સમતલ ત્રણ રંગનું હોઈ શકે, તો ત્રિકોણની અંદરનો રંગ y અને z બંનેને x જેટલો જ રંગ આપવા માટે દબાણ કરશે, પરંતુ પછી, y અને z એકબીજાથી એકમ અંતર પર હોવાથી, આપણી પાસે સમતલના એકમ અંતર આલેખનો યોગ્ય રંગ નહીં હોય. તેથી, આ આલેખ અને તેમાં રહેલા સમતલને રંગવા માટે ઓછામાં ઓછા ચાર રંગોની જરૂર પડે છે. દસ-વર્ટેક્સ ચાર-રંગીન એકમ અંતર આલેખના સ્વરૂપમાં વૈકલ્પિક નીચલા બાઉન્ડ, ગોલોમ્બ ગ્રાફ, સોલોમન ડબ્લ્યુ. ગોલોમ્બ દ્વારા લગભગ તે જ સમયે શોધવામાં આવ્યો હતો. જ્યારે કોમ્પ્યુટર વૈજ્ઞાનિક અને જીવવિજ્ઞાની ઔબ્રે ડી ગ્રેએ 1581-વર્ટેક્સ, બિન-4-રંગીન એકમ-અંતરનો આલેખ શોધી કાઢ્યો ત્યારે 2018માં નીચલી સીમા વધારીને પાંચ કરવામાં આવી હતી. પુરાવો કમ્પ્યુટર સહાયિત છે. ગણિતશાસ્ત્રી ગિલ કાલાઇ અને કોમ્પ્યુટર વૈજ્ઞાનિક સ્કોટ એરોનસને ડી ગ્રેની શોધની ચર્ચા પોસ્ટ કરી હતી, જેમાં એરોનસને SAT સોલ્વર્સનો ઉપયોગ કરીને ડી ગ્રેના પરિણામની સ્વતંત્ર ચકાસણીની જાણ કરી હતી. કાલાઇએ જોર્ડન એલેનબર્ગ અને નોઆમ એલ્કીઝ દ્વારા વધારાની પોસ્ટ્સને જોડ્યા, એલ્કીઝ સાથે અને (અલગથી) ડી ગ્રેએ ડી ગ્રેના બાંધકામ કરતાં ઓછા શિરોબિંદુઓ સાથે બિન-4-રંગીન એકમ અંતર આલેખ શોધવા માટે પોલીમેથ પ્રોજેક્ટની દરખાસ્ત કરી. 2021 સુધીમાં, રંગીન સંખ્યા 5 સાથેનો સૌથી નાનો જાણીતો એકમ અંતર આલેખ 509 શિરોબિંદુઓ ધરાવે છે. પોલીમેથ પ્રોજેક્ટના પૃષ્ઠમાં, વધુ સંશોધન, મીડિયા સાઇટેશન અને ચકાસણી ડેટા છે. રંગીન સંખ્યા પર સાતની ઉપલી સીમા નિયમિત ષટ્કોણ દ્વારા સમતલના ટેસેલેશનના અસ્તિત્વને અનુસરે છે, જેનો વ્યાસ એક કરતા થોડો ઓછો હોય છે, જેને સમતલના 7-રંગની રચના કરવા માટે પુનરાવર્તિત પેટર્નમાં સાત રંગો સોંપી શકાય છે. અનુસાર, આ ઉપલા બાઉન્ડનું નિરીક્ષણ સૌપ્રથમ જ્હોન આર. ઇસબેલ દ્વારા કરવામાં આવ્યું હતું. ભિન્નતા સમસ્યા સરળતાથી ઉચ્ચ પરિમાણો સુધી વિસ્તૃત કરી શકાય છે. 3-જગ્યાની રંગીન સંખ્યા શોધવી એ ખાસ કરીને રસપ્રદ સમસ્યા છે. વિમાનના સંસ્કરણની જેમ, જવાબ જાણી શકાયો નથી, પરંતુ ઓછામાં ઓછા 6 અને વધુમાં વધુ 15 હોવાનું દર્શાવવામાં આવ્યું છે. સમસ્યાના એન-ડાયમેન્શનલ કિસ્સામાં, ટાઇલિંગ એન-ડાયમેન્શનલ ક્યુબ્સમાંથી મળેલા જરૂરી રંગોની સંખ્યા પર એક સરળ ઉપલા બાઉન્ડ છે. સિમ્પ્લેક્સમાંથી નીચલી બાઉન્ડ છે. કારણ કે, મોઝર સ્પિન્ડલના સામાન્યીકરણનો ઉપયોગ કરીને નીચી બાઉન્ડ ઉપલબ્ધ છેઃ વસ્તુઓની એક જોડી (દરેક બે સિમ્પ્લેક્સ એક બાજુ પર એકબીજા સાથે જોડાયેલી હોય છે) જે એક બાજુ એક બિંદુ દ્વારા અને બીજી બાજુ એક રેખા દ્વારા જોડાયેલી હોય છે. 1981માં ફ્રેન્કલ અને વિલ્સન દ્વારા ઘાતાંકીય નિમ્ન સીમા સાબિત કરવામાં આવી હતી. સમતલના રંગોને પણ ધ્યાનમાં લઈ શકાય છે જેમાં દરેક રંગના બિંદુઓના સમૂહો અમુક ચોક્કસ પ્રકારના સમૂહો સુધી મર્યાદિત હોય છે. આવા પ્રતિબંધો રંગોની જરૂરી સંખ્યામાં વધારો કરી શકે છે, કારણ કે તેઓ ચોક્કસ રંગોને સ્વીકાર્ય ગણવામાં આવતા અટકાવે છે. દાખલા તરીકે, જો સમતલના રંગમાં જોર્ડન વળાંકથી ઘેરાયેલા પ્રદેશોનો સમાવેશ થાય છે, તો ઓછામાં ઓછા છ રંગો જરૂરી છે. ચાર રંગ પ્રમેય નોંધો સંદર્ભો બાહ્ય કડીઓ આલેખ સિદ્ધાંતમાં વણઉકેલાયેલી સમસ્યાઓ ભૌમિતિક આલેખ સિદ્ધાંત આલેખ રંગ અનંત આલેખ ગાણિતિક સમસ્યાઓ