প্রতিটি বিন্দুকে বাকি সবগুলোর সঙ্গে জুড়ুন: সবচেয়ে কম ছেদ, এবার প্রমাণিত

এক তা কাগজে পাঁচটি বিন্দু বসান এবং প্রতিটি জোড়াকে একটি বক্ররেখা দিয়ে যুক্ত করুন: মোট দশটি বক্ররেখা। এগুলো যেমন খুশি বাঁকতে পারে, কিন্তু কোনোটিই তৃতীয় কোনো বিন্দুর ভেতর দিয়ে যেতে পারবে না। প্রতিটি ছেদ এড়ানোর চেষ্টা করুন, আপনি ব্যর্থ হবেন। পাঁচটি বিন্দুতে অন্তত 1টি ছেদ অনিবার্য; ছয়টিতে অন্তত 3টি; দশটিতে অন্তত 60টি।

গণিতবিদেরা এমন ছবিকে বলেন সম্পূর্ণ গ্রাফ (complete graph) Kₙ-এর একটি অঙ্কন — n টি বিন্দু, যার প্রতিটি জোড়া যুক্ত — আর যেকোনো অঙ্কন সর্বনিম্ন যতগুলো ছেদে পৌঁছাতে পারে, সেটিকে বলেন এর ছেদ-সংখ্যা (crossing number)। চেক প্রজাতন্ত্রের চার্লস বিশ্ববিদ্যালয়ের মার্টিন বালকো প্রশ্নটিকে বলেন “টপোলজিক্যাল গ্রাফ তত্ত্বের সবচেয়ে বিখ্যাত সমস্যাগুলোর একটি”।

একজন শিল্পীর গণনা

1950-এর দশকের শেষ দিকে ব্রিটিশ শিল্পী অ্যান্টনি হিল (Anthony Hill) Kₙ-এর এমন অঙ্কন তৈরি করেছিলেন, যাদের ছেদের সংখ্যা ঠিক

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

এখানে ⌊ ⌋ মানে নিচের দিকে পূর্ণসংখ্যায় নামানো। কোনো অঙ্কন এর চেয়ে ভালো করতে পারে না — এই অনুমান প্রথম প্রকাশ করেন গাই (Guy), পরে এ নিয়ে আলোচনা করেন হ্যারারি (Harary) ও হিল, আর একে জনপ্রিয় করে তোলেন এর্দোশ (Erdős) ও গাই। এটি হ্যারারি–হিল অনুমান (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” হিসেবে তালিকাভুক্ত করে এবং উপপাদ্যটির কৃতিত্ব দেয়। সেই প্রমাণ কীভাবে পাওয়া গেছে, গবেষণাপত্রটি তা বলে না। বালকোর ভাষায়, মূল প্রমাণটি “তুলনামূলক ছোট”, কিন্তু “অনুসরণ করা বেশ কঠিন”। তাঁর প্রিপ্রিন্ট একটি সুবিন্যস্ত রূপ উপস্থাপন করে, যার জন্য, তিনি লেখেন, “কেবল রৈখিক বীজগণিত ও গ্রাফ তত্ত্বের প্রাথমিক জ্ঞান প্রয়োজন”। আরেকজন গণিতবিদ, গেলাসিও সালাজার (Gelasio Salazar), একটি আলাদা, বিস্তারিত ব্যাখ্যা প্রস্তুত করছেন।

ছেদের বদলে সহগ গোনা

যেহেতু জানা অঙ্কনগুলো ইতিমধ্যেই Z(n)-এ পৌঁছায়, কেবল নিম্নসীমাটিই প্রমাণ করা দরকার। এর জন্য চারটি ধাপ লাগে।

বিজোড় সংখ্যাই যথেষ্ট। একটি সেরা অঙ্কনকে এমনভাবে নতুন করে আঁকা যায় যাতে একটি বিন্দু ভাগ করে নেওয়া বক্ররেখাগুলো কখনো একে অপরকে ছেদ না করে; তখন প্রতিটি ছেদে 4টি ভিন্ন বিন্দু জড়িত থাকে। 6টি বিন্দুর প্রতিটিকে পালা করে মুছে ফেলুন: বাকি থাকা প্রতিটি 5-বিন্দুর ছবিতে অন্তত 1টি ছেদ থাকে, আর প্রতিটি ছেদ 6টি মোছার মধ্যে ঠিক 2টিতে টিকে থাকে (এর নিজের 4টি বিন্দুর যেকোনো একটি মুছলেই এটি মিলিয়ে যায়, আর বাকি 2টিতে টিকে থাকে)। তাই ছেদের সংখ্যার দ্বিগুণ অন্তত 6: অর্থাৎ অন্তত 3, যা Z(6)। একই গণনা প্রতিটি জোড় সংখ্যার জন্য খাটে।
বহুপদীর একটি পরিবার। প্রতিটি বিন্দুকে তার নিজস্ব একটি সংখ্যা দিন। একটি ছেদে দুটি বক্ররেখা জড়িত, তাই চারটি বিন্দু, তাই চারটি সংখ্যা। বালকো চার চলকের বহুপদী ব্যবহার করেন, এমনভাবে বাছাই করা যে n বিজোড় হলে পরিবারটিতে ঠিক Z(n)-টি স্বাধীন সহগ থাকে — 7টি বিন্দুর জন্য 3 × 3 = 9।
খুব কম ছেদ জায়গা ছেড়ে দেয়। একটি ছেদে একটি বহুপদীকে শূন্য হতে বলা মানে একটি সমীকরণ। মুক্ত সহগের চেয়ে কম সমীকরণ থাকলে রৈখিক বীজগণিত সবসময় একটি অশূন্য সমাধান রেখে দেয়। তাই Z(n)-এর চেয়ে কম ছেদসহ একটি অঙ্কনের সঙ্গে থাকবে এমন একটি অশূন্য বহুপদী, যা তার সব ছেদে শূন্য হয়; এদের মধ্যে সর্বনিম্ন ঘাতেরটি নিন।
সমতল পাল্টা বাধা দেয়। জ্যামিতি প্রবেশ করে একটি ধ্রুপদি তথ্যের মাধ্যমে: সমতলে একটি বদ্ধ লুপ অন্য একটিকে ডান থেকে বাঁয়ে ঠিক ততবার ছেদ করে, যতবার বাঁ থেকে ডানে। ভালোভাবে বাছাই করা ভার (weights) দিয়ে এ থেকে পাওয়া যায় বহুপদীটির মানগুলোর বর্গের একটি যোগফল, যার কিছু পদ ধনাত্মকভাবে আর কিছু ঋণাত্মকভাবে গোনা হয়, আর মোট হয় শূন্য। ধনাত্মক পদগুলো সবই ছেদগুলোতে অবস্থিত, যেখানে বহুপদীটি শূন্য, তাই ঋণাত্মক পদগুলোকেও শূন্য হতে হবে। লুপ-তথ্যটির দ্বিতীয় একটি প্রয়োগ একে একটি নির্দিষ্ট উৎপাদক দিয়ে বিভাজ্য করে; ভাগ করলে একই বৈশিষ্ট্যের একটি নিম্নতর ঘাতের অশূন্য বহুপদী পাওয়া যায়, যা অসম্ভব, কারণ আমরা সর্বনিম্নটিই নিয়েছিলাম।

সেই চিহ্ন-যুক্তিই বালকোর প্রধান পরিবর্তন: এটি মূল যুক্তিটির জায়গা নেয়, যাতে ছিল “একটি অ-অপজাত দ্বিরৈখিক রূপ ও লম্ব পরিপূরক” (involving a nondegenerate bilinear form and orthogonal complements)। তিনি লুপ-তথ্যটিও ভিন্নভাবে প্রমাণ করেন এবং প্রতিটি বিন্দুকে আরও সরাসরি আলাদা করেন।

একসঙ্গে মীমাংসিত অন্যান্য নেটওয়ার্ক

ছেদের বদলে যদি গোনা হয় বক্ররেখার সেই জোড়াগুলো, যারা আদৌ ছেদ করে, বা বিজোড় সংখ্যকবার ছেদ করে, তবুও উত্তর থাকে Z(n) — যতক্ষণ একটি বিন্দু ভাগ করে নেওয়া বক্ররেখাগুলো অন্য কোথাও মিলিত না হয়। আগের রূপান্তরগুলোর (reductions) সঙ্গে মিলিয়ে, উপপাদ্যটি নির্ভুল ছেদ-সংখ্যাও দেয় কিছু সংযোগ সরিয়ে ফেলা সম্পূর্ণ গ্রাফের জন্য, একটি পথ বরাবর বা একটি জোড় চক্রের চারপাশে শিকলের মতো জোড়া সম্পূর্ণ গ্রাফের প্রতিলিপির জন্য, এবং বর্ধিত সিয়েরপিনস্কি গ্রাফ (extended Sierpiński graphs) নামে ফ্র্যাক্টাল-সদৃশ নেটওয়ার্কের একটি পরিবারের জন্য।

6টি বিন্দুর সম্পূর্ণ গ্রাফ থেকে একটিমাত্র বক্ররেখা সরিয়ে নিন, এর ন্যূনতম মান 3টি ছেদ থেকে নেমে আসে 2-এ; 8টি বিন্দুতে 18 থেকে 15-এ।