எந்த வரைபடத்துக்கும் நான்கு நிறங்கள், நேரியல் நேரத்தில் கண்டறியப்பட்டன

ஒரு தட்டையான தாளில் வரையப்பட்ட எந்த வரைபடத்தையும், அண்டை நாடுகள் ஒருபோதும் ஒரே நிறத்தைப் பகிராதபடி நான்கு நிறங்களால் நிறமிடலாம். Francis Guthrie இதை 1852-இல் ஊகித்தார்; Appel, Haken ஆகியோர் 1976-இல் நிறுவினர். ஆனால் தேற்றம், நான்கு நிறங்கள் இருக்கின்றன என்பதை மட்டுமே சொல்கிறது. கொடுக்கப்பட்ட ஒரு வரைபடத்துக்கு அவற்றை எப்படிக் கண்டுபிடிப்பது? “எளிய பதில் இல்லை” என்று டோக்கியோ பல்கலைக்கழகத்தின் Yuta Inoue-வும், ஜப்பான், கனடா, ஸ்லோவேனியா, டென்மார்க் ஆகிய நாடுகளைச் சேர்ந்த அவருடைய ஐந்து சக ஆய்வாளர்களும் எழுதுகிறார்கள். அது எவ்வளவு சிக்கலாக இருந்ததென்றால், பல எதிர் உதாரணங்கள் (counterexamples) முன்மொழியப்பட வழிவகுத்தது.

புள்ளிகள், கோடுகள், முக்கோணங்கள்

ஒவ்வொரு நாடும் ஒரு புள்ளி, அதாவது முனை (vertex), ஆகிறது; ஒவ்வொரு பொது எல்லையும் ஒரு கோடு, அதாவது விளிம்பு (edge), ஆகிறது: வரைபடம், கோடுகள் ஒன்றையொன்று கடக்காமல் வரையப்பட்ட ஒரு தள வரைபு (planar graph) ஆகிறது. அதை நிறமிடுவது என்றால், ஒவ்வொரு விளிம்பின் இரு முனைகளிலும் வெவ்வேறாக இருக்கும்படி, ஒவ்வொரு முனைக்கும் நான்கு நிறங்களில் ஒன்றைத் தருவது. முனைகளின் எண்ணிக்கையை n என்போம். ஒவ்வொரு முகமும் ஒரு முக்கோணமாக இருக்கும் முக்கோணப் பிரிப்புகளைக் (triangulations) கையாண்டால் போதும்: அதிக விளிம்புகள் நிறமிடுவதைக் கடினமாக்க மட்டுமே செய்யும்.

கெம்பின் இடமாற்றம்

அடிப்படை நகர்வு, A. B. Kempe-இன் 1879 ஆய்வுக்கட்டுரைக்குச் செல்கிறது. நான்கு நிறங்களை இணைகளாக்குங்கள் — சிவப்புடன் நீலம், பச்சையுடன் மஞ்சள் என்பதுபோல. ஒரு கெம்ப் சங்கிலி (Kempe chain) என்பது ஓர் இணையின் இரண்டு நிறங்களைக் கொண்ட, இணைக்கப்பட்ட முனைகளின் ஒரு குழு. ஒரு முழுச் சங்கிலியின் நெடுகிலும் அந்த இரண்டு நிறங்களை இடம் மாற்றுவது நிறமிடலைச் செல்லுபடியானதாகவே வைக்கிறது.

நான்கு அண்டை முனைகள் கொண்ட ஒரு முனை v-ஐ எடுத்துக்கொள்ளுங்கள் — அதைச் சுற்றி வரிசையாக v0 முதல் v3 வரை — முதலில் மீதியை நிறமிடுங்கள். அண்டை முனைகள் மூன்று அல்லது அதற்கும் குறைவான நிறங்களைப் பயன்படுத்தினால், v காலியான நிறத்தை எடுத்துக்கொள்கிறது. நான்கையும் பயன்படுத்தினால், v0-இல் தொடங்கி v0, v2 ஆகியவற்றின் நிறங்களிலான சங்கிலியைப் பின்தொடருங்கள். அது v2-ஐ அடையவில்லை என்றால், அதை இடம் மாற்றுங்கள்: v0, v2-இன் நிறத்தை எடுக்கிறது, v-க்கு ஒரு நிறம் விடுபடுகிறது. அது v2-ஐ அடைந்தால், அதற்குப் பதிலாக v1, v3 ஆகியவற்றின் நிறங்களிலான v1-இன் சங்கிலியை இடம் மாற்றுங்கள்; அப்போது v1, v3-இன் நிறத்தை எடுக்கிறது.

எப்போதும் சரிசெய்யக்கூடிய துண்டுகள்

தேற்றத்தின் நிரூபணங்கள் குறைக்கக்கூடிய அமைவுகளைச் (reducible configurations) சார்ந்துள்ளன: வெட்டி எடுத்து, மீதி நிறமிடப்பட்ட பின் மீண்டும் வைக்கக்கூடிய சிறிய வடிவங்கள். அவற்றின் வளையத்தின் (ring) — அவற்றைச் சுற்றி உடனடியாக உள்ள முனைகளின் — நிறங்கள் பொருந்தவில்லை என்றால், வெளியே செய்யப்படும் வரம்புக்குட்பட்ட எண்ணிக்கையிலான மேம்படுத்தும் கெம்ப் மாற்றங்கள் எப்போதும் அவற்றைச் சரிசெய்கின்றன: இங்கு பயன்படுத்தப்படும், அதிகபட்சம் 18 முனைகள் கொண்ட வளையங்களுடைய வடிவங்களுக்கு, அதிகபட்சம் 25.

ஒரு குறைக்கக்கூடிய அமைவு (இடது; ஒவ்வோர் எண்ணும், முழு வரைபடத்தில் அந்த முனைக்கு எத்தனை அண்டை முனைகள் இருக்க வேண்டும் என்பதைக் குறிக்கிறது), அதே வடிவம் அதன் வளையம் R-ஆல் நிறைவுசெய்யப்பட்டது (வலது). — படம் 1, Inoue et al. (2026), arXiv:2610.39753.

Robertson, Sanders, Seymour, Thomas ஆகியோர் 1997-இல், ஒரு நேரத்தில் ஒரு வடிவம் என, இவ்வாறு எப்படி நிறமிடுவது என்று காட்டினர். ஒவ்வொரு சுற்றும் வரைபைச் சில முனைகள் சுருக்குகிறது, அதன் முழுவதையும் ஒருமுறை கடக்கும் செலவு ஆகிறது; எனவே நேரம் இருபடி (quadratic): இரு மடங்கு பெரிய வரைபடத்துக்கு நான்கு மடங்கு நீண்டது.

முந்தைய ஓர் ஆய்வுக்கட்டுரையில் (FOCS’26), இதே ஆறு ஆசிரியர்கள், ஒவ்வொரு முக்கோணப் பிரிப்பிலும், 8,202 வடிவங்களின் பட்டியலிலிருந்து எடுக்கப்பட்ட, ஒன்றையொன்று தொடாத குறைக்கக்கூடிய அமைவுகள் n-க்கு விகிதமான எண்ணிக்கையில் இருப்பதை நிறுவினர் — அல்லது இருபுறமும் முனைகள் கொண்ட அதே எண்ணிக்கையிலான குறுகிய சுற்றுகள், அவையும் உதவுகின்றன. அவர்கள் எல்லா வடிவங்களையும் ஒரே நேரத்தில் நீக்கி, மீதியை நிறமிட்டு, பிறகு எல்லா வளையங்களையும் ஒன்றாகச் சரிசெய்கிறார்கள். ஒரு சீரற்ற கெம்ப் மாற்றம், சரியான நிற இணையையும் (மூன்றில் ஒரு வாய்ப்பு), வளையத்தைத் தொடும் ஒவ்வொரு சங்கிலியிலும் சரியான பூவா தலையாவையும் (ஒவ்வொன்றுக்கும் இரண்டில் ஒரு வாய்ப்பு) தேர்ந்தெடுத்தால், கொடுக்கப்பட்ட ஒரு வளையத்துக்கு உதவுகிறது. இத்தகைய 18 சங்கிலிகள் வரை இருந்தால், இது குறைந்தது 3 × 2¹⁸, அதாவது 786,432-இல் ஒரு வாய்ப்பு: சிறியது, ஆனால் நிலையானது. எனவே சுற்றுகளின் எண்ணிக்கை log n என்ற அளவில் மட்டுமே வளர்கிறது — தோராயமாக n-ஐ எத்தனை முறை பாதியாக்கலாம் என்பது. ஆனால் ஒரே ஒரு மாற்றம் வரைபின் ஒரு நிலையான பின்னத்தை உள்ளடக்கக்கூடும்: ஒவ்வொன்றுக்கும் முழுக் கடப்பின் செலவு, மொத்தம் n log n.

கடப்புக்குப் பதிலாக ஓர் அட்டவணை

புதிய ஆய்வுக்கட்டுரை log n மாற்றங்களை வைத்துக்கொண்டு, ஒவ்வொன்றையும் மலிவாக்குகிறது. n-க்கு விகிதமான நேரம் எடுக்கும் ஒரு தயாரிப்புக்குப் பிறகு, ஒவ்வொரு மாற்றமும் சராசரியாகச் சுமார் n / log n படிகளில் கண்டறியப்பட்டுச் செயல்படுத்தப்படுகிறது. அப்போது log n மாற்றங்களும் சேர்ந்து n-க்கு விகிதமான நேரம் — நேரியல் நேரம் (linear time) — எடுக்கின்றன; இந்த வரம்பு உகந்தது (optimal) என்கிறார்கள் ஆசிரியர்கள்.

உத்தி “நான்கு ரஷ்யர்களின் முறை” (Method of Four Russians). ½ log n பிட் குறியீட்டுக்குள் — n-ஐ எழுதத் தேவையான இருமை இலக்கங்களில் பாதிக்குள் — அடங்கும் ஒரு துணைச் சிக்கலுக்கு அதிகபட்சம் √n சாத்தியமான பதிப்புகளே உள்ளன; எனவே அவை அனைத்தின் பதில்களையும் முன்கூட்டியே கணக்கிட்டு ஓர் அட்டவணையில் சேமிக்கலாம். சுமார் log n பிட் நினைவகச் சொற்களைக் கொண்ட, அனுமானிக்கப்பட்ட கணினி, சேமிக்கப்பட்ட எந்தப் பதிலையும் ஒரே படியில் படிக்கிறது.

வரைபு, குறுகிய எல்லைகளுடைய, ஒன்றுக்குள் ஒன்றான பகுதிகளாக மீண்டும் மீண்டும் வெட்டப்படுகிறது. மிகச் சிறியவை சுமார் log n முனைகளைக் கொண்டு, நிறங்கள் உட்பட, ஒரே குறியீட்டுக்குள் அடங்குகின்றன. ஒவ்வொரு பகுதிக்கும், எந்த எல்லை முனைகள் ஒரு கெம்ப் சங்கிலியைப் பகிர்கின்றன என்பதை ஒரு சிறிய சுருக்க வரைபு பதிவு செய்கிறது. பிறகு ஒரு மாற்றம் “இடம் மாற்று” அல்லது “வைத்திரு” என்ற பிட்களின் சரங்களாகக் கீழிறங்குகிறது; ஒவ்வொரு சிறு பகுதியிலும் ஒரே ஒரு பார்வை ஒவ்வொரு நிறத்தையும் புதுப்பிக்கிறது.

நான்கு நிறங்களால் நிறமிடப்பட்ட ஒரு வரைபின் பகுதி. சாம்பல் பரப்பு ஒரு பகுதி R; தடித்த கருப்பு விளிம்புகள் சிவப்பு-நீலம், பச்சை-மஞ்சள் இணைகளின் கெம்ப் சங்கிலிகளைச் சேர்ந்தவை. — படம் 2, Inoue et al. (2026), arXiv:2610.39753.

அதே பகுதியின் சுருக்கம்: ஒவ்வொரு நீலக் கறையும் ஒரு கெம்ப் சங்கிலியின் ஒரு துண்டைக் குறிக்கிறது; அதன் கோடுகள் அது எந்த எல்லை முனைகளை இணைக்கிறது என்பதைக் காட்டுகின்றன. — படம் 3, Inoue et al. (2026), arXiv:2610.39753.

பகடை இல்லாமல் தேர்ந்தெடுத்தல்

சீரற்ற தேர்வுகளுடன், இது ஏற்கெனவே ஒரு வரைபடத்தைச் சராசரியாக நேரியல் நேரத்தில் நிறமிடுகிறது. வேகத்தை இழக்காமல் பகடையை நீக்குவதே “மிக மிகச் சவாலான பகுதி”. இதுவரையிலான ஒவ்வொரு முடிவும் தனக்குச் சாதகமாக அமையும் வரை ஒரு வளையத்தை உயிருள்ளது என்போம். அதைத் தொடும் முடிவெடுக்கப்படாத u சங்கிலிகள் பூவா தலையாவுக்கு விடப்பட்டால், அது 1/2^u நிகழ்தகவுடன் பிழைக்கும்; உயிருள்ள எல்லா வளையங்கள் மீதும் கூட்டினால், இந்த எண்கள் எதிர்பார்க்கப்படும் பிழைத்தவர்களின் எண்ணிக்கையைத் தருகின்றன. ஒரு சங்கிலியைப் பற்றி முடிவெடுப்பது, அந்தத் தேர்வை விரும்பிய ஒவ்வொரு வளையத்தின் உறுப்பையும் இரட்டிப்பாக்கி, மற்றவற்றைப் பூஜ்ஜியமாக்குகிறது. கூட்டுத்தொகை குறையாமல் காக்கும் தேர்வை வழிமுறை எடுக்கிறது; இதனால் இறுதியில், வாய்ப்பு சராசரியாக உதவியிருக்கும் அளவுக்குக் குறையாத எண்ணிக்கையிலான வளையங்களுக்கு உதவி கிடைக்கிறது.

ஒரு வரம்பு, நிறுத்துக் கடிகாரம் அல்ல

ஆய்வுக்கட்டுரை எந்தச் செயலாக்கத்தையும் (implementation) இயக்க நேரத்தையும் அறிவிக்கவில்லை; “n-க்கு விகிதமானது” என்பதில் மறைந்துள்ள மாறிலிகளும் (constants) தரப்படவில்லை. அவை பெரியவை: 8,202 வடிவங்கள் ஒவ்வொன்றுக்கும், அதன் வளையத்தின் ஒவ்வொரு நிறமிடலுக்கும் எத்தனை மேம்படுத்தும் மாற்றங்கள் தேவை என்பதை வழிமுறை சேமிக்கிறது — “பிரம்மாண்டமான, நிலையான அளவு தகவல்”. ஒரு பின்னிணைப்பில், தாங்கள் அடித்தளமாகக் கொண்ட, ஒன்றுக்குள் ஒன்றான பகுதிகளின் 2013 கட்டமைப்பில் இருந்த “ஒரு சிறிய தவறையும்” அவர்கள் திருத்துகிறார்கள். 1852-இன் ஓர் ஊகம், இப்போது, தான் நிறமிடும் வரைபடத்தைவிட வேகமாகச் செலவு வளராத ஒரு நிறமிடும் முறையுடன் வருகிறது.