Burr–Erdős conjecture
গণিতে, বুর-আর্দোস অনুমান ছিল বিরল গ্রাফের রামসে সংখ্যা সম্পর্কিত একটি সমস্যা। অনুমানটি স্টেফান বার এবং পল এরদোসের নামে নামকরণ করা হয়েছে এবং এটি এরদোসের নামে নামকরণ করা অনেকগুলি অনুমানের মধ্যে একটি; এতে বলা হয়েছে যে গ্রাফের যে কোনও বিরল পরিবারের গ্রাফের রামসে সংখ্যা গ্রাফের শীর্ষের সংখ্যার সাথে রৈখিকভাবে বৃদ্ধি করা উচিত। অনুমানটি চুংবাম লি দ্বারা প্রমাণিত হয়েছিল। সুতরাং এটি এখন একটি উপপাদ্য। সংজ্ঞা জি যদি একটি অনির্দিষ্ট গ্রাফ হয়, তবে জি-এর অবক্ষয় হল ন্যূনতম সংখ্যা পি যাতে জি-এর প্রতিটি উপ-গ্রাফে ডিগ্রি পি বা তার চেয়ে ছোট একটি শীর্ষ থাকে। ডিজেনারেসি পি সহ একটি গ্রাফকে পি-ডিজেনারেট বলা হয়। সমতুল্যভাবে, একটি পি-ডিজেনারেট গ্রাফ এমন একটি গ্রাফ যা বারবার ডিগ্রি পি বা তার চেয়ে ছোট একটি শীর্ষস্থান সরিয়ে খালি গ্রাফে হ্রাস করা যেতে পারে। এটি রামসের উপপাদ্য থেকে পাওয়া যায় যে, যে কোনও গ্রাফ জি-এর জন্য একটি ন্যূনতম পূর্ণসংখ্যা, জি-এর রামসে সংখ্যা রয়েছে, যাতে কমপক্ষে যে কোনও শীর্ষে যে কোনও সম্পূর্ণ গ্রাফ যার প্রান্তগুলি লাল বা নীল রঙের হয় তাতে জি-এর একবর্ণের অনুলিপি থাকে। উদাহরণস্বরূপ, একটি ত্রিভুজের রামসে সংখ্যা 6 হয়ঃ ছয়টি শীর্ষে একটি সম্পূর্ণ গ্রাফের প্রান্তগুলি লাল বা নীল রঙের হোক না কেন, সর্বদা একটি লাল ত্রিভুজ বা নীল ত্রিভুজ থাকে। 1973 সালে, স্টিফেন বার এবং পল এরদোস নিম্নলিখিত অনুমানটি করেছিলেনঃ প্রতিটি পূর্ণসংখ্যা p-এর জন্য একটি ধ্রুবক cp বিদ্যমান যাতে n শীর্ষে যে কোনও p-ডিজেনারেট গ্রাফ G-এর সর্বাধিক cp n থাকে। অর্থাৎ, যদি একটি n-ভার্টেক্স গ্রাফ G-এর p-ডিজেনারেট হয়, তবে প্রতিটি দুই প্রান্তের সম্পূর্ণ গ্রাফে cp n শীর্ষে G-এর একটি একবর্ণ প্রতিলিপি থাকা উচিত। সম্পূর্ণ অনুমান প্রমাণিত হওয়ার আগে, কিছু বিশেষ ক্ষেত্রে এটি প্রথমে নিষ্পত্তি করা হয়েছিল। এটি দ্বারা আবদ্ধ-ডিগ্রি গ্রাফের জন্য প্রমাণিত হয়েছিল; তাদের প্রমাণ সিপি-র একটি খুব উচ্চ মানের দিকে পরিচালিত করেছিল এবং এই ধ্রুবকটির উন্নতি এবং দ্বারা করা হয়েছিল। আরও সাধারণভাবে, অনুমানটি পি-বিন্যাসযোগ্য গ্রাফের জন্য সত্য বলে জানা যায়, যার মধ্যে সীমাবদ্ধ সর্বাধিক ডিগ্রি সহ গ্রাফ, প্ল্যানার গ্রাফ এবং গ্রাফ রয়েছে যা কেপি-র একটি উপবিভাগ ধারণ করে না। এটি উপবিভক্ত গ্রাফের জন্যও পরিচিত, যেখানে কোনও দুটি সংলগ্ন শীর্ষে দুটির চেয়ে বেশি ডিগ্রি থাকে না। নির্বিচারে গ্রাফের জন্য, রামসে সংখ্যাটি এমন একটি ফাংশন দ্বারা আবদ্ধ বলে জানা যায় যা কেবল সামান্য অতি রৈখিকভাবে বৃদ্ধি পায়। বিশেষত, দেখানো হয়েছে যে একটি ধ্রুবক সিপি বিদ্যমান যে, যে কোনও পি-ডিজেনারেট এন-ভার্টেক্স গ্রাফ জি-এর জন্য, নোটস রেফারেন্স। । । । । । । । । গ্রাফ তত্ত্ব রামসে তত্ত্ব যে অনুমানগুলি প্রমাণিত হয়েছে বার-আর্দোস অনুমান গ্রাফ তত্ত্বের উপপাদ্য