வலைப்பின்னல்களுக்கான ஒரு வரம்பு, இப்போது எல்லா அளவுகளுக்கும் நிறுவப்பட்டது

சில புள்ளிகளை எடுத்து, அவற்றில் சில இணைகளைக் கோடுகளால் இணையுங்கள். கணிதவியலாளர்கள் இதை வரைபு (graph) என்கிறார்கள்: புள்ளிகள் அதன் முனைகள் (vertices), கோடுகள் அதன் விளிம்புகள் (edges); இரண்டு முனைகளுக்கு இடையிலான தொலைவு என்பது ஒன்றிலிருந்து மற்றொன்றுக்கு நடக்கத் தேவையான மிகக் குறைந்த விளிம்புகளின் எண்ணிக்கை. இப்போது இரண்டு விதிகளைச் சேர்க்கவும். ஒவ்வொரு முனை இணையும் அதிகபட்சம் 2 தொலைவில் இருக்க வேண்டும் — நேரடியாக இணைக்கப்பட்டோ, ஒரு பொது அண்டை முனை வழியாகவோ. எந்த விளிம்பும் உபரியாக இருக்கக் கூடாது: எந்த ஒன்றை நீக்கினாலும், ஏதோ ஓர் இணை இரண்டு படிகளுக்கு மேல் தொலைவாகிவிட வேண்டும். அத்தகைய வரைபு விட்டம்-2-நெருக்கடியானது (diameter-2-critical) எனப்படுகிறது. அதற்கு எத்தனை விளிம்புகள் இருக்க முடியும்?

மான்ட்டெலின் உச்சவரம்பும், துணிச்சலான ஓர் ஊகமும்

1907-இல், முக்கோணம் இல்லாத — மூன்றும் ஒன்றோடொன்று இணைந்த மூன்று முனைகள் இல்லாத — n முனைகள் கொண்ட வரைபுக்கு அதிகபட்சம் ⌊n²/4⌋ விளிம்புகளே உண்டு என்று மான்ட்டெல் (Mantel) நிறுவினார்: n-இன் வர்க்கத்தை நான்கால் வகுத்து, கீழ்நோக்கி முழு எண்ணாக முழுமையாக்கியது. அந்த உச்சவரம்பை ஒரே ஒரு வரைபு மட்டுமே எட்டுகிறது — சமநிலையான முழுமையான இருபகுதி வரைபு (balanced complete bipartite graph): முடிந்தவரை சம அளவிலான இரண்டு குழுக்கள், ஒன்றின் ஒவ்வொரு முனையும் மற்றொன்றின் ஒவ்வொரு முனையுடனும் இணைக்கப்பட்டு, ஒரு குழுவுக்குள் விளிம்பே இல்லாமல்.

முக்கோணத்தை உருவாக்காமல் இன்னும் ஒரு விளிம்பை ஏற்க முடியாத ஒவ்வொரு முக்கோணமற்ற வரைபும் விட்டம்-2-நெருக்கடியானது. மறுதலை உண்மையல்ல: சில விட்டம்-2-நெருக்கடியான வரைபுகளில் முக்கோணங்கள் உள்ளன.

v1v3v5 என்ற முக்கோணத்தைக் கொண்ட, 7 முனைகளும் 9 விளிம்புகளும் உள்ள ஒரு விட்டம்-2-நெருக்கடியான வரைபு. v1v3-ஐ நீக்கினால், v2-க்கும் v3-க்கும் இடையிலான ஒரே இருபடிப் பாதை அழிகிறது; முக்கோணத்துக்கு வெளியே ஒரு விளிம்பை நீக்கினால், அதன் முனைகளுக்கு இருபடிப் பாதையே இல்லாமல் போகிறது. — படம் 1, Das & Fox (2026), arXiv:2610.39032.

ஊகம் இதுதான்: முக்கோணங்கள் எதையும் கூட்டுவதில்லை; n முனைகள் கொண்ட விட்டம்-2-நெருக்கடியான வரைபுக்கு இன்னும் அதிகபட்சம் ⌊n²/4⌋ விளிம்புகளே; சமநிலையான முழுமையான இருபகுதி வரைபு மட்டுமே இன்னும் அதை எட்டுகிறது. மான்ட்டெலின் தேற்றம் ஒரு சிறப்பு நிலையாக இதிலிருந்து பின்தொடரும். படத்திலுள்ள 7 முனைகளுக்கு, உச்சவரம்பு 12 விளிம்புகள்.

2-களின் ஒரு கோபுரம்

Zoltán Füredi தெரிவித்தபடி, Erdős-இன் கூற்றுப்படி, இந்தக் கேள்வி 1960-களில் Ore செய்த ஆய்வுகளுக்குச் செல்கிறது. Ján Plesník 1975-இல் விளிம்பு வரம்பை ஓர் ஊகமாக முன்வைத்தார்; Murty, Simon ஆகியோர் தனித்தனியாக அதை முன்மொழிந்து, சமநிலையான முழுமையான இருபகுதி வரைபே ஒரே உச்ச நிலை என்றும் சேர்த்தனர் — எனவே முர்ட்டி–சைமன் ஊகம். 1970-கள், 1980-களில், c·n² வடிவிலான வரம்புகள் மெல்லக் கீழிறங்கின; c எப்போதும் 1/4-க்கு இன்னும் நெருக்கமாக வந்தது.

1992-இல், Füredi, Szemerédi-இன் ஒழுங்கமைவுத் துணைத்தேற்றத்திலிருந்து பெறப்பட்ட கருவிகளான ஒழுங்கமைவு முறைகளைக் (regularity methods) கொண்டு, போதுமான அளவு பெரிய ஒவ்வொரு n-க்கும் ஊகத்தை நிறுவினார். அதற்கான விலை தொடக்க அளவு: n குறைந்தது தோராயமாக 10¹⁴ உயரமுள்ள 2-களின் கோபுரமாக இருக்க வேண்டும் — அதாவது 2-இன் அடுக்கு 2-இன் அடுக்கு 2…, மேலிருந்து கீழாகக் கணக்கிடப்படுவது — ஒவ்வொரு 2-உம் தனக்கு மேலே உள்ள அனைத்தையும் அடுக்காகக் கொண்டு உயர்த்தப்படுகிறது — அடுக்கில் சுமார் 10¹⁴ இரண்டுகள். அந்த அளவுக்குக் கீழே, சில சிறப்பு வரைபுக் குடும்பங்கள் மட்டுமே தீர்க்கப்பட்டிருந்தன.

விளிம்புகளுக்கு எதிராக இல்லாத விளிம்புகள்

ஸ்டான்ஃபோர்ட் பல்கலைக்கழகக் கணிதத் துறையைச் சேர்ந்த Sanjana Das, Jacob Fox ஆகியோரின் புதிய நிரூபணம், 3 முதல் மேலான ஒவ்வொரு n-க்கும் செல்லுபடியாகிறது. அது ஒரு பெருமப் பொருத்தத்தைப் (maximal matching) பயன்படுத்துகிறது: எந்த இரண்டும் ஒரு முனையைப் பகிராத, இரண்டு சந்திக்காமல் மேலும் ஒரு விளிம்பைச் சேர்க்க முடியாத விளிம்புகளின் தொகுப்பு. n முனைகள் மீதான ஒரு பொருத்தம் அதிகபட்சம் ⌊n/2⌋ விளிம்புகளைக் கொண்டிருக்கும்.

முக்கியத் துணைத்தேற்றம்: விட்டம்-2-நெருக்கடியான ஒரு வரைபில், எந்தவொரு பெருமப் பொருத்தத்துக்கும், பொருத்தத்துக்கு வெளியிலுள்ள விளிம்புகள், விளிம்பற்றவைகளைவிட (non-edges) — இணைக்கப்படாத முனை இணைகளைவிட — ஒருபோதும் அதிகமல்ல. மீதி எண்கணிதம். விளிம்புகளின் எண்ணிக்கையின் இரு மடங்கு, அதிகபட்சம் இணைகளின் எண்ணிக்கையும் பொருத்தத்தின் அளவும் சேர்ந்தது. 10 முனைகளுடன்: 45 இணைகளும் அதிகபட்சம் 5 பொருத்த விளிம்புகளும் சேர்ந்து 50; எனவே அதிகபட்சம் 25 விளிம்புகள். ஒவ்வொரு n-க்கும், அந்தக் கூட்டுத்தொகை சரியாக மான்ட்டெலின் உச்சவரம்பின் இரு மடங்காகிறது.

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

யார் எதைக் கண்டுபிடித்தார்கள்

“இந்த நிரூபணம் பெரும்பாலும் செயற்கை நுண்ணறிவால், குறிப்பாக 2026 ஆகஸ்ட் 11 அன்று GPT-5.6 Sol-ஆல், கண்டுபிடிக்கப்பட்டது” என்று ஆசிரியர்கள் ஒரு சிறிய செயற்கை நுண்ணறிவு அறிக்கையில் எழுதுகிறார்கள். ⌊n²/4⌋ வரம்புக்கான முழு நிரூபணத்தை மாதிரி கண்டுபிடித்தது; அவர்கள் அதை எளிமைப்படுத்தினர். இரட்டைப்படை எண்ணிக்கையிலான முனைகளுக்கு, சமநிலையான முழுமையான இருபகுதி வரைபே ஒரே உச்ச நிலை என்பதையும் அது நிறுவியது — ஒவ்வொரு பெருமப் பொருத்தமும் ஒவ்வொரு முனையையும் உள்ளடக்கும் முழுமையான (perfect) பொருத்தமாக இருக்கும் வரைபுகள் பற்றி Sumner நிறுவிய ஓர் உண்மையைச் சார்ந்து.

ஒற்றைப்படை எண்ணிக்கையிலான முனைகளில், எந்தப் பொருத்தமும் முழுமையானதல்ல; பல வரைபுகளில் ஒவ்வொரு பெருமப் பொருத்தமும் சரியாக ஒரு முனையைத் தவறவிடுகிறது: மாதிரியின் வாதத்தைத் தகவமைக்க முடியவில்லை. சமநிலை நிலைக்கு, ஒவ்வொரு n-க்கும் செல்லுபடியாகும் வேறொரு நிரூபணத்தை ஆசிரியர்கள் கண்டுபிடித்து, ஆய்வுக்கட்டுரையைத் தாங்களே எழுதினர்; GPT-6 Astra வழியான இறுதிச் சரிபார்ப்பு “சில சிறு திருத்தங்களுக்கு” வழிவகுத்தது. ஆய்வுக்கட்டுரை ஒரு முன்பதிப்பு; இன்னும் சக மதிப்பாய்வு செய்யப்படவில்லை; வாதத்தின் கணினியால் சரிபார்க்கப்பட்ட பதிப்பு எதையும் அது குறிப்பிடவில்லை.

மீண்டும் 1907-க்கு

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