Ramsey-Turán theory
রামসে-তুরান তত্ত্ব হল চরম গ্রাফ তত্ত্বের একটি উপক্ষেত্র। এটি রামসের উপপাদ্য এবং তুরানের উপপাদ্যের সাধারণ সাধারণীকরণ অধ্যয়ন করে। সংক্ষেপে, রামসে-তুরান তত্ত্ব একটি গ্রাফের সর্বাধিক সংখ্যক প্রান্তের জন্য জিজ্ঞাসা করে যা তার উপগ্রাফ এবং কাঠামোর সীমাবদ্ধতাগুলি সন্তুষ্ট করতে পারে। এই তত্ত্বটি চরম গ্রাফ তত্ত্বে উদ্ভূত অনেক প্রাকৃতিক প্রশ্নকে সংগঠিত করে। এই তত্ত্বের কেন্দ্রীয় ধারণাগুলি আনুষ্ঠানিক করার প্রথম লেখক ছিলেন 1969 সালে এরদোস এবং সোস, যদিও গণিতবিদরা এর আগে অনেক রামসে-তুরান-ধরনের সমস্যা তদন্ত করেছিলেন। রামসের উপপাদ্য এবং তুরানের উপপাদ্য দুটি রঙ এবং সম্পূর্ণ গ্রাফের জন্য রামসের উপপাদ্য, যা 1930 সালে তার মূল আকারে প্রমাণিত হয়, বলে যে কোনও ধনাত্মক পূর্ণসংখ্যার জন্য এত বড় একটি পূর্ণসংখ্যা বিদ্যমান যে দুটি রঙ ব্যবহার করে সম্পূর্ণ গ্রাফের প্রান্তের যে কোনও রঙের জন্য এর একটি একরঙা অনুলিপি রয়েছে। আরও সাধারণভাবে, যে কোনও গ্রাফের জন্য, এমন একটি সীমা থাকে যে যদি এবং এর প্রান্তগুলি নির্বিচারে রঙের সাথে রঙ করা হয়, তবে কারও কারও জন্য তম রঙে একটি থাকে। তুরানের উপপাদ্য, যা 1941 সালে প্রমাণিত হয়, শীর্ষে প্রান্তের সর্বাধিক সংখ্যা সহ গ্রাফটিকে চিহ্নিত করে যা a ধারণ করে না। বিশেষত, উপপাদ্যটি বলে যে সমস্ত ধনাত্মক পূর্ণসংখ্যার জন্য, একটি-ভার্টেক্স গ্রাফের প্রান্তের সংখ্যা যা একটি সাবগ্রাফ হিসাবে থাকে না এবং সর্বাধিক তুরান গ্রাফ দ্বারা অনন্যভাবে অর্জন করা হয়। এই দুটি ক্লাসিক ফলাফলই একটি নির্দিষ্ট বৈশিষ্ট্যের অধিকারী হওয়ার আগে একটি গ্রাফ কতটা বড় হতে পারে সে সম্পর্কে প্রশ্ন জিজ্ঞাসা করে। তবে একটি উল্লেখযোগ্য শৈলীগত পার্থক্য রয়েছে। তুরানের উপপাদ্যের চরম গ্রাফের একটি খুব কঠোর কাঠামো রয়েছে, যার একটি ছোট ক্রোমাটিক সংখ্যা রয়েছে এবং এতে অল্প সংখ্যক বড় স্বাধীন সেট রয়েছে। অন্যদিকে, রামসে সমস্যায় বিবেচিত গ্রাফটি সম্পূর্ণ গ্রাফ, যার বড় ক্রোমাটিক সংখ্যা রয়েছে এবং কোনও অ-তুচ্ছ স্বাধীন সেট নেই। এই দুই ধরনের সমস্যাকে একত্রিত করার একটি স্বাভাবিক উপায় হল আন্দ্রাসফাই দ্বারা উত্থাপিত নিম্নলিখিত প্রশ্নটি জিজ্ঞাসা করাঃ সমস্যা 1: একটি প্রদত্ত ধনাত্মক পূর্ণসংখ্যার জন্য, একটি-ভার্টেক্স গ্রাফ থাকা উচিত যা স্বাধীন সংখ্যা ধারণ করে না। এই ধরনের গ্রাফের সর্বাধিক কতটি প্রান্ত থাকতে পারে? মূলত, এই প্রশ্নটি রামসে সেটিং-এ তুরান সমস্যার উত্তর চায়; এটি তুরানের সমস্যাটিকে কম সুশৃঙ্খল, আরও এলোমেলো কাঠামো সহ গ্রাফের একটি উপসেটে সীমাবদ্ধ করে। নিম্নলিখিত প্রশ্নটি সমস্যাগুলিকে বিপরীত দিকে একত্রিত করেঃ সমস্যা 2: ধরা যাক স্থির গ্রাফ। শীর্ষে একটি-প্রান্ত রঙিন গ্রাফের সর্বাধিক কতটি প্রান্ত থাকতে পারে এই শর্তে যে এতে তম রঙে একটি নেই? সাধারণ সমস্যা রামসে-তুরান তত্ত্বের মেরুদণ্ড হল উপরের সমস্যাগুলির সাধারণ সাধারণীকরণ। সমস্যা 3: গ্রাফ স্থির করা যাক। ধরা যাক একটি-প্রান্ত-রঙের-ভার্টেক্স গ্রাফ সন্তোষজনক (1) (2) তম রঙ দ্বারা সংজ্ঞায়িত উপগ্রাফটিতে নেই। প্রান্তের সর্বাধিক সংখ্যা কত হতে পারে? আমরা দ্বারা সর্বাধিক নির্দেশ করি। রামসে-তুরান-ধরনের সমস্যাগুলি সমস্যা 3-এর বিশেষ ক্ষেত্রে হয়। এই সমস্যার অনেক ক্ষেত্রেই খোলা থাকে, তবে বেশ কয়েকটি আকর্ষণীয় ক্ষেত্রে সুনির্দিষ্ট অ্যাসিম্পটোটিক সমাধান দিয়ে সমাধান করা হয়েছে। উল্লেখযোগ্য ফলাফল স্বাধীনতা সংখ্যার সীমাবদ্ধতার উপর নির্ভর করে সমস্যা 3-কে তিনটি ভিন্ন ক্ষেত্রে ভাগ করা যেতে পারে। সীমাবদ্ধতা-মুক্ত কেস রয়েছে, যেখানে, যা ক্লাসিক রামসে সমস্যায় হ্রাস পায়। "মধ্যবর্তী" কেস রয়েছে, যেখানে একটি স্থিরের জন্য। সবশেষে, একটি কেস রয়েছে, যার মধ্যে সবচেয়ে বড় সমস্যা রয়েছে। এই পরিসরে সবচেয়ে মৌলিক অ-তুচ্ছ সমস্যাটি হল যখন এরডোস এবং সোস 1969 সালে এই পরিস্থিতিতে রামসে-তুরান সংখ্যার অ্যাসিম্পটোটিক মান নির্ধারণ করেনঃ জোড় সংখ্যার শীর্ষে সম্পূর্ণ গ্রাফের বিষয়টি অনেক বেশি চ্যালেঞ্জিং, এবং 1983 সালে এরডস, হাজনাল, সোস এবং স্জেমেরডি দ্বারা সমাধান করা হয়েছিলঃ লক্ষ্য করুন যে উভয় ক্ষেত্রেই, সমস্যাটিকে তুরানের উপপাদ্যের অতিরিক্ত শর্ত যোগ করা হিসাবে দেখা যেতে পারে। উভয় ক্ষেত্রেই, এটি দেখা যায় যে উপসর্গহীনভাবে, প্রভাবটি একই রকম যেন আমরা বা-এর পরিবর্তে বাদ দিয়েছিলাম। তথ্যসূত্র গ্রাফ তত্ত্ব