प्रतिश्रृंखला

गणित में, आदेश सिद्धांत के क्षेत्र में, एक एंटीचैन आंशिक रूप से ऑर्डर किए गए सेट का एक उपसमुच्चय है, जैसे कि सबसेट में दो अलग-अलग तत्व अतुलनीय हैं।

आंशिक रूप से ऑर्डर किए गए सेट में सबसे बड़े एंटीचेन का आकार इसकी चौड़ाई (आंशिक क्रम) के रूप में जाना जाता है। दिलवर्थ के प्रमेय द्वारा, यह श्रृंखलाओं की न्यूनतम संख्या (पूरी तरह से क्रमबद्ध उपसमुच्चय) के बराबर है जिसमें सेट को विभाजित किया जा सकता है। आंशिक रूप से आदेशित सेट की ऊंचाई (इसकी सबसे लंबी श्रृंखला की लंबाई) मिर्स्की के प्रमेय के बराबर होती है, जिसमें न्यूनतम संख्या में एंटीचिन्स होते हैं, जिसमें सेट को विभाजित किया जा सकता है।

एक परिमित आंशिक रूप से आदेशित सेट में सभी एंटीचेन्स के परिवार को एक वितरण जाली में बनाने के लिए संचालन में शामिल होने और मिलने के लिए दिया जा सकता है। परिमित समुच्चय के सभी उपसमुच्चयों के आंशिक रूप से क्रमबद्ध प्रणाली के लिए, समुच्चय समावेशन द्वारा आदेशित, प्रतिश्रृंखलाओं को स्पर्नर परिवार कहा जाता है और उनकी जाली एक मुक्त वितरण वाली जाली है, जिसमें डेडेकिंड तत्वों की संख्या होती है। अधिक आम तौर पर, परिमित आंशिक रूप से आदेशित सेट के एंटीचेन्स की संख्या की गणना ♯P-पूर्ण|#P-पूर्ण है।

परिभाषाएँ

होने देना $S$ आंशिक रूप से आदेशित सेट बनें। दो तत्व $a$ और $b$ आंशिक रूप से आदेशित सेट को तुलनात्मकता कहा जाता है यदि $a\leq b{\text{ or }}b\leq a.$ यदि दो तत्व तुलनीय नहीं हैं, तो उन्हें अतुलनीय कहा जाता है; वह है, $x$ और $y$ अतुलनीय हैं यदि न तो $x\leq y{\text{ nor }}y\leq x.$ में एक जंजीर $S$ एक उपसमुच्चय है $C\subseteq S$ जिसमें तत्वों की प्रत्येक जोड़ी तुलनीय है; वह है, $C$ कुल आदेश है। एक एंटीचैन में $S$ एक उपसमुच्चय है $A$ का $S$ जिसमें विभिन्न तत्वों का प्रत्येक युग्म अतुलनीय है; अर्थात्, इसमें किन्हीं दो भिन्न तत्वों के बीच कोई क्रम संबंध नहीं है $A.$ (हालांकि, कुछ लेखक एंटीचैन शब्द का उपयोग मजबूत एंटीचैन के लिए करते हैं, एक उपसमुच्चय ऐसा है कि आंशिक रूप से आदेशित सेट का कोई तत्व एंटीचैन के दो अलग-अलग तत्वों से छोटा नहीं है।)

ऊंचाई और चौड़ाई

एक अधिकतम एंटीचैन एक एंटीचैन है जो किसी भी अन्य एंटीचैन का उचित उपसमुच्चय नहीं है। एक अधिकतम एंटीचेन एक एंटीचेन है जिसमें कार्डिनैलिटी कम से कम हर दूसरे एंटीचेन जितनी बड़ी होती है। width}आंशिक रूप से ऑर्डर किए गए सेट का वें एक अधिकतम एंटीचैन की कार्डिनैलिटी है। कोई भी एंटीचैन किसी भी श्रृंखला को अधिकतम एक तत्व में काट सकता है, इसलिए, यदि हम किसी ऑर्डर के तत्वों को विभाजित कर सकते हैं $k$ चेन तो ऑर्डर की चौड़ाई अधिकतम होनी चाहिए $k$ (यदि एंटीचैन से अधिक है $k$ तत्व, कबूतर सिद्धांत द्वारा, इसके 2 तत्व एक ही श्रृंखला से संबंधित होंगे, एक विरोधाभास)। दिलवर्थ के प्रमेय में कहा गया है कि इस सीमा तक हमेशा पहुंचा जा सकता है: हमेशा एक एंटीचैन मौजूद होता है, और तत्वों का जंजीरों में विभाजन होता है, जैसे कि जंजीरों की संख्या एंटीचैन में तत्वों की संख्या के बराबर होती है, जो कि चौड़ाई के बराबर भी होनी चाहिए। इसी प्रकार, कोई परिभाषित कर सकता है height एक श्रृंखला की अधिकतम कार्डिनैलिटी होने के लिए आंशिक क्रम। मिर्स्की के प्रमेय में कहा गया है कि परिमित ऊंचाई के किसी भी आंशिक क्रम में, ऊंचाई कम से कम एंटीचाइन्स के बराबर होती है जिसमें क्रम को विभाजित किया जा सकता है।

स्पर्नर परिवार

एक के सबसेट के समावेशन क्रम में एक एंटीचैन $n$-तत्व सेट को स्पर्नर परिवार के रूप में जाना जाता है। विभिन्न स्पर्नर परिवारों की संख्या की गणना डेडेकिंड संख्याओं द्वारा की जाती है, जिनमें से पहले कुछ संख्याएँ हैं

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (sequence A000372 in the OEIS).

यहां तक ​​कि खाली सेट के पावर सेट में दो एंटीचेन होते हैं: एक में एक सेट होता है (खुद खाली सेट) और एक में कोई सेट नहीं होता है।

शामिल हों और संचालन से मिलें

कोई भी एंटीचैन $A$ कम सेट से मेल खाता है

$$L_{A}=\{x:\exists y\in A{\mbox{ such that }}x\leq y\}.$$

परिमित आंशिक क्रम में (या अधिक आम तौर पर आरोही श्रृंखला की स्थिति को संतुष्ट करने वाला आंशिक क्रम) सभी निचले सेटों में यह रूप होता है। किन्हीं दो निचले सेटों का मिलन एक और निचला सेट है, और यूनियन ऑपरेशन इस तरह से एक जॉइन ऑपरेशन से मेल खाता है एंटीचेन्स पर:

$$A\vee B=\{x\in A\cup B:\nexists y\in A\cup B{\mbox{ such that }}x<y\}.$$

इसी तरह, हम एंटीचेन्स पर मीट ऑपरेशन को परिभाषित कर सकते हैं, जो निचले सेटों के प्रतिच्छेदन के अनुरूप है:

$$A\wedge B=\{x\in L_{A}\cap L_{B}:\nexists y\in L_{A}\cap L_{B}{\mbox{ such that }}x<y\}.$$

एक सेट के परिमित उपसमुच्चय के सभी परिमित एंटीचैन पर शामिल हों और मिलें संचालन $X$ एक वितरणात्मक जाली को परिभाषित करें, जिसके द्वारा उत्पन्न मुक्त वितरणात्मक जाली $X.$ वितरणात्मक जाली के लिए बिरखॉफ के प्रतिनिधित्व प्रमेय में कहा गया है कि प्रत्येक परिमित वितरण जाली को परिमित आंशिक आदेश के एंटीचेन्स पर जुड़ने और मिलने के संचालन के माध्यम से या आंशिक क्रम के निचले सेट पर संघ और चौराहे के संचालन के रूप में प्रदर्शित किया जा सकता है।

कम्प्यूटेशनल जटिलता

बहुपद समय में एक अधिकतम एंटीचेन (और इसका आकार, आंशिक रूप से दिए गए सेट की चौड़ाई) पाया जा सकता है। दिए गए आंशिक रूप से ऑर्डर किए गए सेट में एंटीचेन्स की संख्या की गणना ♯P-पूर्ण|#P-पूर्ण है।

बाहरी संबंध

• Weisstein, Eric W. "Antichain". MathWorld.
• "Antichain". PlanetMath.