ہر نقطے کو ہر دوسرے سے جوڑیے: کم سے کم تقاطع، اب ثابت شدہ

کاغذ کے ایک ورق پر پانچ نقطے رکھیے اور ہر جوڑے کو ایک منحنی سے ملائیے: کل دس منحنیاں۔ وہ جیسے چاہیں مڑ سکتی ہیں، لیکن کوئی بھی کسی تیسرے نقطے سے نہیں گزر سکتی۔ ہر تقاطع سے بچنے کی کوشش کیجیے، اور آپ ناکام رہیں گے۔ پانچ نقطوں کے ساتھ کم از کم 1 تقاطع ناگزیر ہے؛ چھ کے ساتھ کم از کم 3؛ دس کے ساتھ کم از کم 60۔

ریاضی دان ایسی تصویر کو مکمل گراف (complete graph) Kₙ کی ڈرائنگ کہتے ہیں — n نقطے، جن کا ہر جوڑا ملا ہوا ہو — اور کسی بھی ڈرائنگ میں ممکن کم سے کم تقاطع کو اس کا عددِ تقاطع (crossing number)۔ چیک جمہوریہ کی چارلس یونیورسٹی کے مارٹن بالکو (Martin Balko) اس سوال کو “ٹوپولوجیکل گراف تھیوری کے سب سے مشہور مسائل میں سے ایک” کہتے ہیں۔

ایک فنکار کی گنتی

1950 کی دہائی کے اواخر میں برطانوی فنکار انتھونی ہل (Anthony Hill) نے Kₙ کی ایسی ڈرائنگز بنائیں جن میں بالکل

Z(n) = ¼ ⌊n/2⌋ ⌊(n − 1)/2⌋ ⌊(n − 2)/2⌋ ⌊(n − 3)/2⌋

تقاطع تھے، جہاں ⌊ ⌋ کا مطلب ہے نیچے کی طرف پورا کرنا (rounding down)۔ یہ قیاس کہ کوئی ڈرائنگ اس سے بہتر نہیں کر سکتی سب سے پہلے گائی (Guy) نے شائع کیا، بعد میں ہیراری اور ہل (Harary, Hill) نے اس پر بحث کی، اور ایردوش اور گائی (Erdős, Guy) نے اسے مقبول بنایا۔ اسے ہیراری–ہل قیاس (Harary–Hill conjecture)، یا گائی کا قیاس، کہا جاتا ہے۔

فارمولا تیزی سے بڑھتا ہے:

4 یا اس سے کم نقطے: 0 تقاطع
5 نقطے: 1
7 نقطے: 9
10 نقطے: 60
14 نقطے: 315

چھ دہائیوں کے جزوی جوابات

بالکل Z(n) تقاطع والی ڈرائنگز نقطوں کی ہر تعداد کے لیے موجود تھیں؛ مشکل حصہ یہ دکھانا تھا کہ کوئی بھی ڈرائنگ اس سے بہتر نہیں کرتی۔

ساٹھ سال سے زیادہ عرصے تک یہ بات صرف خاص قسم کی ڈرائنگز کے لیے ثابت ہوئی — مثلاً جب تمام نقطے ایک لکیر پر ہوں اور ہر منحنی اس کی ایک ہی جانب رہے، یا جب نقطے ایک کرے پر ہوں اور ہر منحنی مختصر ترین راستہ اختیار کرے۔ بالکو نے خود فولیک اور کینچل (Fulek, Kynčl) کے ساتھ ایسی ہی ایک قسم کا مسئلہ حل کیا تھا۔ 2021 تک کمپیوٹرز 14 نقطوں تک فارمولے کی تصدیق کر چکے تھے۔ نقطوں کی بہت بڑی تعداد کے لیے بہترین عمومی نتائج Z(n) کے کم از کم 98.5%، پھر 98.99%، کی ضمانت دیتے تھے۔

ایک ثبوت، پھر ایک زیادہ واضح ثبوت

2026 میں OpenAI نے نقطوں کی ہر تعداد کے لیے ایک ثبوت کا اعلان کیا، جسے بالکو کا مقالہ “OpenAI Math Release preprint” کے طور پر درج کرتا ہے اور مسئلۂ ثابتہ (theorem) کا سہرا اسی کے سر باندھتا ہے۔ مقالہ یہ نہیں بتاتا کہ وہ ثبوت کیسے تلاش کیا گیا۔ بالکو کے الفاظ میں اصل ثبوت “نسبتاً مختصر ہے”، لیکن “اسے سمجھنا کافی مشکل ہے”۔ ان کا پری پرنٹ ایک سہل شدہ نسخہ پیش کرتا ہے جس کے لیے، وہ لکھتے ہیں، “صرف خطی الجبرا اور گراف تھیوری کی ابتدائی معلومات درکار ہیں”۔ ایک اور ریاضی دان، گیلاسیو سالازار (Gelasio Salazar)، ایک الگ، تفصیلی وضاحت تیار کر رہے ہیں۔

تقاطع کے بجائے عددی سر گننا

چونکہ معلوم ڈرائنگز پہلے ہی Z(n) تک پہنچ جاتی ہیں، اس لیے صرف زیریں حد کا ثبوت درکار ہے۔ اس کے لیے چار قدم لگتے ہیں۔

طاق اعداد کافی ہیں۔ ایک بہترین ڈرائنگ کو اس طرح دوبارہ بنایا جا سکتا ہے کہ ایک نقطہ شریک رکھنے والی منحنیاں کبھی ایک دوسرے کو نہ کاٹیں؛ تب ہر تقاطع میں 4 مختلف نقطے شامل ہوتے ہیں۔ 6 نقطوں میں سے ہر ایک کو باری باری مٹائیے: بچ جانے والی ہر 5 نقطوں کی تصویر میں کم از کم 1 تقاطع ہے، اور ہر تقاطع 6 میں سے ٹھیک 2 حذف کے بعد باقی رہتا ہے (جب بھی اس کے اپنے 4 نقطوں میں سے کوئی ایک مٹایا جائے تو یہ غائب ہو جاتا ہے، اور باقی 2 کے بعد بچا رہتا ہے)۔ لہٰذا تقاطع کی تعداد کا دوگنا کم از کم 6 ہے: یعنی کم از کم 3، جو Z(6) ہے۔ یہی گنتی ہر جفت عدد کے لیے کام کرتی ہے۔
کثیر رقمیوں کا ایک خاندان۔ ہر نقطے کو اس کا اپنا عدد دیجیے۔ ایک تقاطع میں دو منحنیاں شامل ہوتی ہیں، یعنی چار نقطے، یعنی چار اعداد۔ بالکو چار متغیرات والی کثیر رقمیاں (polynomials) استعمال کرتے ہیں، جنہیں اس طرح چنا گیا ہے کہ n طاق ہونے پر اس خاندان کے بالکل Z(n) آزاد عددی سر (coefficients) ہوں — 7 نقطوں کے لیے 3 × 3 = 9۔
بہت کم تقاطع گنجائش چھوڑ دیتے ہیں۔ کسی کثیر رقمی سے یہ تقاضا کرنا کہ وہ کسی تقاطع پر صفر ہو جائے، ایک مساوات ہے۔ جب مساوات آزاد عددی سروں سے کم ہوں تو خطی الجبرا ہمیشہ ایک غیر صفر حل باقی چھوڑتا ہے۔ چنانچہ Z(n) سے کم تقاطع والی کسی ڈرائنگ کے ساتھ ایک غیر صفر کثیر رقمی ہوگی جو اس کے تمام تقاطع پر صفر ہو جاتی ہے؛ ان میں سے سب سے کم درجے والی کو لیجیے۔
مستوی مزاحمت کرتا ہے۔ جیومیٹری ایک کلاسیکی حقیقت کے ذریعے داخل ہوتی ہے: مستوی میں ایک بند حلقہ کسی دوسرے کو دائیں سے بائیں ٹھیک اتنی ہی بار کاٹتا ہے جتنی بار بائیں سے دائیں۔ اچھی طرح چنے گئے اوزان کے ساتھ اس سے کثیر رقمی کی قدروں کے مربعوں کا ایک ایسا مجموعہ حاصل ہوتا ہے، جن میں سے کچھ مثبت اور کچھ منفی شمار ہوتے ہیں، جس کا کل صفر ہے۔ مثبت حدیں سب تقاطع پر واقع ہیں، جہاں کثیر رقمی صفر ہے، اس لیے منفی حدوں کو بھی صفر ہونا پڑتا ہے۔ حلقے والی حقیقت کا دوسرا استعمال اسے ایک مقررہ جزوِ ضربی سے قابلِ تقسیم بنا دیتا ہے؛ تقسیم کرنے سے کم درجے کی ایک غیر صفر کثیر رقمی ملتی ہے جس میں یہی خاصیت ہے، جو ناممکن ہے، کیونکہ ہم نے سب سے کم درجے والی لی تھی۔

علامت (sign) والی یہ دلیل بالکو کی بنیادی تبدیلی ہے: یہ اصل دلیل کی جگہ لیتی ہے جو “ایک غیر منحط دو خطی شکل (nondegenerate bilinear form) اور عمودی تکملوں (orthogonal complements) پر مشتمل” تھی۔ وہ حلقے والی حقیقت کو بھی مختلف طریقے سے ثابت کرتے ہیں اور ہر نقطے کو زیادہ براہِ راست الگ کرتے ہیں۔

دوسرے نیٹ ورکس کا مسئلہ بھی ساتھ ہی حل

جواب Z(n) ہی رہتا ہے اگر تقاطع کے بجائے منحنیوں کے وہ جوڑے گنے جائیں جو ایک دوسرے کو کاٹتے ہی ہوں، یا جو ایک دوسرے کو طاق تعداد میں کاٹتے ہوں — بشرطیکہ ایک نقطہ شریک رکھنے والی منحنیاں کہیں اور نہ ملیں۔ پہلے کی تخفیفوں (reductions) کے ساتھ مل کر یہ مسئلۂ ثابتہ ان مکمل گرافوں کے قطعی عددِ تقاطع بھی دیتا ہے جن سے کچھ ربط ہٹا دیے گئے ہوں، مکمل گراف کی ان نقول کے جو ایک راستے کے ساتھ یا ایک جفت دور (even cycle) کے گرد زنجیر کی طرح جڑی ہوں، اور فریکٹل جیسے نیٹ ورکس کے ایک خاندان کے، جنہیں توسیع شدہ سیئرپنسکی گراف (extended Sierpiński graphs) کہا جاتا ہے۔

6 نقطوں والے مکمل گراف سے صرف ایک منحنی ہٹا دیجیے، اور اس کی کم از کم حد 3 تقاطع سے گھٹ کر 2 رہ جاتی ہے؛ 8 نقطوں پر 18 سے 15۔