১/৩–২/৩ অনুমান

ক্রম তত্ত্বে, গণিতের একটি শাখা, ১/৩–২/৩ অনুমান বলে যে, যদি কেউ একটি সেটের উপাদানগুলিকে তুলনা সর্ট করে, তবে পূর্বে যে তুলনাগুলি করা হয়েছে তা নির্বিশেষে, সর্বদা পরবর্তী তুলনাটি এমনভাবে বেছে নেওয়া সম্ভব যা সম্ভাব্য সর্টকৃত ক্রমের সংখ্যাকে ২/৩ বা তারও ভালো একটি গুণক দ্বারা হ্রাস করে। সমতুল্যভাবে, প্রতিটি সসীম আংশিকভাবে ক্রমিত সেটে যা সম্পূর্ণ ক্রমিত নয়, এমন একটি জোড়া উপাদান x এবং y বিদ্যমান যার বৈশিষ্ট্য হল আংশিক ক্রমের রৈখিক সম্প্রসারণগুলির কমপক্ষে ১/৩ এবং সর্বাধিক ২/৩ অংশ x কে y এর আগে স্থাপন করে।

উদাহরণ
তিনটি উপাদান a, b, এবং c নিয়ে গঠিত একটি আংশিক ক্রম একটি একক তুলনীয় সম্পর্ক সহ,  এর তিনটি রৈখিক সম্প্রসারণ রয়েছে:   এবং  এই তিনটি সম্প্রসারণের সবকটিতেই, a b এর আগে আসে। তবে, a c এর আগে শুধুমাত্র দুটিতে আসে, এবং তৃতীয়টিতে c এর পরে আসে। অতএব, a এবং c এর জোড়ার কাঙ্ক্ষিত বৈশিষ্ট্য রয়েছে, যা দেখায় যে এই আংশিক ক্রমটি ১/৩–২/৩ অনুমান মেনে চলে।

এই উদাহরণটি দেখায় যে অনুমানের ১/৩ এবং ২/৩ ধ্রুবকগুলি টাইট; যদি q ১/৩ এবং ২/৩ এর মধ্যে কঠোরভাবে কোনো ভগ্নাংশ হয়, তবে এমন কোনো জোড়া x, y থাকবে না যেখানে x y এর আগে এমন আংশিক ক্রমের সংখ্যায় যা মোট আংশিক ক্রমের q এবং  গুণের মধ্যে থাকে।

সাধারণভাবে, P কে তিন-উপাদান আংশিক ক্রম এবং একক-উপাদান আংশিক ক্রমের যেকোনো সিরিজ রচনা হিসাবে ধরা যাক, যেমন চিত্রে রয়েছে। তাহলে P ১/৩–২/৩ অনুমানের জন্য একটি চরম ক্ষেত্র গঠন করে, এই অর্থে যে প্রতিটি জোড়া x, y উপাদানের জন্য, দুটি উপাদানের মধ্যে একটি অন্যটির আগে P এর রৈখিক সম্প্রসারণের সর্বাধিক ১/৩ অংশে ঘটে। এই কাঠামো সহ আংশিক ক্রমগুলি অগত্যা সিরিজ-সমান্তরাল সেমিআর্ডার; এগুলি অনুমানের জন্য একমাত্র পরিচিত চরম ক্ষেত্র এবং প্রমাণিত হয়েছে যে এগুলি প্রস্থ দুই সহ একমাত্র চরম ক্ষেত্র।

সংজ্ঞা
একটি আংশিক ক্রমিত সেট হল একটি সেট X একটি বাইনারি রিলেশন ≤ সহ যা রিফ্লেক্সিভ, অ্যান্টিসিমেট্রিক এবং ট্রানজিটিভ। একটি সম্পূর্ণ ক্রম হল একটি আংশিক ক্রম যেখানে প্রতিটি জোড়া উপাদান তুলনীয়। একটি সসীম আংশিক ক্রমের একটি রৈখিক সম্প্রসারণ হল X এর উপাদানগুলির একটি অনুক্রমিক ক্রম, যার বৈশিষ্ট্য হল যদি আংশিক ক্রমে x ≤ y হয়, তবে x রৈখিক সম্প্রসারণে y এর আগে আসতে হবে। অন্য কথায়, এটি আংশিক ক্রমের সাথে সামঞ্জস্যপূর্ণ একটি সম্পূর্ণ ক্রম। যদি একটি সসীম আংশিক ক্রমিত সেট সম্পূর্ণ ক্রমিত হয়, তবে এটির শুধুমাত্র একটি রৈখিক সম্প্রসারণ থাকে, কিন্তু অন্যথায় এটির একাধিক থাকবে। ১/৩–২/৩ অনুমান বলে যে কেউ দুটি উপাদান x এবং y বেছে নিতে পারে যাতে, এই সম্ভাব্য রৈখিক সম্প্রসারণগুলির সেটের মধ্যে, তাদের মধ্যে ১/৩ থেকে ২/৩ x কে y এর আগে স্থাপন করে এবং প্রতিসমভাবে তাদের মধ্যে ১/৩ থেকে ২/৩ y কে x এর আগে 

১/৩–২/৩ অনুমানের একটি বিকল্প এবং সমতুল্য বিবৃতি সম্ভাব্যতা তত্ত্বের ভাষায় রয়েছে।
কেউ রৈখিক সম্প্রসারণগুলির উপর একটি ইউনিফর্ম সম্ভাব্যতা বণ্টন সংজ্ঞায়িত করতে পারে যেখানে প্রতিটি সম্ভাব্য রৈখিক সম্প্রসারণ নির্বাচনের সমান সম্ভাবনা থাকে। ১/৩–২/৩ অনুমান বলে যে, এই সম্ভাব্যতা বণ্টনের অধীনে, এমন একটি জোড়া উপাদান x এবং y বিদ্যমান যেখানে একটি এলোমেলো রৈখিক সম্প্রসারণে x y এর আগে হওয়ার সম্ভাবনা ১/৩ এবং ২/৩ এর মধ্যে থাকে।

১৯৮৪ সালে, জেফ কাহন এবং মাইকেল স্যাক্স যেকোন আংশিক ক্রমিত সেট P এর জন্য δ(P) সংজ্ঞায়িত করেছেন, যাতে δ(P) হল সবচেয়ে বড় বাস্তব সংখ্যা δ যেমন P এর একটি জোড়া x, y রয়েছে যেখানে x y এর আগে রৈখিক সম্প্রসারণের সংখ্যায় যা মোট রৈখিক সম্প্রসারণের δ এবং  এর মধ্যে থাকে। এই স্বরলিপিতে, ১/৩–২/৩ অনুমান বলে যে প্রতিটি সসীম আংশিক ক্রম যা সম্পূর্ণ নয়, তার  রয়েছে।

ইতিহাস
১/৩–২/৩ অনুমানটি ১৯৬৮ সালে সার্গেই কিসলিটসিন দ্বারা প্রণয়ন করা হয়েছিল, এবং পরে স্বাধীনভাবে মাইকেল ফ্রেডম্যান এবং ১৯৮৪ সালে নাতি লিনিয়াল দ্বারা তৈরি করা হয়েছিল। এটি অর্ডার জার্নাল প্রতিষ্ঠার সময় একটি বৈশিষ্ট্যযুক্ত অমীমাংসিত সমস্যা হিসাবে তালিকাভুক্ত করা হয়েছিল এবং অমীমাংসিত রয়ে গেছে; একে "পোসেটের কম্বিনেটোরিয়াল তত্ত্বে সবচেয়ে আকর্ষণীয় সমস্যাগুলির মধ্যে একটি" বলা হয়েছে।

১৯৯৯ সালে এই অনুমানের একটি সমীক্ষা তৈরি করা হয়েছিল।

আংশিক ফলাফল
১/৩–২/৩ অনুমান নির্দিষ্ট শ্রেণীর আংশিক ক্রমের জন্য সত্য বলে জানা গেছে, যার মধ্যে প্রস্থ দুই সহ আংশিক ক্রম, উচ্চতা দুই সহ আংশিক ক্রম, সর্বাধিক 11টি উপাদান সহ আংশিক ক্রম, আংশিক ক্রম যেখানে প্রতিটি উপাদান সর্বাধিক ছয়টির সাথে অসম্পর্কিত, সিরিজ-সমান্তরাল আংশিক ক্রম এবং আংশিক ক্রম যার হাসে ডায়াগ্রাম N-মুক্ত, সেমিআর্ডার। এবং পলিট্রি। সীমাতে n যখন অসীমের দিকে যায়, n-উপাদান আংশিক ক্রমের অনুপাত যা ১/৩–২/৩ অনুমান মেনে চলে তা 100% এর দিকে ঝোঁক।

১৯৯৫ সালে, গ্রাহাম ব্রাইটওয়েল, স্টিফান ফেলসনার এবং উইলিয়াম ট্রটার প্রমাণ করেছিলেন যে, যেকোন সসীম আংশিক ক্রম P যা সম্পূর্ণ নয়, তার জন্য  তাদের ফলাফল পূর্বের দুর্বল একই ধরনের সীমাকে উন্নত করে। তারা δ(P) এর সম্ভাব্যতা ব্যাখ্যা ব্যবহার করে নির্দিষ্ট অসীম আংশিক ক্রমে এর সংজ্ঞা প্রসারিত করে; সেই প্রসঙ্গে, তারা দেখায় যে তাদের সীমা সর্বোত্তম, কারণ এমন অসীম আংশিক ক্রম রয়েছে যার

অ্যাপ্লিকেশন
১৯৮৪ সালে জেফ কাহন এবং স্যাক্স সমস্যার জন্য নিম্নলিখিত অ্যাপ্লিকেশন প্রস্তাব করেছিলেন:
ধরুন কেউ তুলনা সর্ট করতে চায় একটি সম্পূর্ণ ক্রমিত সেট X, যার জন্য কিছু আংশিক ক্রম তথ্য ইতিমধ্যেই X এর একটি আংশিক ক্রম আকারে পরিচিত। সবচেয়ে খারাপ ক্ষেত্রে, উপাদানগুলির প্রতিটি অতিরিক্ত তুলনা x এবং y যতটা সম্ভব কম তথ্য প্রদান করতে পারে, তুলনার ফলাফলের সাথে সামঞ্জস্যপূর্ণ যতগুলি সম্ভব রৈখিক সম্প্রসারণ রেখে তুলনাটি সমাধান করে। ১/৩–২/৩ অনুমান বলে যে, প্রতিটি ধাপে, কেউ একটি তুলনা সম্পাদন করতে বেছে নিতে পারে যা অবশিষ্ট রৈখিক সম্প্রসারণের সংখ্যাকে ২/৩ এর একটি গুণক দ্বারা হ্রাস করে; অতএব, যদি প্রাথমিক তথ্য দ্বারা প্রদত্ত আংশিক ক্রমের E রৈখিক সম্প্রসারণ থাকে, তবে সর্টিং সমস্যাটি সর্বাধিক log3/2E অতিরিক্ত তুলনায় সম্পন্ন হতে পারে।

যাইহোক, এই বিশ্লেষণটি সর্বোত্তম জোড়া x এবং y বেছে নেওয়ার জটিলতাকে অবহেলা করে। অতিরিক্তভাবে, এই বিশ্লেষণ যা পরামর্শ দেয় তার চেয়ে কম সংখ্যক তুলনা ব্যবহার করে একটি আংশিক ক্রম সর্ট করা সম্ভব হতে পারে, কারণ একটি সর্টিং অ্যালগরিদমের প্রতিটি ধাপে এই সবচেয়ে খারাপ-ক্ষেত্রের আচরণ ঘটতে পারে না। এই দিকে, এটি অনুমান করা হয়েছে যে logφE তুলনা যথেষ্ট হতে পারে, যেখানে φ সোনালি অনুপাত বোঝায়।

তুলনা সর্টিং সমস্যার একটি ঘনিষ্ঠভাবে সম্পর্কিত শ্রেণী ১৯৭৬ সালে ফ্রেডম্যান দ্বারা বিবেচনা করা হয়েছিল, যার মধ্যে X কে তুলনা সর্ট করার সমস্যা রয়েছে যখন X এর সর্ট করা ক্রমটি X এর কিছু পারমুটেশন সেট S তে অবস্থিত বলে জানা যায়। এখানে S অগত্যা একটি আংশিক ক্রমের রৈখিক সম্প্রসারণের সেট হিসাবে তৈরি হয় না। এই অতিরিক্ত সাধারণতা সত্ত্বেও, ফ্রেডম্যান দেখিয়েছিলেন যে X কে log2|S| + O(|X|) তুলনা ব্যবহার করে সর্ট করা যেতে পারে, বিগ ও নোটেশনে প্রকাশিত। এই একই সীমা আংশিক ক্রমের ক্ষেত্রেও প্রযোজ্য এবং দেখায় যে log2E + O(n) তুলনা যথেষ্ট।

সাধারণীকরণ এবং সম্পর্কিত ফলাফল
১৯৮৪ সালে, কাহন এবং স্যাক্স অনুমান করেছিলেন যে, w অসীমের দিকে যাওয়ার সীমাতে, w প্রস্থের আংশিক ক্রমিত সেটের জন্য δ(P) এর মান ১/২ এর দিকে ঝোঁকাবে। বিশেষ করে, তারা আশা করে যে শুধুমাত্র প্রস্থ দুই সহ আংশিক ক্রমিত সেটগুলি সবচেয়ে খারাপ ক্ষেত্রের মান  অর্জন করতে পারে এবং ১৯৮৫ সালে মার্টিন আইগনার স্পষ্টভাবে এটি একটি অনুমান হিসাবে উল্লেখ করেছিলেন। তিন প্রস্থের পোসেটের জন্য δ(P) এর ক্ষুদ্রতম পরিচিত মান হল ১৪/৩৯, এবং কম্পিউটার অনুসন্ধানগুলি দেখিয়েছে যে নয় বা তার কম উপাদান সহ প্রস্থ-৩ পোসেটের জন্য আরও ছোট মান সম্ভব নয়। আরেকটি সম্পর্কিত অনুমান, আবার কম্পিউটার অনুসন্ধানের উপর ভিত্তি করে, বলে যে ১/৩ এবং δ(P) এর অন্যান্য সম্ভাব্য মানগুলির মধ্যে একটি ব্যবধান রয়েছে: যখনই একটি আংশিক ক্রমে δ(P) ঠিক ১/৩ না থাকে, তখন এতে δ(P) ≥ ০.৩৪৮৮৪৩ থাকে।

মার্সিন পেকজারস্কি একটি "সোনালি বিভাজন অনুমান" প্রণয়ন করেছেন যা বলে যে প্রতিটি আংশিক ক্রমে যা সম্পূর্ণ ক্রম নয়, কেউ দুটি পরপর তুলনা খুঁজে পেতে পারে যেমন, যদি ti i তম তুলনা করার পরে অবশিষ্ট রৈখিক সম্প্রসারণের সংখ্যা নির্দেশ করে, তাহলে (তুলনার চারটি সম্ভাব্য ফলাফলের প্রতিটিতে)  যদি এই অনুমানটি সত্য হয়, তবে এটি ১/৩–২/৩ অনুমানকে বোঝাবে: দুটি তুলনার মধ্যে প্রথমটি অবশ্যই এমন একটি জোড়ার মধ্যে হতে হবে যা অবশিষ্ট তুলনাগুলিকে সবচেয়ে খারাপভাবে ১/৩–২/৩ অনুপাত দ্বারা বিভক্ত করে। সোনালি বিভাজন অনুমানটি আরও বোঝাবে যে E রৈখিক সম্প্রসারণ সহ একটি আংশিক ক্রমকে সর্বাধিক logφE তুলনায় সর্ট করা যেতে পারে; অনুমানের নামটি সোনালি অনুপাতের সাথে এই সংযোগ থেকে নেওয়া হয়েছে।

এটি #P-সম্পূর্ণ, একটি সসীম আংশিক ক্রম P এবং একটি জোড়া উপাদান x এবং y দেওয়া হলে, P এর রৈখিক সম্প্রসারণের অনুপাত গণনা করা যেগুলি x কে y এর আগে স্থাপন করে।

টীকা

তথ্যসূত্র
.
.
.
.
.
.

.
.
. As cited by .
. 
.
.
.
.

.
.
.

ক্রম তত্ত্ব
অনুমান
গণিতে অমীমাংসিত সমস্যা