கணிதம்முன்பதிப்புகோட்பாடுபடிக்க 3 நிமிடங்கள்

சீரற்ற வலையமைப்புகள் ஒரு நிலையான அடர்த்தியில் வண்ணமிட முடியாதவையாகின்றன

ஒரு வரைபடத்தை (graph) — இணைப்புகளால் இணைக்கப்பட்ட புள்ளிகள் — ஒரு பெட்டி நிறங்களுடன் எடுத்துக்கொள்ளுங்கள். q நிறங்களைக் கொண்ட ஒரு முறையான வண்ணமிடல் (proper colouring), இணைக்கப்பட்ட இரண்டு புள்ளிகள் ஒருபோதும் ஒரே நிறத்தைப் பகிராதபடி, ஒவ்வொரு புள்ளிக்கும் q நிறங்களில் ஒன்றைத் தருகிறது. சில இணைப்புகளே இருந்தால், அது எளிது. பல இருந்தால், அது சாத்தியமற்றதாகிறது.

இப்போது வரைபடத்தைச் சீரற்ற முறையில் கட்டமைக்கவும்: n புள்ளிகள்; ஒவ்வொரு புள்ளி இணையும் ஒரு சிறிய நிகழ்தகவுடன், மற்றவற்றைச் சாராமல் இணைக்கப்படுகிறது; இதனால் ஒரு புள்ளிக்குச் சராசரியாக d அண்டைப் புள்ளிகள் இருக்கும். d வளர வளர, சீரற்ற வரைபடம் “q நிறங்களால் கிட்டத்தட்ட உறுதியாக வண்ணமிடக்கூடியது” என்ற நிலையிலிருந்து “கிட்டத்தட்ட உறுதியாக வண்ணமிட முடியாதது” என்ற நிலைக்குச் செல்கிறது. அந்த மாற்றம் சரியாக எங்கே நிகழ்கிறது? மூன்று முதல் எந்த ஒரு நிலையான நிற எண்ணிக்கை q-க்கும், அந்தக் கேள்வியே கேம்பிரிட்ஜ் பல்கலைக்கழகத்தைச் (University of Cambridge) சேர்ந்த Gaia Carenini எழுதிய ஒரு புதிய ஆய்வுக் கட்டுரையின் பொருள்.

அலைபாயக்கூடிய ஒரு மாற்றம்

நூற்பட்டியலில் இடம்பெற்றுள்ள 1999-ஆம் ஆண்டின் ஒரு கட்டுரையில், Achlioptas, Friedgut ஆகியோர் இந்த நிலைமாற்றம் கூர்மையானது (sharp) என்று நிரூபித்தனர்: ஒவ்வொரு அளவு n-க்கும், d_q(n) என்ற ஒரு மாறுநிலைச் சராசரிப் படி (critical average degree) உள்ளது; அதற்குச் சற்றுக் கீழே வரைபடம் கிட்டத்தட்ட உறுதியாக வண்ணமிடக்கூடியது, சற்று மேலே கிட்டத்தட்ட உறுதியாக வண்ணமிட முடியாதது. மாற்றம் நிகழும் சாளரம் சுருங்கி ஒன்றுமில்லாமல் போகிறது.

ஆனால் அது ஓர் ஓட்டையை விட்டுச்சென்றது. வரைபடங்கள் பெரிதாகும்போது மாறுநிலை மதிப்பே அலைவுறுவதை (oscillating) எதுவும் தடுக்கவில்லை — ஓர் அளவிலான வரைபடங்களுக்கு ஓரிடத்திலும், பெரியவற்றுக்குச் சற்று வேறிடத்திலும் இருந்து, ஒருபோதும் நிலைபெறாமல். Achlioptas–Friedgut ஒருங்கல் அனுமானம் (convergence conjecture) இது நிகழாது என்கிறது: ஒவ்வொரு q-க்கும் d_q என்ற ஒற்றை மாறிலி உள்ளது; அதற்குக் கீழே சீரற்ற வரைபடங்கள் வண்ணமிடக்கூடியவை, அதற்கு மேலே அவ்வாறு இல்லை.

இயற்பியலாளர்கள் முன்னுரைத்தது

என்ன நடக்கிறது என்பது பற்றிப் புள்ளியியல் இயற்பியலிடம் ஒரு சித்திரம் இருந்தது. இணைப்புகள் சேர்க்கப்படும்போது, செல்லுபடியான வண்ணமிடல்கள் கொத்துகளாகத் (clusters) திரள்கின்றன: ஒரு கொத்துக்குள் உள்ள வண்ணமிடல்கள் ஒன்றையொன்று ஒத்திருக்கின்றன; இரண்டு கொத்துகளோ பல புள்ளிகளில் வேறுபடுகின்றன. பின்னர், ஒடுக்கம் (condensation) எனப்படும் ஒரு கட்டத்தில், ஒரு சில பெரிய கொத்துகள் அனைத்து வண்ணமிடல்களிலும் கணிசமான பங்கைக் கொண்டிருக்கின்றன — அதன் பிறகுதான் வண்ணமிடல்களின் தொகுப்பு வெறுமையாகிறது. வரம்புக்கு அருகில் எண்ணிக்கை அடிப்படையிலான வாதங்கள் ஏன் தடுமாறுகின்றன என்பதை அந்த ஒழுங்கமைப்பு விளக்குகிறது.

பல நிறங்களுக்கு, முந்தைய ஆய்வுகள் ஏற்கெனவே வரம்பை ஒரு குறுகிய வீச்சுக்குள் அடைத்திருந்தன: அது ஏறக்குறைய 2q log q − log q − 2 log 2 என்பதற்கும் 2q log q − log q − 1 என்பதற்கும் இடையில் உள்ளது; q வளரும்போது இது 2 log 2 − 1 அகலமுள்ள ஓர் இடைவெளி. ஆனால் “குறுகியது” என்பது “நிலையானது” அல்ல; மூன்று போன்ற சிறிய எண்ணிக்கையிலான நிறங்களுக்கு, கேள்வி திறந்தே இருந்தது.

முதலில் எதிர்கொள்ளப்பட்ட ஓர் இரட்டைச் சிக்கல்

வண்ணமிடலுக்கு ஓர் இரட்டை உண்டு: நிறைவுசெய்யத்தக்க தன்மை (satisfiability) — சீரற்ற தருக்கக் கட்டுப்பாடுகளின் ஒரு பட்டியல் முழுவதும் உண்மையாகும்படி, மாறிகளுக்கு உண்மை அல்லது பொய் மதிப்புகளைத் தேர்ந்தெடுக்கும் சிக்கல். அங்கும், ஒரு கூர்மையான வரம்பு இருப்பது அறியப்பட்டிருந்தது; ஆனால் அது நிலைபெறுகிறது என்பதற்கு நிரூபணம் இல்லை. கட்டுரையில் மேற்கோள் காட்டப்பட்டுள்ள 2026-ஆம் ஆண்டின் ஓர் அறிக்கையில், மூன்று முதல் ஒவ்வொரு கட்டுப்பாட்டு நீளத்துக்கும் அது நிலைபெறுகிறது என்பதற்கான ஒரு நிரூபணத்தை Carenini அறிவித்தார்; நிலைமாற்றச் சாளரம் மிகக் குறுகியது என்று காட்டுவதன் மூலம். புதிய கட்டுரை அந்த வாதத்தை வண்ணமிடலுக்குத் தகவமைக்கிறது.

ஒன்றாக உறைந்த இணைகள்

நிரூபணம் தொடர்ச்சியான குறைப்புகளின் வழியாக முன்னேறுகிறது. சீரற்ற இணைப்புகளை ஒவ்வொன்றாகச் சேர்க்கும்போது, வரைபடம் வண்ணமிட முடியாததாக மாறும் தருணத்தை H என்போம். ஒரு சீரற்ற வரைபடத்திலிருந்து மற்றொன்றுக்கு H சிறிதளவே மாறினால் — சுமார் n/(log n)² இணைப்புகள் கொண்ட ஒரு சாளரத்துக்குள் — வரம்பு நிலைபெற்றே ஆக வேண்டும். ஒரு செவ்வியல் சமனின்மை இதை, வண்ணமிடக்கூடிய கடைசி வரைபடம் பற்றிய ஒரு கேள்வியாக மாற்றுகிறது: சராசரியாக, அது எத்தனை புதிய சீரற்ற இணைப்புகளைத் தாங்கி நிலைக்கிறது?

இங்கேதான் முக்கியக் கருத்து வருகிறது: உறைந்த இணைகள் (frozen pairs). ஒவ்வொரு செல்லுபடியான வண்ணமிடலும் இரண்டு புள்ளிகளுக்கு ஒரே நிறத்தைத் தரும்போது, அவை ஓர் உறைந்த இணையை உருவாக்குகின்றன. ஒரு புதிய இணைப்பு அத்தகைய ஓர் இணையை இணைக்கும்போது, சரியாக அப்போதுதான் அது அழிவுகரமானதாகிறது. தனிப் புள்ளிகள் ஒரு குறிப்பிட்ட நிறத்தில் உறைந்திருக்க முடியாது; ஏனெனில் நிறங்களை ஒன்றுக்கொன்று இடம் மாற்றினால் எப்போதும் இன்னொரு செல்லுபடியான வண்ணமிடல் கிடைக்கிறது; கட்டாயமாக்கப்படுவது இரண்டு புள்ளிகளுக்கு இடையிலான ஓர் உறவு. இணைப்புகள் சேர்க்கப்படும்போது இந்த உறைந்த வகுப்புகள் எவ்வாறு வளர்கின்றன என்பதை Carenini பின்தொடர்கிறார்; ஓர் இணைப்பையோ ஒரு முழுப் புள்ளியையோ நீக்கி, மீண்டும் தோன்றும் தேர்வுகளைப் பார்ப்பதன் மூலம். வண்ணமிடக்கூடிய கடைசி வரைபடம் நீண்ட காலம் நிலைக்க முடியாது என்று மதிப்பீடுகள் காட்டுகின்றன; இது அனுமானத்தை நிரூபிக்கும் அளவுக்குச் சாளரத்தைக் குறுக்குகிறது.

இன்னும் அறியப்படாதது

q ≥ 3 என்ற ஒவ்வொரு மதிப்புக்கும் வரம்பு d_q இருக்கிறது என்று தேற்றம் கூறுகிறது. அது எங்கே இருக்கிறது என்று அது சொல்லவில்லை: மூன்று நிறங்களுக்குக் கூட, கட்டுரை அதற்கு எந்த மதிப்பையும் தரவில்லை. கட்டுரை ஒற்றை ஆசிரியரைக் கொண்ட ஒரு முன்பதிப்பு; இது இன்னும் சக மதிப்பாய்வு செய்யப்படவில்லை. அதன் கணித வாதங்கள் எதுவும் ஒரு பெரிய மொழி மாதிரியால் உருவாக்கப்படவில்லை என்ற ஒரு சிறு அறிவிப்புடன் அது முடிகிறது.