نیٹ ورکس کی ایک حد، اب ہر جسامت کے لیے ثابت

چند نقطے لیجیے اور ان میں سے کچھ جوڑوں کو لکیروں سے ملا دیجیے۔ ریاضی دان اسے گراف (graph) کہتے ہیں: نقطے اس کے راس (vertices) ہیں، لکیریں اس کے کنارے (edges)، اور دو راسوں کے درمیان فاصلہ کناروں کی وہ کم سے کم تعداد ہے جو ایک سے دوسرے تک چلنے کے لیے درکار ہو۔ اب دو اصول جوڑیے۔ راسوں کا ہر جوڑا زیادہ سے زیادہ 2 کے فاصلے پر ہونا چاہیے — براہِ راست جڑا ہوا، یا کسی مشترکہ پڑوسی کے ذریعے۔ اور کوئی کنارہ فالتو نہیں ہونا چاہیے: کسی بھی ایک کو حذف کیجیے، تو کوئی جوڑا دو قدموں سے زیادہ دور ہو جاتا ہے۔ ایسے گراف کو قطر-2-نازک (diameter-2-critical) کہا جاتا ہے۔ اس کے کتنے کنارے ہو سکتے ہیں؟

مینٹل کی چھت، اور ایک زیادہ جرات مندانہ اندازہ

1907 میں مینٹل (Mantel) نے ثابت کیا کہ n راسوں پر ایک ایسا گراف جس میں کوئی مثلث نہ ہو — یعنی کوئی تین راس جو سب ایک دوسرے سے جڑے ہوں — زیادہ سے زیادہ ⌊n²/4⌋ کنارے رکھتا ہے: n کا مربع چار سے تقسیم، نیچے کی طرف ایک پورے عدد تک گول کیا ہوا۔ صرف ایک گراف اس چھت تک پہنچتا ہے، یعنی متوازن مکمل دو حصی گراف (balanced complete bipartite graph): دو گروہ جو جسامت میں جتنے ممکن ہو برابر ہوں، ایک کا ہر راس دوسرے کے ہر راس سے جڑا ہوا، کسی گروہ کے اندر کوئی کنارہ نہیں۔

ہر بے مثلث گراف جو مثلث بنائے بغیر ایک اور کنارہ نہ لے سکے، قطر-2-نازک ہوتا ہے۔ الٹ درست نہیں: بعض قطر-2-نازک گرافوں میں مثلث ہوتے ہیں۔

7 راسوں اور 9 کناروں والا ایک قطر-2-نازک گراف، جس میں مثلث v1v3v5 شامل ہے۔ v1v3 کو حذف کرنا v2 اور v3 کے درمیان دو قدمی واحد راستہ ختم کر دیتا ہے؛ مثلث سے باہر کسی کنارے کو حذف کرنا اس کے سروں کو کسی دو قدمی راستے کے بغیر چھوڑ دیتا ہے۔ — شکل 1، Das & Fox (2026)، arXiv:2610.39032۔

اندازہ یہ تھا کہ مثلثوں سے کچھ حاصل نہیں ہوتا: n راسوں پر ایک قطر-2-نازک گراف بھی زیادہ سے زیادہ ⌊n²/4⌋ کنارے رکھتا ہے، اور متوازن مکمل دو حصی گراف ہی اب بھی واحد گراف ہے جو اس تک پہنچتا ہے۔ مینٹل کا مسئلہ ایک خاص صورت کے طور پر اس سے نکل آتا۔ شکل کے 7 راسوں کے لیے چھت 12 کنارے ہے۔

2 کا ایک مینار

ایردوش (Erdős) کے مطابق، جیسا کہ زولتان فوریدی (Zoltán Füredi) نے بیان کیا، یہ سوال 1960 کی دہائی میں اور (Ore) کے کام تک جاتا ہے۔ یان پلیسنک (Ján Plesník) نے 1975 میں کناروں کی حد کو ایک قیاس کے طور پر بیان کیا؛ مرتی اور سائمن (Murty and Simon) نے آزادانہ طور پر یہی تجویز کیا اور اضافہ کیا کہ متوازن مکمل دو حصی گراف واحد انتہائی صورت ہے — اسی لیے مرتی–سائمن قیاس (Murty–Simon conjecture)۔ 1970 اور 1980 کی دہائیوں میں c·n² کی شکل کی حدیں آہستہ آہستہ نیچے آئیں، جن میں c مسلسل 1/4 کے قریب ہوتا گیا۔

1992 میں فوریدی نے باقاعدگی کے طریقوں (regularity methods) — یعنی سیمیریڈی (Szemerédi) کے باقاعدگی لیما سے ماخوذ آلات — کے ذریعے ہر کافی بڑے n کے لیے قیاس ثابت کیا۔ قیمت ابتدائی جسامت تھی: n کو کم از کم تقریباً 10¹⁴ اونچائی کا 2 کا ایک مینار ہونا تھا، یعنی 2 کی طاقت 2 کی طاقت 2…، جسے اوپر سے نیچے کی طرف حل کیا جاتا ہے — ہر 2 کو اپنے اوپر کی ہر چیز کی طاقت تک اٹھایا جاتا ہے — ڈھیر میں تقریباً 10¹⁴ دو کے ساتھ۔ اس جسامت سے نیچے صرف گرافوں کے خاص خاندانوں کا فیصلہ ہوا تھا۔

کنارے بمقابلہ غائب کنارے

اسٹینفورڈ یونیورسٹی کے شعبۂ ریاضی کی سنجنا داس (Sanjana Das) اور جیکب فاکس (Jacob Fox) کا نیا ثبوت 3 سے اوپر ہر n کے لیے کام کرتا ہے۔ یہ ایک اعظمی مطابقت (maximal matching) استعمال کرتا ہے: کناروں کا ایک مجموعہ، جن میں سے کوئی دو ایک راس میں شریک نہ ہوں، جس میں کوئی اور کنارہ ان میں سے دو کے ملے بغیر شامل نہ کیا جا سکے۔ n راسوں پر ایک مطابقت زیادہ سے زیادہ ⌊n/2⌋ کنارے رکھتی ہے۔

کلیدی لیما (lemma): ایک قطر-2-نازک گراف میں، کسی بھی اعظمی مطابقت کے لیے، مطابقت سے باہر کے کنارے غیر کناروں سے کبھی زیادہ نہیں ہوتے — یعنی راسوں کے وہ جوڑے جو جڑے ہوئے نہیں۔ باقی حساب ہے۔ کناروں کی تعداد کا دگنا زیادہ سے زیادہ جوڑوں کی تعداد جمع مطابقت کی جسامت ہے۔ 10 راسوں کے ساتھ: 45 جوڑے جمع زیادہ سے زیادہ 5 مطابقتی کنارے 50 بنتے ہیں، لہٰذا زیادہ سے زیادہ 25 کنارے۔ ہر n کے لیے یہ مجموعہ ٹھیک مینٹل کی چھت کا دگنا بنتا ہے۔

لیما خود ایک محتاط حساب کتاب ہے۔ ایک غیر کنارہ نازک (critical) ہے اگر ایک ہی دو قدمی راستہ اس کے سروں کو جوڑتا ہو، جیسا کہ شکل 1 کے تمام بارہ غیر کناروں کے لیے ہے۔ مصنفین ہر نازک غیر کنارے کو اس کے راستے کے دو کناروں سے منسلک کرتے ہیں اور حاصل ہونے والے جال کو جڑے ہوئے ٹکڑوں میں بانٹ دیتے ہیں۔ ایک ٹکڑا نازک غیر کناروں سے زیادہ سے زیادہ ایک کنارہ زیادہ رکھتا ہے، اور اس فاضل والے ہر ٹکڑے کی قیمت ایک غیر نازک غیر کنارے سے ادا ہونی چاہیے۔ انہیں ڈھونڈنے کے لیے مصنفین تبادلی نکاس (switch exits) استعمال کرتے ہیں: ٹکڑے کا کوئی کنارہ یا نازک غیر کنارہ لیجیے اور اس کے ایک سرے کو مطابقت میں اس سرے کے ساتھی سے بدل دیجیے۔ ہر غیر نازک غیر کنارے پر زیادہ سے زیادہ دو بار دعویٰ کیا جاتا ہے، فاضل والا ہر ٹکڑا کم از کم دو دعوے کرتا ہے، اور گنتی پوری ہو جاتی ہے۔

کس نے کیا ڈھونڈا

مصنفین مصنوعی ذہانت سے متعلق ایک مختصر بیان میں لکھتے ہیں: “یہ ثبوت زیادہ تر مصنوعی ذہانت نے ڈھونڈا، بالخصوص GPT-5.6 Sol نے 11 اگست 2026 کو”۔ ماڈل نے ⌊n²/4⌋ کی حد کا ایک مکمل ثبوت ڈھونڈا، جسے انہوں نے سادہ کیا۔ راسوں کی جفت تعداد کے لیے اس نے یہ بھی ثابت کیا کہ متوازن مکمل دو حصی گراف واحد انتہائی صورت ہے، سمنر (Sumner) کے ثابت کردہ ایک حقیقت پر انحصار کرتے ہوئے جو ایسے گرافوں کے بارے میں ہے جن میں ہر اعظمی مطابقت کامل (perfect) ہو، یعنی ہر راس کا احاطہ کرے۔

راسوں کی طاق تعداد کے ساتھ کوئی مطابقت کامل نہیں ہوتی، اور بہت سے گرافوں میں ہر اعظمی مطابقت ٹھیک ایک راس چھوڑ دیتی ہے: ماڈل کے استدلال کو ڈھالا نہیں جا سکا۔ مصنفین نے مساوات کی صورت کا ایک مختلف ثبوت ڈھونڈا، جو ہر n کے لیے درست ہے، اور مقالہ خود لکھا؛ GPT-6 Astra سے ایک آخری نظرثانی “چند معمولی ترامیم” کا باعث بنی۔ مقالہ ایک پری پرنٹ ہے، ابھی ہم مرتبہ جائزے سے نہیں گزرا، اور اس میں استدلال کے کسی کمپیوٹر سے جانچے گئے نسخے کا ذکر نہیں۔

واپس 1907 کی طرف

اگر کوئی گراف چھت کے برابر ہو، تو کلیدی عدم مساوات ہر اعظمی مطابقت کے لیے مساوات بن جاتی ہے۔ ہوشیاری سے مطابقتیں چن کر مصنفین دکھاتے ہیں کہ ایسا گراف یا تو ایک ستارہ (star) ہے — ایک راس جو باقی سب سے جڑا ہو، اور کچھ نہیں — یا اس میں کوئی نازک غیر کنارہ ہے ہی نہیں۔ ایک قطر-2-نازک گراف میں مثلث کا ہر کنارہ کسی نازک راستے پر ہوتا ہے، اس لیے کوئی نازک غیر کنارہ نہ ہونے کا مطلب ہے کوئی مثلث نہیں؛ ستارے میں بھی کوئی مثلث نہیں ہوتا۔ لہٰذا چھت کے برابر آنے والا گراف بے مثلث ہے، اور آخری قدم وہی مسئلہ ہے جسے یہ قیاس مضبوط کرنے نکلا تھا: مینٹل کا 1907 کا نتیجہ، جو متوازن مکمل دو حصی گراف کو چھت پر اکیلا چھوڑ دیتا ہے۔