১৯৬০-এর দশকের এক গ্রাফ-ধাঁধার অবশেষে সমাধান

কয়েকটি বিন্দু নিন এবং তাদের কিছু জোড়াকে রেখা দিয়ে যুক্ত করুন: গণিতবিদেরা একে বলেন গ্রাফ, বিন্দুগুলোকে এর শীর্ষ (ভার্টেক্স) আর রেখাগুলোকে এর প্রান্ত (এজ)। চক্র (সাইকেল) হলো একটি বন্ধ লুপ, যা ভিন্ন ভিন্ন শীর্ষ ঘুরে তার শুরুর বিন্দুতে ফিরে আসে। একটি স্বাভাবিক প্রশ্ন হলো, একটি গ্রাফের প্রান্তগুলোকে — প্রতিটি প্রান্ত ঠিক একবার ব্যবহার করে — চক্রে ভাগ করা যায় কি না।

গবেষণাপত্রটি যেমন মনে করিয়ে দেয়, উত্তরটি বহুদিন ধরে জানা: এটি সম্ভব ঠিক তখনই, যখন প্রতিটি শীর্ষ জোড় সংখ্যক প্রান্ত স্পর্শ করে। এমন গ্রাফকে বলা হয় অয়লারীয় (Eulerian)। পরের প্রশ্ন হলো কতগুলো চক্র দরকার। আর যেসব গ্রাফে শুধু চক্র দিয়ে কাজ চলে না, সেখানে একক প্রান্তকেও টুকরো হিসেবে গ্রহণ করা হয়।

অনুমানটি

১৯৬০-এর দশকে এর্ডশ (Erdős) ও গালাই (Gallai) অনুমান করেন যে n শীর্ষের প্রতিটি গ্রাফের প্রান্তগুলোকে এমন সংখ্যক চক্র ও একক প্রান্তে ভাগ করা যায়, যা সর্বোচ্চ n-এর সমানুপাতিক — লেখা হয় O(n)। এর্ডশ এটিকে তাঁর অমীমাংসিত সমস্যার কয়েকটি সংকলনে অন্তর্ভুক্ত করেছিলেন। হাইওশ (Hajós)-এর একটি সম্পর্কিত অনুমান প্রতিটি অয়লারীয় গ্রাফে সর্বোচ্চ (n − 1)/2টি চক্র চায়।

রৈখিক হলো সবচেয়ে ভালো যা আশা করা যায়: এর্ডশ দেখিয়েছিলেন যে কিছু গ্রাফের প্রায় ১.৫ n টুকরো লাগে। প্রশ্ন ছিল, কোনো একটি ধ্রুবক গুণ n সবসময় যথেষ্ট কি না।

পঞ্চাশ বছরের ধীরগতির সীমা

এর্ডশ ও গালাই নিজেরাই একটি সহজ পদ্ধতি লক্ষ করেছিলেন: বারবার সবচেয়ে লম্বা চক্রটি সরানো। এতে প্রায় n log n টুকরো পাওয়া যায় — এবং গবেষণাপত্র অনুযায়ী, প্রায় পঞ্চাশ বছর ধরে এটিই ছিল সবচেয়ে ভালো সাধারণ সীমা। সম্প্রতি Conlon, Fox ও Sudakov একে নামিয়ে আনেন n log log n-এ, তারপর Bucić ও Montgomery n log* n-এ, যেখানে log* n — অর্থাৎ একের নিচে নামতে কতবার লগারিদম নিতে হয় — অকল্পনীয় ধীরগতিতে বাড়ে। এই পদ্ধতিগুলো ধাপে ধাপে কাজ করত, আর প্রতিটি ধাপে প্রায় n চক্র খরচ হতো, তাই ধাপের সংখ্যা সবসময় চূড়ান্ত গণনায় ঢুকে পড়ত। দৈব (র‍্যান্ডম) গ্রাফের মতো কিছু বিশেষ গ্রাফ-পরিবারের জন্য অনুমানটি আগেই প্রমাণিত হয়েছিল।

লুপের দাম মেটায় যে ওজন

দক্ষিণ কোরিয়ার KAIST-এর Jaehoon Kim এখন অনুমানটি প্রমাণ করেছেন: একটি নির্দিষ্ট ধ্রুবক C আছে, যার জন্য n শীর্ষের প্রতিটি গ্রাফ সর্বোচ্চ Cn চক্র ও প্রান্তে ভাগ হয়। এর অনুসিদ্ধান্ত হিসেবে, হাইওশের অনুমান একটি ধ্রুব গুণক পর্যন্ত সত্য।

প্রমাণটি ধাপের পদ্ধতি ছেড়ে দেয়। একটিমাত্র প্রক্রিয়া একটি একটি করে চক্র ও প্রান্ত সরায়, আর মোট সংখ্যা নিয়ন্ত্রিত হয় দুটি রাশি দিয়ে, যাদের প্রতিটি একটি ধ্রুবক গুণ n-এর নিচে থাকে।

• মাত্রাভিত্তিক একটি বিভব। প্রতিটি শীর্ষ একটি ওজন পায়, যা তার প্রান্তের সংখ্যার সঙ্গে কমে, মোটামুটি ১ / (মাত্রা × log² মাত্রা)। একটি চক্র ভারী যদি তার শীর্ষগুলোর ওজনের যোগফল অন্তত ১ হয়। একটি ভারী চক্র সরালে একটি সামগ্রিক “বিভব” (পোটেনশিয়াল) অন্তত ১ কমে, আর সেই বিভব শুরুতে একটি ধ্রুবক গুণ n-এর বেশি নয়। তাই ভারী চক্র কেবল O(n) বারই সরানো যায়।
• শীর্ষের সংখ্যা। যখন আর কোনো ভারী চক্র থাকে না, গ্রাফটি তখন “হালকা” — আর প্রধান নতুন উপপাদ্যটি দেখায় যে বড় মাত্রার একটি হালকা গ্রাফে অবশ্যই একটি ঘন, প্রায় বদ্ধ অঞ্চল থাকে। সেই অঞ্চলকে তার আকারের সমানুপাতিক সংখ্যক চক্র ও প্রান্তে ভাগ করা হয়, তারপর তার শীর্ষগুলোর অন্তত পঞ্চাশ ভাগের এক ভাগের হাতে থাকে সর্বোচ্চ দুটি প্রান্ত এবং সেগুলো চিরতরে বাদ পড়ে। যেহেতু প্রতিটি শীর্ষ কেবল একবারই বাদ পড়তে পারে, এই অংশের খরচও O(n)।

গ্রাফের ঘন অংশের ভেতরে, পথের টুকরোগুলোকে “এক্সপ্যান্ডারের” মধ্য দিয়ে যাওয়া সংযোগকারী পথ দিয়ে একটিমাত্র চক্রে বন্ধ করা হয়; একটি দৈব রঙ করা একই চক্রের সংযোগকারী পথগুলোকে আলাদা রাখে। — চিত্র ৩, Kim (2026), arXiv:2610.07840.

ওই ঘন অঞ্চলগুলো ভাগ করতে প্রমাণটি Bucić ও Montgomery-র মজবুত “এক্সপ্যান্ডার” (expanders) — এমন গ্রাফ যেখানে শীর্ষের প্রতিটি সেটের অনেক প্রতিবেশী থাকে — সংক্রান্ত সরঞ্জাম প্রসারিত করে, এবং শীর্ষগুলোকে দৈবভাবে রঙ করে যাতে একই চক্রের সংযোগকারী পথগুলো কখনও সংঘর্ষে না জড়ায়।

যা এখনও উন্মুক্ত

ধ্রুবক C বিশাল, আর লেখক একে সর্বোত্তম করার চেষ্টা করেননি। সবচেয়ে ভালো ধ্রুবক — যা অন্তত ১.৫ — খুঁজে বের করা এখনও উন্মুক্ত প্রশ্ন, যেমন উন্মুক্ত হাইওশের সঠিক অনুমান এবং গ্রাফকে পথে ভাগ করা নিয়ে গালাইয়ের একটি সম্পর্কিত অনুমান। ওজনের কৌশলটির জন্য কেবল এমন ওজন দরকার যাদের যোগফল অভিসারী, এবং লেখকের মতে এটি অন্যান্য বিভাজন-সমস্যাতেও কাজে লাগতে পারে।

এটি একজন লেখকের একটি প্রিপ্রিন্ট, যা এখনও সমকক্ষ-পর্যালোচনায় যাচাই হয়নি।

স্বার্থের সংঘাত। লেখক জানিয়েছেন যে যুক্তি তৈরিতে এবং লেখা ও চিত্র প্রস্তুতে তিনি ব্যাপকভাবে ChatGPT (OpenAI) ও Claude (Anthropic) ব্যবহার করেছেন, এবং তিনি সব ফলাফল যাচাই করেছেন ও গবেষণাপত্রের পূর্ণ দায়িত্ব নিচ্ছেন। আপনি যে লেখাটি পড়ছেন, সেটিও Claude-এরই লেখা।