গ্রাফ তত্ত্বে একটি খুব বড় ছোট লিপ ফরোয়ার্ড

15 মার্চ, কৌতূহলী সেমিনার ঘোষণাগুলি গণনার গাণিতিক অধ্যয়ন, কম্বিনেটিক্সের ক্ষেত্রে গন্ডগোল পাঠায়। তিন সহযোগী পরের দিন সমন্বিত বক্তৃতা দেওয়ার পরিকল্পনা করেছিলেন। জুলিয়ান সহস্রবুধে ইংল্যান্ডের কেমব্রিজে গণিতবিদদের সম্বোধন করবেন সাইমন গ্রিফিথস রিও ডি জেনিরোতে খবর শেয়ার করবেন এবং মার্সেলো ক্যাম্পোস সাও পাওলোতে। তিনটি বক্তৃতায় অভিন্ন শিরোনাম এবং রহস্যময়, দুই-বাক্যের বিমূর্ত উল্লেখ করা হয়েছে "এর্দসের একটি পুরানো সমস্যার সাম্প্রতিক অগ্রগতি"। পল এরডস, একজন হাঙ্গেরিয়ান গণিতবিদ যিনি 1996 সালে মারা গিয়েছিলেন, পোজ দিয়েছেন শত শত সমস্যা তার কর্মজীবনের সময়, সংযোজকরা দ্রুত নির্দিষ্ট সমস্যাটি ভাগ করে দিয়েছিলেন যে ত্রয়ী সম্পর্কে কথা বলার পরিকল্পনা ছিল। রামসে নম্বর নামক কিছু নিয়ে গুজব ছড়িয়ে পড়ে, যা গণিতে গণনা করা সবচেয়ে কঠিন পরিমাণগুলির মধ্যে একটি।

রামসে সংখ্যাগুলি রামসে তত্ত্ব নামে একটি সম্পূর্ণ শৃঙ্খলা তৈরি করেছে, যা বিশাল পরিসরে সিস্টেমের মধ্যে অনিবার্য প্যাটার্নের সন্ধান করে।

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

র‌্যামসে সংখ্যাটি পরিমাপ করে যে নির্দিষ্ট নিদর্শন অনিবার্যভাবে উদ্ভূত হওয়ার আগে একটি দৃষ্টান্তমূলক উদাহরণ কত বড় হতে হবে। কিন্তু এর কেন্দ্রীয়তা থাকা সত্ত্বেও, র‍্যামসে সংখ্যাটি ছাড়া কেউই গণনা করতে পারেনি সহজ উদাহরণ. তারা যা করতে সক্ষম হয়েছে তা হল এটি কী হতে পারে তার সীমা (বা সীমানা) খুঁজে বের করা। তারপরেও, প্রায় এক শতাব্দী আগে এরডস এবং একজন সহযোগীর দ্বারা প্রথম স্থাপিত উপরের সীমাটি খুব কমই ঠেকেছিল।

তারপর, 15 মার্চের সেমিনারে, এবং সেই সন্ধ্যার পরে পোস্ট করা একটি গবেষণাপত্রে, গবেষকরা ঘোষণা করেছিলেন যে তারা সূচকীয় পরিমাণে রামসে নম্বরের উপরের সীমাকে উন্নত করেছেন।

"আমি মেঝে ছিল," বলেন ইউভাল উইগডারসন, তেল আবিব বিশ্ববিদ্যালয়ের একজন গণিতবিদ, নতুন ফলাফল সম্পর্কে শুনে। "আমি আক্ষরিক অর্থে আধা ঘন্টা থেকে এক ঘন্টা পর্যন্ত কাঁপছিলাম।"

পার্টি লাইন

Ramsey তত্ত্ব সাধারণত পূর্ণসংখ্যা বা গ্রাফ সম্পর্কে প্রশ্ন জিজ্ঞাসা করে। একটি গ্রাফ, এই প্রসঙ্গে, নোড নামক বিন্দুর সংগ্রহকে বোঝায়, প্রান্ত নামক রেখা দ্বারা সংযুক্ত, যার দৈর্ঘ্যের মতো বৈশিষ্ট্য থাকতে পারে বা — রামসে সংখ্যার ক্ষেত্রে — রঙের মতো।

একটি সম্পূর্ণ গ্রাফ উভয়ই জটিল এবং সহজ - প্রতিটি নোড প্রতিটি অন্য নোডের সাথে সংযুক্ত থাকে। Ramsey সংখ্যা বর্ণনা করে যে একটি সম্পূর্ণ গ্রাফে কতটি নোড থাকতে হবে যাতে একটি নির্দিষ্ট কাঠামো থাকতে বাধ্য হয়। বলুন একটি সম্পূর্ণ গ্রাফের প্রান্ত দুটি রঙের একটি বরাদ্দ করা হয়েছে: লাল বা নীল। এবং বলুন আপনি প্রান্তগুলিকে এমনভাবে রঙ করার চেষ্টা করুন যা একই রঙের প্রান্তগুলির সাথে নোডগুলির একটি গ্রুপকে সংযুক্ত করা এড়িয়ে যায়। 1930 সালে, ফ্রাঙ্ক রামসে প্রমাণ করেছিলেন যে যদি একটি গ্রাফ যথেষ্ট বড় হয়, তাহলে গণিতবিদরা যাকে একরঙা চক্র বলে থাকেন তা তৈরি করা এড়ানো অসম্ভব হয়ে পড়ে - নোডগুলির একটি গ্রুপ যার সাধারণ প্রান্তগুলি হয় সমস্ত লাল বা সমস্ত নীল।

একটি একরঙা চক্রের উত্থান হতে বাধ্য হওয়ার আগে একটি গ্রাফ কতটা বড় হতে হবে? উত্তর নির্ভর করে চক্রের আকারের উপর। রামসে দেখিয়েছিলেন যে একটি সংখ্যা বিদ্যমান, যাকে এখন রামসে নম্বর বলা হয়, নোডের ন্যূনতম সংখ্যার প্রতিনিধিত্ব করে যার জন্য প্রদত্ত আকারের একটি একরঙা চক্র বিদ্যমান থাকা আবশ্যক, প্রান্তগুলি যেভাবেই রঙিন হোক না কেন।

কিন্তু Ramsey সংখ্যার আকার পিন ডাউন কঠিন. 1935 সালে, রামসে এর অস্তিত্ব দেখানোর পাঁচ বছর পর, এরডস এবং জর্জ সেকেরেস একটি প্রদত্ত আকারের একটি চক্রের জন্য রামসে সংখ্যাটি কত বড় তা নিয়ে একটি নতুন, শক্ত উপরের সীমানা প্রদান করেছিলেন। কিন্তু তারপর থেকে, গণিতবিদরা সবেমাত্র Erdős এবং Szekeres এর গণনায় উন্নতি করতে সক্ষম হয়েছেন।

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

"একটি গ্রাফে আপনার যে সহজ জিনিসটি থাকতে পারে তা হল একটি একরঙা চক্র," বলেছেন৷ মারিয়া চুদনভস্কি, প্রিন্সটন বিশ্ববিদ্যালয়ের একজন গণিতবিদ। “এটি আশ্চর্যজনক যে প্রতিটি বিশাল গ্রাফে আপনি তাদের মধ্যে একটি বড় খুঁজে পেতে পারেন। এটা পুরোপুরি পরিষ্কার নয়।”

প্রথম কয়েকটি রামসে সংখ্যা গণনা করা তুলনামূলকভাবে সহজ। ধরা যাক আপনি ক্ষুদ্রতম গ্রাফের আকার জানতে চান যা অনিবার্যভাবে গণিতবিদদের কাছে আকার দুই বা R(2) এর একটি চক্র ধরে রাখতে হবে। যেহেতু দুটি নোড সহ একটি সম্পূর্ণ গ্রাফ একটি প্রান্ত দ্বারা সংযুক্ত দুটি নোড, এবং সেই প্রান্তটি হয় লাল বা নীল হতে হবে, R(2) হল 2৷ আরও সাধারণভাবে, R(k), অথবা এর রামসে নম্বর k, হল নোডের সর্বনিম্ন সংখ্যা যার বাইরে একটি গ্রাফ আকারের একটি চক্রকে এড়াতে পারে না k.

এটি দেখানো এত কঠিন নয় যে আকার 3, বা R(3) এর একটি চক্রের রামসে সংখ্যা 6 (গ্রাফিক দেখুন)। কিন্তু 1955 সাল পর্যন্ত R(4) 18 এ পিন করা হয়নি। R(5) অজানা রয়ে গেছে - এটি কমপক্ষে 43 এবং 48 এর চেয়ে বড় নয়। যদিও এই সংখ্যাগুলি ছোট, সম্ভাব্য সমস্ত রঙের মধ্যে দিয়ে বের করে দেওয়া হয়েছে ক্যালিফোর্নিয়া ইনস্টিটিউট অফ টেকনোলজির ডেভিড কনলন বলেছেন। 43টি নোড সহ একটি সম্পূর্ণ গ্রাফে রঙের সংখ্যা বিবেচনা করুন। "আপনার 903 প্রান্ত আছে; তাদের প্রতিটি দুটি উপায়ে রঙ করা যেতে পারে,” তিনি ব্যাখ্যা করেছেন। "তাহলে আপনি 2 পাবেন⁹⁰³, যা জ্যোতির্বিদ্যাগতভাবে বড়।"

চক্রের আকার বাড়ার সাথে সাথে, রামসে নম্বরটি পেরেক ঠেকানোর কাজটি আরও কঠিন হয়ে যায়। এরদস বলেছিলেন যে গাণিতিকভাবে দাবি করা এলিয়েনদের সাথে সর্বাত্মক যুদ্ধ চেষ্টা করার চেয়ে সহজ হবে R(6) বের করুন, যা 102 এবং 165 এর মধ্যে কোথাও। অনিশ্চয়তার পরিসর দ্রুত বৃদ্ধি পায়: অনুযায়ী Stanisław Radziszowski দ্বারা সংকলিত অনুমান, R(10) 798 এর মত ছোট এবং 23,556 এর মত বড় হতে পারে। কিন্তু গণিতবিদদের লক্ষ্য র‍্যামসে সংখ্যা 10 ছাড়িয়ে গেছে। তারা এমন একটি সূত্র চায় যা R(এর একটি ভাল অনুমান দেবে।k), এমনকি — বা বিশেষ করে — যখন k অত্যন্ত বড়।

উইগডারসন বলেন, “আমি কম্বিনেটরিক্সে এমন একজন ব্যক্তিকে চিনি না যিনি এই সমস্যাটি নিয়ে অন্তত একটু চিন্তা করেননি। "এই সমস্যাটি, আমি মনে করি, সত্যিই বিশেষ।"

আদালতে আদেশ

ফ্র্যাঙ্ক রামসে একজন সারগ্রাহী, উজ্জ্বল ব্যক্তিত্ব ছিলেন যিনি 26 বছর বয়সে মারা গিয়েছিলেন। তিনি মারা যাওয়ার কয়েক সপ্তাহ আগে, দ লন্ডন ম্যাথমেটিকাল সোসাইটির কার্যপ্রণালী প্রকাশিত কাগজটি যেটিতে তিনি রামসে নম্বর প্রবর্তন করেছিলেন। সেই কাজটি এমনকি গ্রাফ সম্পর্কেও ছিল না, কিন্তু গাণিতিক যুক্তিতে একটি সমস্যা সম্পর্কে। রামসে প্রমাণ করেছেন যে একটি বিবৃতি যা কিছু শর্ত পূরণ করে তা অন্তত কিছু সময় সত্য হতে হবে। এই শর্তগুলির মধ্যে একটি হল বিবৃতিটি পরীক্ষা করার জন্য একটি বৃহৎ "মহাবিশ্ব" দৃশ্যকল্প থাকবে। এই ফলাফলের একটি ধাপ হিসাবে, রামসে দেখিয়েছিলেন যে রামসে সংখ্যাটি সসীম।

পাঁচ বছর পরে, Erdős এবং Szekeres দেখিয়েছেন যে Ramsey সংখ্যা k 4 এর কম^k. এবং তার 12 বছর পর, Erdős দেখিয়েছেন যে এটি প্রায় $latex sqrt{2}^k$ থেকে বড়। এটি করার জন্য, তিনি সম্ভাবনাগুলি গণনা করেছিলেন যে এলোমেলোভাবে রঙিন প্রান্ত সহ একটি গ্রাফে একটি একরঙা চক্র রয়েছে। এই "সম্ভাব্য" কৌশলটি গ্রাফ তত্ত্বে ব্যাপকভাবে প্রভাবশালী হয়ে উঠেছে। এটি R(k) দুটি দ্রুত ক্রমবর্ধমান গোলপোস্টের মধ্যে: $latex sqrt{2}^k$ এবং $latex 4^k$।

কয়েক দশক যত কমছে, অসংখ্য গণিতবিদ রামসে সংখ্যার সম্ভাব্য মানের মধ্যে ব্যবধান কমানোর চেষ্টা করেছেন। কিছু সফল: 1975 সালে, জোয়েল স্পেন্সার নিম্ন সীমা দ্বিগুণ. এবং দ্বারা কাগজপত্র একটি সিরিজ কনলন, অ্যান্ড্রু থমাসন এবং অশ্বিন সাহ উপরের সীমা নিচে ঠেলে 4 সালের মধ্যে প্রায় $latex 2^{log(k)^2020}$ এর একটি ফ্যাক্টর দ্বারা। কিন্তু Ramsey সংখ্যার সীমার আকারের তুলনায়, এই সমন্বয়গুলি ছোট ছিল। বিপরীতে, Erdős এবং Szekeres-এর সূত্র R(এ 4-এর কোনো হ্রাসk) < 4^k দ্রুতগতিতে ক্রমবর্ধমান একটি সূচকীয় উন্নতি হবে k বড় হয়

"এটি শুধু একটি চতুর সামান্য প্রশ্ন মত মনে হচ্ছে," বলেন রব মরিস, IMPA এর একজন গণিতবিদ, ব্রাজিলের বিশুদ্ধ ও ফলিত গণিতের ইনস্টিটিউট, রিও ডি জেনেরিওতে, যিনি ক্যাম্পোস, গ্রিফিথস এবং সহস্রবুধের সাথে নতুন ফলাফলের সহ-লেখক। “এটি প্রশংসা করা একটু সূক্ষ্ম. কিন্তু মানুষ সত্যিই এটি সম্পর্কে যত্নশীল।" এই সম্ভবত একটি understatement. "তারা 1936 সালে এটি প্রমাণ করলে, লোকেরা বলত, ঠিক আছে, তাহলে বড় ব্যাপার কী?" বেলা বোলোবাস বলেছেন, যিনি ছিলেন মেমফিস বিশ্ববিদ্যালয়ের মরিস এবং সহস্রবুধের ডক্টরেট উপদেষ্টা। "তারপর থেকে, এটি প্রমাণিত হয়েছে যে এটি একটি খুব বড় সমস্যা, কারণ বছরের পর বছর ধরে, রামসে সমস্যার বিভিন্ন রূপের উপর কয়েক হাজার কাগজপত্র লেখা হয়েছে।" হিসাবে লিয়ানা ইয়েপ্রেমিয়ানএমরি ইউনিভার্সিটির একজন গণিতবিদ বলেছেন, "রামসে সংখ্যাগুলি সমন্বয়বিদ্যা এবং সম্ভাব্যতা এবং জ্যামিতির মধ্যে সেতু তৈরি করে।"

খেলা তত্ত্ব

 আগস্ট 2018 সালে, সহস্রবুধে IMPA-তে মরিসের অধীনে একজন পোস্টডক্টরাল ফেলো ছিলেন। দুজন গ্রিফিথের সাথে একটি নতুন প্রকল্প শুরু করার আশা করছিলেন, যিনি কাছাকাছি পন্টিফিকাল ক্যাথলিক বিশ্ববিদ্যালয়ে শিক্ষকতা করেন, যখন কনলনের একটি কাগজ তাদের দৃষ্টি আকর্ষণ করে। কাগজটি রামসে নম্বরে একটি সূচকীয় উন্নতি পাওয়ার জন্য একটি সম্ভাব্য কৌশলের রূপরেখা দিয়েছে। গ্রিফিথস, মরিস এবং সহস্রবুধে এই ধারণা নিয়ে খেলা শুরু করেন।

"শুরুতে এটি সত্যিই উত্তেজনাপূর্ণ ছিল," সহস্রবুধে স্মরণ করেন। তিনি বলেন, তাদের যুক্তির একটি স্কেচ তৈরি করতে তাদের প্রায় এক মাস সময় লেগেছে।

তাদের পরিকল্পনা ছিল Erdős এবং Szekeres-এর মূল প্রমাণ যে $latex R(k) < 4^k$ এ ব্যবহৃত ধারণার উপর ভিত্তি করে গড়ে তোলা। রামসে নম্বরটি সর্বাধিক $latex 4^k$ প্রমাণ করতে, $latex 4^k$ নোড সহ একটি সম্পূর্ণ গ্রাফে একটি গেম খেলার কল্পনা করুন। গেমটিতে দুইজন খেলোয়াড় রয়েছে। প্রথমত, আপনার প্রতিপক্ষ প্রতিটি প্রান্তকে লাল বা নীল রঙ করে, প্রান্তগুলিকে এমনভাবে রঙ করার আশায় যাতে একটি একরঙা চক্র তৈরি না হয় k নোড

আপনার প্রতিপক্ষের রং করা হয়ে গেলে, একরঙা চক্রের সন্ধান করা আপনার কাজ। আপনি যদি একটি খুঁজে পান, আপনি জিতবেন।

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

আপনার অভিনব আঘাত যে কোনো নোড দিয়ে শুরু করুন. তারপর সংযোগকারী প্রান্তগুলি দেখুন। যদি প্রান্তগুলির অর্ধেক বা তার বেশি লাল হয়, তাহলে সমস্ত নীল প্রান্ত এবং তারা যে নোডগুলির সাথে সংযুক্ত রয়েছে তা মুছুন। তারপরে আপনার আসল পছন্দটি "লাল" বালতিতে রাখুন। এই নোডের সমস্ত লাল প্রান্তগুলি এখনও জীবিত এবং ভাল, বালতির ভিতরে থেকে গ্রাফের বাকি অংশে আঁকড়ে আছে। যদি প্রান্তের অর্ধেকের বেশি নীল হয়, তাহলে আপনি লাল প্রান্ত এবং নোডগুলিকে একইভাবে মুছে ফেলুন এবং নীল বালতিতে রাখুন।

আপনার কোন নোড বাকি না হওয়া পর্যন্ত পুনরাবৃত্তি করুন। (যেহেতু গ্রাফটি সম্পূর্ণ হয়েছে, প্রতিটি অবশিষ্ট নোড যেকোন বিন্দুতে উভয় বালতির সাথে সংযুক্ত থাকে যতক্ষণ না এটি তাদের একটিতে স্থাপন করা হয়।)

আপনি সম্পন্ন হলে, বালতি ভিতরে দেখুন. যেহেতু একটি নোড লাল বালতিতে চলে যায় শুধুমাত্র তার নীল প্রতিবেশীদের নির্মূল করার পরে, লাল বালতির সমস্ত নোডগুলি লাল প্রান্ত দ্বারা সংযুক্ত থাকে — তারা একটি লাল চক্র তৈরি করে। একইভাবে, নীল বালতি একটি নীল চক্র গঠন করে। যদি আপনার আসল গ্রাফে কমপক্ষে $latex 4^k$ নোড থাকে, তাহলে এটি প্রমাণ করা সম্ভব যে এই বালতিগুলির মধ্যে একটিতে অন্তত থাকতে হবে k নোড, মূল গ্রাফে একটি একরঙা চক্রের নিশ্চয়তা দেয়।

এই যুক্তিটি চতুর এবং মার্জিত, কিন্তু এটি আপনাকে দুটি চক্র তৈরি করেছে - একটি নীল এবং একটি লাল - যদিও আপনার শুধুমাত্র একটিরই প্রয়োজন৷ সর্বদা লাল হওয়া আরও কার্যকর হবে, কনলন ব্যাখ্যা করেছেন। এই কৌশলের অধীনে, আপনি প্রতিটি ধাপে একটি নোড বাছাই করবেন, এর নীল প্রান্তগুলি মুছে ফেলবেন এবং লাল বালতিতে নিক্ষেপ করবেন। লাল বালতিটি দ্রুত পূর্ণ হবে এবং আপনি একটি লাল চক্র সংগ্রহ করবেন k অর্ধেক সময়ে নোড.

কিন্তু আপনার কৌশলটি যেকোনো লাল-নীল রঙের জন্য কাজ করতে হবে, এবং আপনি সবসময় প্রচুর লাল প্রান্তের একটি নোড খুঁজে পেতে পারেন কিনা তা জানা কঠিন। সুতরাং কনলনের পরামর্শ অনুসরণ করা এমন একটি নোডে চলে যাওয়ার ঝুঁকি চালায় যার সাথে প্রায় কোনও লাল প্রান্ত সংযুক্ত নেই। এটি আপনাকে একবারে গ্রাফের একটি বিশাল অংশ মুছে ফেলতে বাধ্য করবে, আপনার নোড ফুরিয়ে যাওয়ার আগে আপনাকে আপনার চক্র তৈরি করতে ঝাঁকুনি দেবে। কনলনের পরামর্শ কার্যকর করার জন্য, গ্রিফিথস, মরিস এবং সহস্রবুধেকে প্রমাণ করতে হবে যে এই ঝুঁকি এড়ানো যায়।

একটি ওপেন-বুক পরীক্ষা

তাদের গেমপ্লে আপডেট করার সময়, গ্রিফিথস, মরিস এবং সহস্রবুধে একটু বেশি বৃত্তাকার পথ অনুসরণ করেছিলেন। তাদের লাল এবং নীল বালতিতে নোডগুলি ফেলে সরাসরি একটি একরঙা চক্র তৈরি করার পরিবর্তে, তারা প্রথমে একটি লাল বই নামক কাঠামো তৈরির দিকে মনোনিবেশ করেছিল।

একটি বই, গ্রাফ তত্ত্বে, দুটি অংশ নিয়ে গঠিত: একটি একরঙা চক্র আছে, যাকে "মেরুদণ্ড" বলা হয় এবং একটি দ্বিতীয়, স্বতন্ত্র নোডের ক্লাস্টার যাকে "পৃষ্ঠা" বলা হয়। একটি লাল বইতে, মেরুদণ্ডের মধ্যে সংযোগকারী নোডগুলির সমস্ত প্রান্তগুলি লাল, যেমন প্রান্তগুলি মেরুদণ্ডকে পৃষ্ঠাগুলির সাথে সংযুক্ত করে। পৃষ্ঠাগুলির মধ্যে নোড সংযোগকারী প্রান্তগুলি, যাইহোক, রঙের যেকোনো সংমিশ্রণ হতে পারে। কনলন তার 2018 সালের গবেষণাপত্রে উল্লেখ করেছিলেন যে আপনি যদি একটি বইয়ের পৃষ্ঠাগুলির মধ্যে একটি লাল চক্র খুঁজে পান, তাহলে আপনি এটিকে মেরুদণ্ডের সাথে একত্রিত করে একটি বড় লাল চক্র পেতে পারেন। এটি আপনাকে দুটি সহজ অনুসন্ধানে একটি বড় লাল চক্রের জন্য একটি অনুসন্ধানকে পচন করতে দেয়৷ প্রথমে একটি লাল বই তাকান। তারপর বইয়ের পাতায় একটি চক্র সন্ধান করুন।

গ্রিফিথস, মরিস এবং সহস্রবুধে গেম-বিজয়ী অ্যালগরিদম সামঞ্জস্য করতে চেয়েছিলেন যাতে এটি একটি লাল চক্রের পরিবর্তে একটি লাল বই তৈরি করে। যদিও তারা তাদের প্রকল্পের মাত্র কয়েক সপ্তাহের মধ্যে এই পরিকল্পনাটি স্থির করেছে, তবে এটি কাজ করতে কয়েক বছর সময় লাগবে। তাদের এখনও তাদের সমস্ত লাল প্রান্ত হারানোর হুমকি বন্ধ করতে হবে।

2021 সালে এই প্রকল্পে যোগদানকারী ক্যাম্পোস বলেন, "আমরা খুব দীর্ঘ সময়ের জন্য আটকে ছিলাম।"

এই জানুয়ারিতে, চার গণিতবিদ সমস্যার অন্য সংস্করণে স্যুইচ করতে সম্মত হন। সেই সংস্করণটি আরও জটিল শোনাচ্ছে, তবে এটি আরও সহজ হয়ে উঠেছে।

সব সময়, দলটি রামসে নম্বর R(k), "তির্যক" Ramsey সংখ্যা নামেও পরিচিত। আকারের একটি গ্রাফ R(k) অবশ্যই থাকতে হবে k নোড, সব একই রঙের প্রান্ত দ্বারা সংযুক্ত, কিন্তু সেই রঙ লাল বা নীল কিনা তা কোন ব্যাপার না। অন্যদিকে, "অফ-ডায়াগনাল" রামসে নম্বর R(k, l) পরিমাপ করে যে একটি গ্রাফ কত বড় হতে হবে তার আগে এর সাথে একটি লাল চক্র রয়েছে৷ k নোড, বা সঙ্গে একটি নীল চক্র l নোড তির্যক সমস্যাটি হ্যাক করা চালিয়ে যাওয়ার পরিবর্তে, গ্রুপটি অফ-তির্যক সংস্করণ চেষ্টা করার সিদ্ধান্ত নিয়েছে। এটা উদ্ঘাটন প্রমাণিত.

গ্রিফিথস বলেন, "দীর্ঘ সময় ধরে, মনে হচ্ছিল যে প্রতিটি দরজা আপনি ধাক্কা দিয়েছিলেন তা হয় বন্ধ হয়ে গেছে, বা অন্তত পক্ষে যাওয়া বেশ কঠিন," গ্রিফিথস বলেছিলেন। “এবং সেই পরিবর্তনের পরে, আপনি অনুভব করেছিলেন যেন প্রতিটি দরজা খোলা ছিল। একরকম, সবকিছু ঠিক কাজ বলে মনে হচ্ছে।" অফ-তির্যক সংস্করণে, তারা একটি নির্দিষ্ট প্রোটোকল অনুসরণ করে একবারে একগুচ্ছ নীল প্রান্ত মুছে ফেলার একটি উপায় খুঁজে পেয়েছিল, যা লাল প্রান্তের ঘনত্ব বৃদ্ধি করে এবং অফ-তির্যক রামসে নম্বরে একটি উন্নত আবদ্ধতার দিকে পরিচালিত করে। এই পদ্ধতি, একটি "ঘনত্ব বৃদ্ধি" যুক্তি বলা হয়, আগে সমাধান করার জন্য ব্যবহার করা হয়েছিল সংমিশ্রণে অন্যান্য গুরুত্বপূর্ণ সমস্যা, কিন্তু এটি Ramsey নম্বর সমস্যা ব্যবহার করা হয়নি.

চারজন গণিতবিদ তারপরে তির্যক ফলাফলের পথ পরিষ্কার করতে অফ-তির্যক রামসে নম্বরে নতুন বাউন্ড ব্যবহার করেছিলেন। ফেব্রুয়ারির শুরুতে, তারা অবশেষে সূচকীয় ফ্যাক্টর দ্বারা রামসে সংখ্যার সীমা কমিয়ে দিয়েছিল, একটি অর্জন গণিতবিদরা প্রায় এক শতাব্দী ধরে চেয়েছিলেন। এবং 1935 সালে Erdős এবং Szekeres যে যুক্তিটি তুলে ধরেছিলেন, সেই একই যুক্তির আধুনিকীকরণের মাধ্যমে তারা এটি করেছিলেন।

এপসিলন, এপসিলন

16 মার্চ আলোচনার পর, অংশগ্রহণকারীরা গুজব নিশ্চিত করতে শুরু করে। সহস্রবুধের কথোপকথনের ছবিগুলি ফোন কল এবং ব্যক্তিগত বার্তাগুলির মাধ্যমে প্রচারিত হয়েছিল — এমনকি ক অস্পষ্ট কিন্তু পরামর্শমূলক পোস্ট গণিতবিদ গিল কালাইয়ের ব্লগে। ক্যাম্পোস, গ্রিফিথস, সহস্রবুধে এবং মরিস দাবি করেছেন যে $latex R(k) <3.993^k$। ওই রাতেই চার লেখক ড তাদের কাগজ অনলাইন পোস্ট, গণিতবিদদের নিজেদের জন্য নতুন প্রমাণ দেখতে অনুমতি দেয়।

"আমি মনে করি আমাদের মধ্যে অনেকেই আমাদের জীবনে এমন উন্নতি দেখতে আশা করিনি, মূলত," বলেন মাতিজা বুসিচ, প্রিন্সটন ইউনিভার্সিটি এবং ইনস্টিটিউট ফর অ্যাডভান্সড স্টাডির একজন গণিতবিদ। "আমি মনে করি এটি একটি একেবারে আশ্চর্যজনক ফলাফল।"

অনেক বিশেষজ্ঞ আশাবাদী যে, সূচকীয় বাধা কমে গেলে, আরও অগ্রগতি দ্রুত অনুসরণ করবে। নতুন কাগজের লেখকরা ইচ্ছাকৃতভাবে তাদের পদ্ধতিকে তার সীমাতে ঠেলে দেননি, অপ্রয়োজনীয় বিবরণ দিয়ে তাদের যুক্তিকে মেঘলা এড়াতে। "আমি খুব আগ্রহী যে পদ্ধতিটি আসলে কতদূর যেতে পারে, কারণ আমার কোন ধারণা নেই," ক্যাম্পোস বলেছিলেন।

“এটি একটি সম্পূর্ণ বুদ্ধিমান, একেবারে বিস্ময়কর প্রমাণ এবং একটি সত্যিকারের সাফল্য। তাই এখন আমি আশা করি ফ্লাডগেট খুলে দেওয়া হবে,” বলোবাস বলেছেন। “আমি নিশ্চিত যে তিন বছরের মধ্যে, বিতর্কটি সম্ভাব্য উন্নতির বিষয়ে হবে। আমরা কি 3.993 থেকে 3.9 পর্যন্ত উন্নতি করতে পারি? হতে পারে 3.4? এবং 3 সম্পর্কে কি?"

নতুন প্রমাণটি 56 পৃষ্ঠায় আসে, এবং কম্বিনেটোরিক্স সম্প্রদায় দ্বারা প্রতিটি বিশদ সম্পূর্ণরূপে যাচাই করতে কয়েক সপ্তাহ সময় লাগবে। তবে সহকর্মীরা আশাবাদী। “এই লেখকদের দল, তারা খুব সিরিয়াস মানুষ। এবং তারা এমন লোক যারা সত্যিই, খুব প্রযুক্তিগত জিনিসগুলিতে সত্যিই ভাল,” উইগডারসন বলেছিলেন।

যখন তার সহযোগীদের কথা আসে, গ্রিফিথ সম্মত হন। “ব্রিলিয়ান্ট লোকদের সাথে কাজ করাটা একটা সৌভাগ্যের ব্যাপার, তাই না? এবং আমি মনে করি এর জন্য আমি খুব কৃতজ্ঞ বোধ করি,” তিনি বলেছিলেন। "যদি তারা এটি আমার উপর ছেড়ে দিত, তবে বিস্তারিত সঠিক পেতে আমার আরও পাঁচ বছর লাগতে পারে।"