1960களின் ஒரு வரைபடப் புதிர் இறுதியாக முடிவுக்கு வருகிறது

சில புள்ளிகளை எடுத்து, அவற்றில் சில ஜோடிகளைக் கோடுகளால் இணையுங்கள்: கணிதவியலாளர்கள் இதை வரைபடம் (graph) என்றும், புள்ளிகளை அதன் முனைகள் (vertices) என்றும், கோடுகளை அதன் விளிம்புகள் (edges) என்றும் அழைக்கின்றனர். ஒரு சுற்று (cycle) என்பது தனித்தனி முனைகளுக்குச் சென்று தொடங்கிய இடத்துக்கே திரும்பும் ஒரு மூடிய சுழல். ஒரு வரைபடத்தின் விளிம்புகளை — ஒவ்வொரு விளிம்பையும் சரியாக ஒருமுறை பயன்படுத்தி — சுற்றுகளாகப் பிரிக்க முடியுமா என்பது ஓர் இயல்பான கேள்வி.

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

அனுமானம்

1960களில், எர்டோஷும் கல்லாயும் (Erdős, Gallai), n முனைகள் கொண்ட எந்த வரைபடத்தின் விளிம்புகளையும், அதிகபட்சம் n-க்கு விகிதமான எண்ணிக்கையிலான — O(n) என எழுதப்படுவது — சுற்றுகளாகவும் தனி விளிம்புகளாகவும் பிரிக்க முடியும் என்று அனுமானித்தனர். எர்டோஷ் இதைத் தீர்க்கப்படாத சிக்கல்களின் தனது பல தொகுப்புகளில் சேர்த்தார். ஹயோஷின் (Hajós) தொடர்புடைய ஓர் அனுமானம், ஒவ்வொரு ஆய்லர் வரைபடத்திலும் அதிகபட்சம் (n − 1)/2 சுற்றுகளைக் கோருகிறது.

நேரியல் (linear) வரம்புதான் எதிர்பார்க்கக்கூடிய சிறந்தது: சில வரைபடங்களுக்குச் சுமார் 1.5 n துண்டுகள் தேவை என்று எர்டோஷ் காட்டினார். n-இன் ஏதேனும் ஒரு மாறிலி மடங்கு எப்போதும் போதுமா என்பதே கேள்வி.

மெல்ல நகர்ந்த வரம்புகளின் ஐம்பது ஆண்டுகள்

எர்டோஷும் கல்லாயும் தாங்களே ஓர் எளிய வழியைக் கவனித்தனர்: மிக நீளமான சுற்றைத் திரும்பத் திரும்ப நீக்குவது. இது சுமார் n log n துண்டுகளைத் தருகிறது — கட்டுரையின்படி, கிட்டத்தட்ட ஐம்பது ஆண்டுகள் இதுவே சிறந்த பொது வரம்பாக இருந்தது. சமீபத்தில், கான்லன், ஃபாக்ஸ், சுடகோவ் ஆகியோர் இதை n log log n ஆகக் குறைத்தனர்; பின்னர் புசிச், மாண்ட்கோமரி ஆகியோர் n log* n ஆகக் குறைத்தனர்; இங்கே log* n — ஒன்றுக்குக் கீழே வர எத்தனை முறை மடக்கை (logarithm) எடுக்க வேண்டும் என்பது — கற்பனைக்கு எட்டாத அளவு மெதுவாக வளர்கிறது. இந்த அணுகுமுறைகள் சுற்றுகளாக (rounds) இயங்கின; ஒவ்வொரு சுற்றும் சுமார் n சுழல்களைச் செலவழித்தது; எனவே சுற்றுகளின் எண்ணிக்கை எப்போதும் இறுதி எண்ணிக்கையில் நுழைந்துவிட்டது. சீரற்ற வரைபடங்கள் (random graphs) போன்ற சிறப்புக் குடும்பங்களுக்கும் இந்த அனுமானம் நிரூபிக்கப்பட்டிருந்தது.

சுழல்களுக்கு விலை செலுத்தும் எடைகள்

தென் கொரியாவின் KAIST-ஐச் சேர்ந்த ஜேஹூன் கிம் (Jaehoon Kim) இப்போது அனுமானத்தை நிரூபிக்கிறார்: n முனைகள் கொண்ட ஒவ்வொரு வரைபடமும் அதிகபட்சம் Cn சுற்றுகளாகவும் விளிம்புகளாகவும் பிரியும்படியான ஒரு நிலையான மாறிலி C உள்ளது. இதன் விளைவாக, ஹயோஷின் அனுமானம் ஒரு மாறிலிக் காரணி வரை உண்மையாகிறது.

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

• பாகைகளை (degrees) அடிப்படையாகக் கொண்ட ஒரு நிலையாற்றல் (potential). ஒவ்வொரு முனையும், அதன் விளிம்புகளின் எண்ணிக்கை கூடக்கூடச் சுருங்கும் ஓர் எடையைப் பெறுகிறது, தோராயமாக 1 / (degree × log² degree). ஒரு சுற்றின் முனைகளின் எடைகளின் கூட்டுத்தொகை குறைந்தது 1 என்றால், அந்தச் சுற்று கனமானது. ஒரு கனமான சுற்றை நீக்குவது ஒட்டுமொத்த “நிலையாற்றலை” குறைந்தது 1 குறைக்கிறது; அந்த நிலையாற்றல் n-இன் ஒரு மாறிலி மடங்குக்கு மேற்படாத மதிப்பில் தொடங்குகிறது. எனவே கனமான சுற்றுகளை O(n) முறை மட்டுமே நீக்க முடியும்.
• முனைகளின் எண்ணிக்கை. கனமான சுற்று எதுவும் மிஞ்சாதபோது, வரைபடம் “இலேசானது” — பெரிய பாகைகள் கொண்ட இலேசான வரைபடம், அடர்த்தியான, கிட்டத்தட்ட மூடப்பட்ட ஒரு பகுதியைக் கொண்டிருக்க வேண்டும் என்று புதிய முதன்மைத் தேற்றம் காட்டுகிறது. அந்தப் பகுதி அதன் அளவுக்கு விகிதமான எண்ணிக்கையிலான சுற்றுகளாகவும் விளிம்புகளாகவும் பிரிக்கப்படுகிறது; அதன் பிறகு அதன் முனைகளில் குறைந்தது ஐம்பதில் ஒரு பங்கு அதிகபட்சம் இரண்டு விளிம்புகளுடன் எஞ்சி, நிரந்தரமாக வெளியேறுகின்றன. ஒவ்வொரு முனையும் ஒருமுறை மட்டுமே வெளியேற முடியும் என்பதால், இந்தப் பகுதியும் O(n) செலவே ஆகிறது.

வரைபடத்தின் அடர்த்தியான பகுதிகளுக்குள், “விரிவாக்கிகள்” (expanders) வழியாகச் செல்லும் இணைப்புப் பாதைகள் மூலம் பாதைத் துண்டுகள் ஒரே சுற்றாக மூடப்படுகின்றன; ஒரு சீரற்ற வண்ணமிடல் ஒரு சுற்றின் இணைப்புப் பாதைகளைத் தனித்தனியாக வைக்கிறது. — Figure 3, Kim (2026), arXiv:2610.07840.

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

இன்னும் திறந்திருப்பவை

மாறிலி C மிகப் பெரியது; ஆசிரியர் அதை உகப்பாக்க முயலவில்லை. சிறந்த மாறிலியைக் — குறைந்தது 1.5 — கண்டறிவது இன்னும் திறந்த கேள்வி; ஹயோஷின் துல்லியமான அனுமானமும், வரைபடங்களைப் பாதைகளாகப் (paths) பிரிப்பது குறித்த கல்லாயின் தொடர்புடைய அனுமானமும் அப்படியே. எடையிடும் உத்திக்கு, கூட்டுத்தொகை குவியும் (converges) எடைகள் மட்டுமே தேவை; இது பிற பிரிப்புச் சிக்கல்களிலும் பயன்படக்கூடும் என்று ஆசிரியர் பரிந்துரைக்கிறார்.

இது ஒற்றை ஆசிரியரின் முன்அச்சு; இன்னும் சக மதிப்பாய்வால் சரிபார்க்கப்படவில்லை.

நலன் முரண்பாடு. வாதங்களை உருவாக்குவதிலும் உரையையும் படங்களையும் தயாரிப்பதிலும் ChatGPT (OpenAI), Claude (Anthropic) ஆகியவற்றை விரிவாகப் பயன்படுத்தியதாகவும், அனைத்து முடிவுகளையும் சரிபார்த்ததாகவும், கட்டுரைக்கு முழுப் பொறுப்பேற்பதாகவும் ஆசிரியர் தெரிவிக்கிறார். நீங்கள் படிக்கும் இந்த உரையும் Claude-ஆல் எழுதப்பட்டதே.