গণিতপ্রিপ্রিন্টতত্ত্বপড়তে ৩ মিনিট

একটি নির্দিষ্ট ঘনত্বে পৌঁছে এলোমেলো নেটওয়ার্ক আর রং করা যায় না

একটি গ্রাফ নিন — সংযোগ দিয়ে জোড়া বিন্দুর সমষ্টি — আর রঙের একটি বাক্স। q রং দিয়ে একটি যথাযথ রঙবিন্যাস (proper colouring) প্রতিটি বিন্দুকে q রঙের একটি দেয়, এমনভাবে যে দুটি যুক্ত বিন্দু কখনো একই রং পায় না। সংযোগ কম থাকলে কাজটি সহজ। অনেক থাকলে তা অসম্ভব হয়ে যায়।

এবার গ্রাফটি গড়ুন এলোমেলোভাবে: n-টি বিন্দু, যাদের প্রতিটি জোড়া স্বাধীনভাবে একটি ছোট সম্ভাবনায় যুক্ত, যাতে একটি বিন্দুর গড়ে d-টি প্রতিবেশী থাকে। d বাড়ার সঙ্গে সঙ্গে এলোমেলো গ্রাফটি “q রঙে প্রায় নিশ্চিতভাবে (almost surely) রং করা যায়” অবস্থা থেকে চলে যায় “প্রায় নিশ্চিতভাবে যায় না” অবস্থায়। বদলটি ঠিক কোথায় ঘটে? তিন থেকে শুরু করে যেকোনো নির্দিষ্ট রঙ-সংখ্যা q-এর জন্য এই প্রশ্নটিই University of Cambridge-এর Gaia Carenini-র একটি নতুন গবেষণাপত্রের বিষয়।

যে বদল টলমল করতে পারত

গ্রন্থপঞ্জিতে তালিকাভুক্ত 1999 সালের একটি গবেষণাপত্রে Achlioptas আর Friedgut প্রমাণ করেছিলেন যে রূপান্তরটি তীক্ষ্ণ (sharp): প্রতিটি আকার n-এর জন্য একটি সংকট গড় মাত্রা (critical average degree) d_q(n) আছে, যার সামান্য নিচে গ্রাফটি প্রায় নিশ্চিতভাবে রং করা যায়, আর সামান্য ওপরে প্রায় নিশ্চিতভাবে যায় না। যে জানালার (window) মধ্যে বদলটি ঘটে, তা সংকুচিত হয়ে শূন্যে মিলিয়ে যায়।

কিন্তু এতে একটি ফাঁক রয়ে গিয়েছিল। গ্রাফ বড় হওয়ার সঙ্গে সঙ্গে সংকট মানটি নিজেই দুলতে থাকবে না, এমন কোনো নিশ্চয়তা ছিল না — এক আকারের গ্রাফে এক জায়গায়, আরও বড়গুলোর বেলায় সামান্য অন্য জায়গায়, কখনো থিতু না হয়ে। Achlioptas–Friedgut অভিসৃতি অনুমান (convergence conjecture) বলে যে এমনটা ঘটে না: প্রতিটি q-এর জন্য একটিই ধ্রুবক d_q আছে, যার নিচে এলোমেলো গ্রাফ রং করা যায় আর ওপরে যায় না।

পদার্থবিদেরা কী পূর্বাভাস দিয়েছিলেন

পরিসংখ্যানগত পদার্থবিদ্যার কাছে কী ঘটে, তার একটি ছবি ছিল। সংযোগ যোগ হতে থাকলে বৈধ রঙবিন্যাসগুলো গুচ্ছে (clusters) জোট বাঁধে: একটি গুচ্ছের ভেতরের রঙবিন্যাসগুলো পরস্পরের মতো, আর দুটি গুচ্ছ অনেক বিন্দুতে আলাদা। তারপর, ঘনীভবন (condensation) নামের এক পর্যায়ে, মুষ্টিমেয় কয়েকটি বড় গুচ্ছ সব রঙবিন্যাসের একটি উল্লেখযোগ্য অংশ ধরে রাখে — আর কেবল তার পরেই রঙবিন্যাসের সেটটি শূন্য হয়ে যায়। এই বিন্যাসই ব্যাখ্যা করে, সীমার কাছে গণনাভিত্তিক যুক্তিগুলো কেন হিমশিম খায়।

বেশি রঙের ক্ষেত্রে আগের কাজ সীমাটিকে ইতিমধ্যে একটি সরু পরিসরে আটকে ফেলেছিল: এটি থাকে মোটামুটি 2q log q − log q − 2 log 2 আর 2q log q − log q − 1-এর মধ্যে, যে ফাঁকের প্রস্থ q বাড়লে 2 log 2 − 1। কিন্তু “সরু” মানেই “নির্দিষ্ট” নয়, আর তিনের মতো কম রঙের ক্ষেত্রে প্রশ্নটি খোলাই থেকে গিয়েছিল।

একটি যমজ সমস্যা, যার মোকাবিলা আগে

রং করার একটি যমজ আছে: সন্তোষযোগ্যতা (satisfiability), অর্থাৎ চলকগুলোর জন্য সত্য বা মিথ্যা মান বেছে নেওয়ার সমস্যা, যাতে এলোমেলো যৌক্তিক শর্তের একটি তালিকার সবগুলোই খাটে। সেখানেও একটি তীক্ষ্ণ সীমার অস্তিত্ব জানা ছিল, কিন্তু তা যে থিতু হয়, তার প্রমাণ ছিল না। গবেষণাপত্রে উদ্ধৃত 2026 সালের একটি প্রতিবেদনে Carenini ঘোষণা করেছিলেন যে তা থিতু হয়, তিন থেকে শুরু করে প্রতিটি শর্ত-দৈর্ঘ্যের (constraint length) জন্য, রূপান্তরের জানালাটি যে খুব সরু তা দেখিয়ে। নতুন গবেষণাপত্রটি সেই যুক্তিকেই রং করার ক্ষেত্রে খাপ খাইয়ে নেয়।

একসঙ্গে জমে থাকা জোড়া

প্রমাণটি এগোয় পরপর কয়েকটি লঘুকরণের (reductions) একটি শিকল ধরে। একটি একটি করে এলোমেলো সংযোগ যোগ করার সময় ধরা যাক H সেই মুহূর্ত, যখন গ্রাফটি আর রং করা যায় না। যদি H এক এলোমেলো গ্রাফ থেকে আরেকটিতে সামান্যই বদলায় — প্রায় n/(log n)²-টি সংযোগের একটি জানালার মধ্যে — তাহলে সীমাটিকে থিতু হতেই হবে। একটি ধ্রুপদি অসমতা এটিকে পরিণত করে শেষ রং-করা-যায় এমন গ্রাফটি সম্পর্কে একটি প্রশ্নে: গড়ে কতগুলো নতুন এলোমেলো সংযোগ সয়েও এটি টিকে থাকে?

এখানেই আসে মূল ধারণাটি: জমে যাওয়া জোড়া (frozen pairs)। দুটি বিন্দু একটি জমে যাওয়া জোড়া গঠন করে, যখন প্রতিটি বৈধ রঙবিন্যাস তাদের একই রং দেয়। একটি নতুন সংযোগ ঠিক তখনই প্রাণঘাতী, যখন তা এমন একটি জোড়াকে যুক্ত করে। একক বিন্দুকে কোনো একটি নির্দিষ্ট রঙে জমিয়ে রাখা যায় না, কারণ রংগুলো অদলবদল করলে সবসময় আরেকটি বৈধ রঙবিন্যাস পাওয়া যায়; যা বাধ্যতামূলক হয়ে পড়ে, তা দুটি বিন্দুর মধ্যকার একটি সম্পর্ক। সংযোগ যোগ হওয়ার সঙ্গে সঙ্গে এই জমে যাওয়া শ্রেণিগুলো কীভাবে বাড়ে, Carenini তা অনুসরণ করেন একটি সংযোগ বা একটি গোটা বিন্দু মুছে দিয়ে আর আবার ফিরে আসা বিকল্পগুলো দেখে। হিসাবগুলো (estimates) দেখায় যে শেষ রং-করা-যায় এমন গ্রাফটি বেশিক্ষণ টিকতে পারে না, আর তাতে জানালাটি এতটাই সরু হয় যে অনুমানটি প্রমাণ হয়ে যায়।

যা এখনো অজানা

উপপাদ্যটি বলে যে প্রতিটি q ≥ 3-এর জন্য সীমা d_q আছে। এটি বলে না সেটি কোথায়: গবেষণাপত্রটি এর কোনো মান দেয় না, এমনকি তিন রঙের জন্যও নয়। গবেষণাপত্রটি একক লেখকের একটি প্রিপ্রিন্ট, আর এখনো সমকক্ষ পর্যালোচনার মধ্য দিয়ে যায়নি। এটি শেষ হয় একটি সংক্ষিপ্ত বিবৃতি দিয়ে: এর কোনো গাণিতিক যুক্তিই কোনো বৃহৎ ভাষা মডেল তৈরি করেনি।