নেটওয়ার্কের একটি সীমা, এখন প্রতিটি আকারের জন্য প্রমাণিত

কয়েকটি বিন্দু নিন এবং তাদের কিছু জোড়াকে রেখা দিয়ে যুক্ত করুন। গণিতবিদেরা একে বলেন গ্রাফ: বিন্দুগুলো এর শীর্ষবিন্দু (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-এর একটি মিনার

Zoltán Füredi-র বিবরণ অনুযায়ী, Erdős-এর মতে প্রশ্নটির সূত্রপাত 1960-এর দশকে Ore-এর কাজে। Ján Plesník 1975 সালে বাহুর সীমাটিকে একটি অনুমান হিসেবে উত্থাপন করেন; Murty ও Simon স্বাধীনভাবে এটি প্রস্তাব করেন এবং যোগ করেন যে সুষম সম্পূর্ণ দ্বিবিভক্ত গ্রাফই একমাত্র চরম ক্ষেত্র — তাই নাম মূর্তি–সাইমন অনুমান (Murty–Simon conjecture)। 1970 ও 1980-এর দশকে c·n² আকারের সীমাগুলো ধীরে ধীরে নেমেছে, c ক্রমশ 1/4-এর কাছে এসেছে।

1992 সালে Füredi নিয়মিততা পদ্ধতি (regularity methods) — Szemerédi-র নিয়মিততা লেমা থেকে আসা হাতিয়ার — দিয়ে যথেষ্ট বড় প্রতিটি n-এর জন্য অনুমানটি প্রমাণ করেন। মূল্য ছিল শুরুর আকার: n-কে অন্তত প্রায় 10¹⁴ উচ্চতার 2-এর একটি মিনার হতে হতো, অর্থাৎ 2-এর ঘাত 2-এর ঘাত 2…, ওপর থেকে নিচে হিসাব করা — প্রতিটি 2-কে তোলা হয় তার ওপরের সবকিছুর ঘাতে — স্তূপে প্রায় 10¹⁴টি দুই। সেই আকারের নিচে কেবল গ্রাফের কিছু বিশেষ পরিবারেরই মীমাংসা হয়েছিল।

বাহু বনাম অনুপস্থিত বাহু

স্ট্যানফোর্ড বিশ্ববিদ্যালয়ের গণিত বিভাগের Sanjana Das ও Jacob Fox-এর নতুন প্রমাণটি 3 থেকে শুরু করে প্রতিটি n-এর জন্য কাজ করে। এটি একটি সর্বাধিক মিলন (maximal matching) ব্যবহার করে: বাহুর এমন একটি সেট, যাদের কোনো দুটি একটি শীর্ষবিন্দু ভাগ করে না, এবং যাতে আর কোনো বাহু যোগ করা যায় না তাদের দুটি মিলে না গিয়ে। n শীর্ষবিন্দুর ওপর একটি মিলনে বড়জোর ⌊n/2⌋টি বাহু থাকে।

মূল লেমাটি: একটি ব্যাস-2-সংকট গ্রাফে, যে-কোনো সর্বাধিক মিলনের ক্ষেত্রে, মিলনের বাইরের বাহুগুলো কখনো অ-বাহুর চেয়ে সংখ্যায় বেশি নয় — অ-বাহু মানে যে শীর্ষবিন্দু-জোড়াগুলো যুক্ত নয়। বাকিটা পাটিগণিত। বাহুর সংখ্যার দ্বিগুণ বড়জোর জোড়ার সংখ্যা আর মিলনের আকারের যোগফলের সমান। 10টি শীর্ষবিন্দুর ক্ষেত্রে: 45টি জোড়া আর বড়জোর 5টি মিলন-বাহু মিলে 50, তাই বড়জোর 25টি বাহু। প্রতিটি n-এর জন্য সেই যোগফল ঠিক ম্যান্টেলের ছাদের দ্বিগুণ হয়।

লেমাটি নিজে একটি যত্নশীল হিসাব-নিকাশ। একটি অ-বাহু সংকট (critical), যদি একটিমাত্র দুই-ধাপের পথ তার দুই প্রান্তকে যুক্ত করে, যেমনটি চিত্র 1-এর বারোটি অ-বাহুর সবকটির ক্ষেত্রে। লেখকেরা প্রতিটি সংকট অ-বাহুকে তার পথের দুটি বাহুর সঙ্গে জুড়ে দেন এবং এভাবে তৈরি জালটিকে সংযুক্ত টুকরোয় ভাগ করেন। একটি টুকরোয় সংকট অ-বাহুর চেয়ে বড়জোর একটি বেশি বাহু থাকে, আর সেই উদ্বৃত্তওয়ালা প্রতিটি টুকরোর দাম চোকাতে হয় একটি অ-সংকট অ-বাহু দিয়ে। সেগুলো খুঁজতে লেখকেরা ব্যবহার করেন সুইচ নির্গম (switch exits): টুকরোর একটি বাহু বা সংকট অ-বাহু নিন এবং তার একটি প্রান্তকে মিলনে সেই প্রান্তের সঙ্গীর সঙ্গে বদলে দিন। প্রতিটি অ-সংকট অ-বাহুর ওপর বড়জোর দুবার দাবি ওঠে, উদ্বৃত্তওয়ালা প্রতিটি টুকরো অন্তত দুটি দাবি করে, আর হিসাব মিলে যায়।

কে কী খুঁজে পেয়েছে

“এই প্রমাণ বেশিরভাগই খুঁজে পেয়েছে এআই, নির্দিষ্টভাবে GPT-5.6 Sol, 2026 সালের 11 আগস্ট,” লেখকেরা একটি সংক্ষিপ্ত এআই-বিবৃতিতে লিখেছেন। মডেলটি ⌊n²/4⌋ সীমার একটি সম্পূর্ণ প্রমাণ খুঁজে পেয়েছিল, যা তাঁরা সরল করেছেন। জোড় সংখ্যক শীর্ষবিন্দুর ক্ষেত্রে এটি আরও প্রমাণ করেছিল যে সুষম সম্পূর্ণ দ্বিবিভক্ত গ্রাফই একমাত্র চরম ক্ষেত্র, Sumner-এর প্রমাণিত একটি তথ্যের ওপর নির্ভর করে, যা এমন গ্রাফ নিয়ে যেখানে প্রতিটি সর্বাধিক মিলন নিখুঁত (perfect), অর্থাৎ প্রতিটি শীর্ষবিন্দুকে ঢেকে দেয়।

বিজোড় সংখ্যক শীর্ষবিন্দুর ক্ষেত্রে কোনো মিলনই নিখুঁত নয়, আর বহু গ্রাফে প্রতিটি সর্বাধিক মিলন ঠিক একটি শীর্ষবিন্দু বাদ দেয়: মডেলের যুক্তি খাপ খাওয়ানো যায়নি। লেখকেরা সমতার ক্ষেত্রটির একটি ভিন্ন প্রমাণ খুঁজে পেয়েছেন, যা প্রতিটি n-এর জন্য বৈধ, এবং গবেষণাপত্রটি নিজেরাই লিখেছেন; GPT-6 Astra দিয়ে একটি চূড়ান্ত পাঠের ফলে হয়েছে “কয়েকটি ছোট সম্পাদনা”। গবেষণাপত্রটি একটি প্রিপ্রিন্ট, এখনো সহকর্মী-পর্যালোচিত নয়, এবং এতে যুক্তিটির কম্পিউটারে যাচাই করা কোনো সংস্করণের উল্লেখ নেই।

ফিরে 1907-এ

কোনো গ্রাফ ছাদ ছুঁলে, মূল অসমতাটি প্রতিটি সর্বাধিক মিলনের জন্য সমতা হয়ে যায়। চতুরভাবে মিলন বেছে নিয়ে লেখকেরা দেখান, এমন গ্রাফ হয় একটি তারা (star) — একটি শীর্ষবিন্দু বাকি সবার সঙ্গে যুক্ত, আর কিছু নয় — নয়তো তাতে কোনো সংকট অ-বাহুই নেই। একটি ব্যাস-2-সংকট গ্রাফে ত্রিভুজের প্রতিটি বাহু কোনো না কোনো সংকট পথে থাকে, তাই সংকট অ-বাহু না থাকা মানে ত্রিভুজ না থাকা; তারাতেও কোনো ত্রিভুজ নেই। তাই ছাদ ছোঁয়া গ্রাফ ত্রিভুজহীন, আর শেষ ধাপটি সেই উপপাদ্য যাকে অনুমানটি শক্তিশালী করতে চেয়েছিল: ম্যান্টেলের 1907 সালের ফল, যা সুষম সম্পূর্ণ দ্বিবিভক্ত গ্রাফকে ছাদে একা রেখে দেয়।