నెట్‌వర్క్‌లపై ఒక పరిమితి, ఇప్పుడు ప్రతి పరిమాణానికీ నిరూపితం

కొన్ని బిందువులను తీసుకుని, వాటిలో కొన్ని జతలను గీతలతో కలపండి. గణిత శాస్త్రవేత్తలు దీన్ని గ్రాఫ్ (graph) అంటారు: బిందువులు దాని శీర్షాలు (vertices), గీతలు దాని అంచులు (edges), రెండు శీర్షాల మధ్య దూరం అంటే ఒకదాని నుంచి మరోదానికి నడవడానికి అవసరమైన అతి తక్కువ అంచుల సంఖ్య. ఇప్పుడు రెండు నియమాలు చేర్చండి. ప్రతి శీర్షాల జతా గరిష్ఠంగా 2 దూరంలో ఉండాలి — నేరుగా కలపబడి, లేదా ఒక ఉమ్మడి పొరుగు శీర్షం ద్వారా. ఏ అంచూ అదనంగా ఉండకూడదు: ఏ ఒక్క అంచును తొలగించినా, ఏదో ఒక జత రెండు అడుగుల కంటే ఎక్కువ దూరమైపోవాలి. అలాంటి గ్రాఫ్‌ను వ్యాసం-2-క్లిష్ట (diameter-2-critical) గ్రాఫ్ అంటారు. దానికి ఎన్ని అంచులు ఉండగలవు?

మాంటెల్ పైకప్పు, ఇంకా సాహసోపేతమైన ఒక ఊహ

1907లో, త్రిభుజం లేని — అంటే మూడు శీర్షాలూ ఒకదానితో ఒకటి కలపబడి ఉండని — n శీర్షాల గ్రాఫ్‌కు గరిష్ఠంగా ⌊n²/4⌋ అంచులు ఉంటాయని మాంటెల్ నిరూపించారు: 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ల గోపురం

జోల్టాన్ ఫ్యూరెడి ఉటంకించిన ఎర్డోష్ మాటల ప్రకారం, ఈ ప్రశ్న 1960లలో ఓర్ చేసిన కృషి నాటిది. యాన్ ప్లెస్నిక్ 1975లో అంచుల పరిమితిని ఒక ఊహగా ప్రకటించారు; మూర్తి, సైమన్ స్వతంత్రంగా దీన్ని ప్రతిపాదించి, సమతుల్య సంపూర్ణ ద్విభాగ గ్రాఫ్ ఒక్కటే అంత్య సందర్భం అని జోడించారు — అందుకే మూర్తి–సైమన్ ఊహ (Murty–Simon conjecture). 1970లు, 1980లలో, c·n² రూపంలోని పరిమితులు నెమ్మదిగా కిందికి దిగాయి, c అంతకంతకూ 1/4కు దగ్గరవుతూ.

1992లో, ఫ్యూరెడి తగినంత పెద్ద ప్రతి nకూ ఈ ఊహను క్రమబద్ధత పద్ధతులతో (regularity methods) — సెమెరేడి క్రమబద్ధత లెమ్మా నుంచి ఉద్భవించిన సాధనాలతో — నిరూపించారు. మూల్యం ప్రారంభ పరిమాణం: n కనీసం సుమారు 10¹⁴ ఎత్తైన 2ల గోపురం అంత ఉండాలి, అంటే 2 ఘాతం 2 ఘాతం 2…, పై నుంచి కిందికి లెక్కించినది — ప్రతి 2ను తన పైనున్న మొత్తానికి ఘాతంగా పెంచుతూ — ఆ దొంతరలో సుమారు 10¹⁴ రెండులు ఉండేలా. ఆ పరిమాణం కంటే తక్కువ ఉన్నవాటిలో, ప్రత్యేక గ్రాఫ్ కుటుంబాలు మాత్రమే తేలాయి.

అంచులకూ లేని అంచులకూ మధ్య పోటీ

స్టాన్‌ఫర్డ్ విశ్వవిద్యాలయపు గణిత శాస్త్ర విభాగానికి చెందిన సంజనా దాస్, జేకబ్ ఫాక్స్ ఇచ్చిన కొత్త నిరూపణ 3 నుంచి మొదలుకొని ప్రతి nకూ పనిచేస్తుంది. అది ఒక గరిష్ఠ జతకూర్పును (maximal matching) వాడుతుంది: ఏ రెండూ ఒక శీర్షాన్ని పంచుకోని అంచుల సమితి, దానికి ఇంకే అంచును చేర్చినా వాటిలో రెండు కలుసుకుంటాయి. n శీర్షాలపై ఒక జతకూర్పులో గరిష్ఠంగా ⌊n/2⌋ అంచులు ఉంటాయి.

కీలక లెమ్మా: వ్యాసం-2-క్లిష్ట గ్రాఫ్‌లో, ఏ గరిష్ఠ జతకూర్పుకైనా, జతకూర్పు బయటి అంచులు లేని అంచుల (non-edges) కంటే ఎప్పుడూ ఎక్కువ ఉండవు — లేని అంచులంటే కలపబడని శీర్షాల జతలు. మిగతాదంతా అంకగణితం. అంచుల సంఖ్యకు రెట్టింపు, జతల సంఖ్య ప్లస్ జతకూర్పు పరిమాణం కంటే ఎక్కువ ఉండదు. 10 శీర్షాలతో: 45 జతలు ప్లస్ గరిష్ఠంగా 5 జతకూర్పు అంచులు కలిపి 50, కాబట్టి గరిష్ఠంగా 25 అంచులు. ప్రతి nకూ, ఆ మొత్తం సరిగ్గా మాంటెల్ పైకప్పుకు రెట్టింపు అవుతుంది.

లెమ్మా స్వయంగా జాగ్రత్తగా చేసిన లెక్కల నిర్వహణ. ఒక లేని అంచు చివర్లను ఒకే ఒక రెండు అడుగుల మార్గం కలిపితే, అది క్లిష్టమైనది (critical) — చిత్రం 1లోని పన్నెండు లేని అంచులూ అలాంటివే. రచయితలు ప్రతి క్లిష్ట లేని అంచునూ దాని మార్గంలోని రెండు అంచులకు జోడించి, అలా ఏర్పడిన వలను అనుసంధానిత ముక్కలుగా విడగొడతారు. ఒక ముక్కలో క్లిష్ట లేని అంచుల కంటే గరిష్ఠంగా ఒక అంచు మాత్రమే ఎక్కువ ఉంటుంది, ఆ మిగులు ఉన్న ప్రతి ముక్కకూ ఒక క్లిష్టం కాని లేని అంచు మూల్యం చెల్లించాలి. వాటిని కనుగొనడానికి, రచయితలు మార్పిడి నిష్క్రమణలను (switch exits) వాడుతారు: ముక్కలోని ఒక అంచును గానీ క్లిష్ట లేని అంచును గానీ తీసుకుని, దాని ఒక చివరను జతకూర్పులో ఆ చివరకు జోడీగా ఉన్న శీర్షంతో మార్చండి. ప్రతి క్లిష్టం కాని లేని అంచునూ గరిష్ఠంగా రెండు సార్లు క్లెయిమ్ చేస్తారు, మిగులు ఉన్న ప్రతి ముక్కా కనీసం రెండు క్లెయిమ్‌లు చేస్తుంది, దాంతో లెక్క సరిపోతుంది.

ఏది ఎవరు కనుగొన్నారు

“ఈ నిరూపణను ఎక్కువగా AI కనుగొంది, ప్రత్యేకంగా 2026 ఆగస్టు 11న GPT-5.6 Sol,” అని రచయితలు ఒక చిన్న AI ప్రకటనలో రాశారు. మోడల్ ⌊n²/4⌋ పరిమితికి ఒక పూర్తి నిరూపణను కనుగొంది, దాన్ని వారు సరళీకరించారు. సరి సంఖ్యలో శీర్షాలకు, సమతుల్య సంపూర్ణ ద్విభాగ గ్రాఫ్ ఒక్కటే అంత్య సందర్భం అని కూడా అది నిరూపించింది; దీనికి, ప్రతి గరిష్ఠ జతకూర్పూ సంపూర్ణమైనది (perfect) — అంటే ప్రతి శీర్షాన్నీ కప్పేది — అయిన గ్రాఫ్‌ల గురించి సమ్నర్ నిరూపించిన ఒక వాస్తవంపై అది ఆధారపడింది.

బేసి సంఖ్యలో శీర్షాలు ఉన్నప్పుడు, ఏ జతకూర్పూ సంపూర్ణం కాదు, పైగా చాలా గ్రాఫ్‌లలో ప్రతి గరిష్ఠ జతకూర్పూ సరిగ్గా ఒక శీర్షాన్ని వదిలేస్తుంది: మోడల్ వాదనను దీనికి అనుగుణంగా మార్చడం కుదరలేదు. రచయితలు సమానత్వ సందర్భానికి ప్రతి nకూ చెల్లే ఒక వేరే నిరూపణను కనుగొని, పత్రాన్ని స్వయంగా రాశారు; GPT-6 Astra ద్వారా చేసిన చివరి పరిశీలన “కొన్ని చిన్న సవరణలకు” దారితీసింది. ఈ పత్రం ఒక ప్రీప్రింట్, ఇంకా సహ సమీక్ష (peer review) జరగలేదు, వాదనకు కంప్యూటర్ ద్వారా ధ్రువీకరించిన రూపం ఏదీ అది ప్రస్తావించలేదు.

తిరిగి 1907కు

ఒక గ్రాఫ్ పైకప్పును సమం చేస్తే, ప్రతి గరిష్ఠ జతకూర్పుకూ కీలక అసమానత సమానత్వం అవుతుంది. జతకూర్పులను తెలివిగా ఎంచుకుంటూ, అలాంటి గ్రాఫ్ ఒక నక్షత్రం (star) — ఒక శీర్షం మిగతా అన్నింటితో కలపబడి, ఇంకేమీ లేనిది — అయినా అవుతుందని, లేదా దానిలో క్లిష్ట లేని అంచే ఉండదని రచయితలు చూపిస్తారు. వ్యాసం-2-క్లిష్ట గ్రాఫ్‌లో, త్రిభుజంలోని ప్రతి అంచూ ఏదో ఒక క్లిష్ట మార్గంపై ఉంటుంది, కాబట్టి క్లిష్ట లేని అంచు లేదంటే త్రిభుజం లేదు; నక్షత్రంలో కూడా త్రిభుజం ఉండదు. కాబట్టి పైకప్పును సమం చేసే గ్రాఫ్ త్రిభుజరహితం, చివరి అడుగు ఈ ఊహ బలపరచడానికి బయలుదేరిన సిద్ధాంతమే: మాంటెల్ 1907 ఫలితం, అది సమతుల్య సంపూర్ణ ద్విభాగ గ్రాఫ్‌ను ఒక్కదాన్నే పైకప్పు వద్ద నిలుపుతుంది.