एंटीमैट्रोइड: Difference between revisions

[[Image:Antimatroid.svg|thumb|360px|एक एंटीमेट्रोइड के तीन विचार: व्यावहारिक समुच्चयों के अपने समूह पर समावेशन आदेश, औपचारिक भाषा और संबंधित पथ पोसमुच्चय।]]गणित में, '''एंटीमैट्रोइड''' ऐसी [[औपचारिक प्रणाली]] है जो उन प्रक्रियाओं का वर्णन करती है जिसमें समय में तत्व को सम्मिलित करके [[सेट (गणित)|समुच्चय (गणित)]] बनाया जाता है, और जिसमें तत्व के समावेश के लिए उपलब्ध इसके होने तक उपलब्ध समान रूप से रहते हैं।<ref>See {{harvtxt|Korte|Lovász|Schrader|1991}} for a comprehensive survey of antimatroid theory with many additional references.</ref> एंटीमैट्रोइड्स सामान्यतः [[क्रिप्टोमोर्फिज्म]] हैं, या तो ऐसी प्रक्रिया के संभावित स्थितियों को मॉडलिंग करने वाली [[सेट प्रणाली|समुच्चय प्रणाली]] के रूप में, या [[औपचारिक भाषा]] के रूप में विभिन्न अनुक्रमों को मॉडलिंग करते हैं जिसमें तत्व सम्मिलित हो सकते हैं।

रॉबर्ट पी. दिलवर्थ (1940) फिन्टर (आदेश) पर आधारित और स्वसिद्धीकरण का उपयोग करते हुए एंटीमेट्रोइड्स का अध्ययन करने वाले पहले व्यक्ति थे, और इस प्रकार उन्हें प्रायः अन्य संदर्भों में फिर से खोजा गया है।<ref>Two early references are {{harvtxt|Edelman|1980}} and {{harvtxt|Jamison|1980}}; Jamison was the first to use the term "antimatroid". {{harvtxt|Monjardet|1985}} surveys the history of rediscovery of antimatroids.</ref>

एंटीमैट्रोइड्स को समुच्चय सिस्टम के रूप में परिभाषित करने वाले सिद्धांत मैट्रोइड्स के समान माना जाता हैं, किन्तु जबकि को मैट्रोइड स्वतंत्र समुच्चय, बेस और परिपथ द्वारा परिभाषित किया जाता है, इस प्रकार एंटीमैट्रोइड्स को एंटी-एक्सचेंज स्वयंसिद्ध द्वारा परिभाषित किया जाता है, जिससे उनका नाम प्राप्त होता है।

एंटीमैट्रोइड्स [[अर्ध-मॉड्यूलर जाली|अर्ध-मॉड्यूलर फिल्टर]] की विशेष स्थिति के रूप में देखा जा सकता है, और [[आंशिक आदेश|आंशिक आदेशों]] और वितरण संबंधी फिल्टर के सामान्यीकरण के रूप में देखा जा सकता है।

 

एंटीमैट्रोइड्स समतुल्य हैं, पूरक (समुच्चय थ्योरी) द्वारा, 'उत्तल [[ज्यामिति]]' के लिए, ज्यामिति में [[उत्तल सेट|उत्तल समुच्चयों]] का संयोजी रूप हैं।

एक एंटीमैट्रोइड को परिमित समूह <math>\mathcal{F}</math>के रूप में परिभाषित किया जा सकता है , इस प्रकार निम्नलिखित दो गुणों के साथ, परिमित समुच्चय, जिसे व्यावहारिक समुच्चय कहा जाता है:<ref>See e.g. {{harvtxt|Kempner|Levit|2003}}, Definition 2.1 and Proposition 2.3, p. 2.</ref>

* किसी भी दो संभव समुच्चयों का [[संघ (सेट सिद्धांत)|संघ (समुच्चय सिद्धांत)]] भी संभव है। वह <math>\mathcal{F}</math> है जो यूनियनों के अनुसार क्लोजर (गणित) करता है।

* यदि <math>S</math> गैर-रिक्त संभव समुच्चय है, तो <math>S</math> तत्व होता है <math>x</math> जिसके लिए <math>S\setminus\{x\}</math> (हटाने से गठित समुच्चय <math>x</math> से <math>S</math>) भी संभव है। वह <math>\mathcal{F}</math> है जो [[सुलभ सेट प्रणाली|सुलभ समुच्चय प्रणाली]] प्रकट करता हैं।

* वर्णमाला का प्रत्येक प्रतीक <math>\mathcal{L}</math> द्वारा कम से कम शब्द में प्रकट करता है।

* इसका प्रत्येक शब्द <math>\mathcal{L}</math> प्रत्येक प्रतीक की अधिकतम प्रति सम्मिलित है। इस गुण वाली भाषा को सामान्य कहा जाता है।{{sfnp|Korte|Lovász|Schrader|1991|p=5}}

* यदि <math>S</math> और <math>T</math> में शब्द हैं <math>\mathcal{L}</math>, और <math>S</math> कम से कम प्रतीक है जो <math>T</math> के अंदर नहीं है, तो प्रतीक <math>x</math> में <math>S</math> है जो इस प्रकार हैं कि संघ <math>Tx</math> में और शब्द <math>\mathcal{L}</math> है।

परिभाषा के इन दो रूपों की समानता को निम्नानुसार देखा जा सकता है। यदि <math>\mathcal{L}</math> औपचारिक भाषा के रूप में परिभाषित एंटीमेट्रोइड है, फिर शब्दों के प्रतीकों का समुच्चय <math>\mathcal{L}</math> सुलभ संघ-बंद समुच्चय सिस्टम के रूप में बनाया जाता हैं। इस प्रकार यह स्ट्रिंग्स की वंशानुगत संपत्ति द्वारा सुलभ है, और इसे स्ट्रिंग्स के संयोजन गुण के बार-बार उपयोग द्वारा संघ-बंद दिखाया जा सकता है। इस प्रकार दूसरी दिशा में, सुलभ संघ-बंद समुच्चय प्रणाली से <math>\mathcal{F}</math>, सामान्य स्ट्रिंग्स की भाषा जिसके सभी उपसर्गों से संबंधित <math>\mathcal{F}</math> प्रतीकों के समुच्चय होते हैं, औपचारिक भाषा के लिए एंटीमेट्रोइड होने की आवश्यकताओं को पूरा करता है। ये दो परिवर्तन दूसरे के प्रतिलोम हैं: औपचारिक भाषा को निर्धारित समूह में बदलना और इसके विपरीत, ही प्रणाली का निर्माण करता है। इस प्रकार, ये दो परिभाषाएँ गणितीय रूप से वस्तुओं के समतुल्य वर्गों की ओर ले जाती हैं।{{sfnp|Korte|Lovász|Schrader|1991|loc=Theorem 1.4, p. 24}}

[[Image:Convex shelling.svg|thumb|300px|प्लानर पॉइंट समुच्चय का गोलाबारी क्रम में रहते हैं। कुछ बिंदुओं को हटा दिए जाने के बाद रेखा खंड उत्तल पतवार के किनारों को दिखाते हैं।]]निम्नलिखित प्रणालियाँ एंटीमैट्रोइड्स के उदाहरण प्रदान करती हैं:

: एकल स्ट्रिंग के उपसर्ग, और इन उपसर्गों में प्रतीकों के समुच्चय, एंटीमैट्रोइड बनाते हैं। उदाहरण के लिए स्ट्रिंग द्वारा परिभाषित चेन एंटीमैट्रोइड <math>abcd</math> इसकी औपचारिक भाषा के रूप में स्ट्रिंग्स का समुच्चय है <math display=block>\{\varepsilon, a, ab, abc, abcd\}</math> (जहाँ <math>\varepsilon</math> [[खाली स्ट्रिंग|रिक्त स्ट्रिंग]] को दर्शाता है) और जैसा कि संभव है इसका समूह समूह को समुच्चय करता है{{sfnp|Gordon|1997}} <math display=block>\bigl\{\emptyset,\{a\},\{a,b\},\{a,b,c\},\{a,b,c,d\}\bigr\}.</math>

: एक परिमित [[आंशिक रूप से आदेशित सेट|आंशिक रूप से आदेशित समुच्चय]] के निचले समुच्चय एंटीमैट्रोइड बनाते हैं, जिसमें एंटीमैट्रोइड के पूर्ण-लंबाई वाले शब्द आंशिक क्रम के रैखिक एक्सटेंशन बनाते हैं।{{sfnp|Korte|Lovász|Schrader|1991|pp=24–25}} इस प्रकार बिरखॉफ के वितरण प्रमेय द्वारा वितरण फिल्टर के लिए, पॉसमुच्चय एंटीमेट्रॉइड (समुच्चय समावेशन द्वारा आदेशित) में व्यावहारिक समुच्चय वितरण फिल्टर बनाते हैं, और इस प्रकार सभी वितरण फिल्टर इस प्रकार से बन सकते हैं। इस प्रकार, एंटीमैट्रोइड्स को वितरणात्मक लैटिस के सामान्यीकरण के रूप में देखा जा सकता है। इस प्रकार चेन एंटीमैट्रोइड कुल ऑर्डर के लिए पोसमुच्चय एंटीमैट्रोइड का विशेष स्थिति है।{{sfnp|Gordon|1997}}

: परिमित समुच्चय का गोलाबारी क्रम <math>U</math> [[यूक्लिडियन विमान]] या उच्च-आयामी [[यूक्लिडियन अंतरिक्ष]] में बिंदुओं की संख्या उत्तल पतवार के बार-बार हटाने से बनती है। इन अनुक्रमों द्वारा गठित एंटीमेट्रोइड के व्यावहारिक समुच्चय इंटरसेक्शन (समुच्चय सिद्धांत) हैं <math>U</math> उत्तल समुच्चय के पूरक (समुच्चय सिद्धांत) के साथ उपयोग किया जाता हैं।{{sfnp|Gordon|1997}} इस प्रकार प्रत्येक एंटीमैट्रोइड पर्याप्त उच्च-आयामी अंतरिक्ष में बिंदुओं के शेलिंग एंटीमैट्रोइड के लिए आइसोमोर्फिक है।{{sfnp|Kashiwabara|Nakamura|Okamoto|2005}}

: [[कॉर्डल ग्राफ]] का पूर्ण विलोपन क्रम उसके शीर्षों का ऐसा क्रम है, जो प्रत्येक शीर्ष के लिए होता है <math>v</math>, के पड़ोसी <math>v</math> जो बाद में <math>v</math> ऑर्डरिंग फॉर्म में [[ गुट (ग्राफ सिद्धांत) |गुट (ग्राफ सिद्धांत)]] होता है। इस प्रकार कॉर्डल ग्राफ के पूर्ण उन्मूलन क्रम के उपसर्ग एंटीमैट्रोइड बनाते हैं।<ref>{{harvtxt|Gordon|1997}} describes several results related to antimatroids of this type, but these antimatroids were mentioned earlier e.g. by {{harvtxt|Korte|Lovász|Schrader|1991}}. {{harvtxt|Chandran|Ibarra|Ruskey|Sawada|2003}} use the connection to antimatroids as part of an algorithm for efficiently listing all perfect elimination orderings of a given chordal graph.</ref>

[[ चिप फायरिंग का खेल | चिप फायरिंग]]

: चिप-फायरिंग गेम जैसे कि [[एबेलियन सैंडपाइल मॉडल]] को [[निर्देशित ग्राफ]] द्वारा परिभाषित किया जाता है, साथ ही इसके शीर्ष पर चिप्स की प्रणाली होती है। जब भी शीर्ष पर चिप्स की संख्या <math>v</math> कम से कम उतना बड़ा है जितना कि किनारों की संख्या <math>v</math>, फायर करना संभव है, इस प्रकार चिप को प्रत्येक पड़ोसी शीर्ष पर ले जाना संभव रहता हैं। वह घटना जो <math>v</math> के लिए आग <math>i</math>वें समय केवल तभी हो सकता है जब यह पहले से ही निकाल दिया गया हो <math>i-1</math> बार और संचित <math>i\cdot\deg(v)</math> कुल चिप्स पर निर्भर करता हैं। ये स्थितियाँ पिछली फायरिंग के आदेश पर निर्भर नहीं करती हैं, और तब तक सही रहती हैं <math>v</math> आग, इसलिए किसी दिए गए ग्राफ और चिप्स की प्रारंभिक नियुक्ति जिसके लिए सिस्टम समाप्त हो जाता है, इस प्रकार जोड़े पर एंटीमैट्रोइड <math>(v,i)</math> को परिभाषित करता है, इन प्रणालियों की एंटीमैट्रोइड संपत्ति का परिणाम यह है कि, किसी दिए गए प्रारंभिक राज्य के लिए, प्रत्येक वर्टेक्स की आग की संख्या और इस प्रणाली की अंतिम स्थिर स्थिति फायरिंग ऑर्डर पर निर्भर नहीं होती है।<ref>{{harvtxt|Björner|Lovász|Shor|1991}}; {{harvtxt|Knauer|2009}}.</ref>

एक एंटीमैट्रोइड के समुच्चय थ्योरिटिक स्वयंसिद्धीकरण में कुछ विशेष समुच्चय होते हैं जिन्हें पथ कहा जाता है जो पूरे एंटीमैट्रोइड को निर्धारित करते हैं, इस अर्थ में कि एंटीमैट्रोइड के समुच्चय वास्तव में पथों के संघ हैं।{{sfnp|Korte|Lovász|Schrader|1991|loc=Lemma 3.12, p. 31}} यदि <math>S</math> एंटीमैट्रोइड, तत्व का कोई व्यावहारिक समुच्चय है <math>x</math> जिससे <math>S</math> को हटाया जा सकता है और संभव समुच्चय बनाने के लिए समापन बिंदु <math>S</math> को कहा जाता है, और व्यावहारिक समुच्चय जिसमें केवल समापन बिंदु होता है, उसे एंटीमैट्रोइड का पथ कहा जाता है।{{sfnp|Korte|Lovász|Schrader|1991|p=31}} इस प्रकार पथों के समूह को समुच्चय समावेशन द्वारा आंशिक रूप से आदेशित किया जा सकता है, जिससे एंटीमैट्रोइड का पथ पोसमुच्चय बनता है।{{sfnp|Korte|Lovász|Schrader|1991|pp=39–43}}

इस प्रकार संभवतः समुच्चय के लिए <math>S</math> एंटीमैट्रोइड में, और हर तत्व <math>x</math> का <math>S</math>, किसी का पथ उपसमुच्चय मिल सकता है <math>S</math> जिसके लिए <math>x</math> समापन बिंदु है: ऐसा करने के लिए, के अतिरिक्त अन्य तत्वों को समय में <math>x</math> को हटा देते हैं। जब तक ऐसा कोई निष्कासन संभव उपसमुच्चय नहीं छोड़ता हैं। इसलिए एंटीमेट्रोइड में प्रत्येक व्यावहारिक समुच्चय इसके पथ उपसमुच्चय का संघ है।{{sfnp|Korte|Lovász|Schrader|1991|loc=Lemma 3.12, p. 31}} यदि <math>S</math> पथ नहीं है, इस संघ में प्रत्येक उपसमुच्चय का उचित उपसमुच्चय <math>S</math> है, किन्तु यदि <math>S</math> अपने आप में समापन बिंदु वाला पथ <math>x</math> है, जिसका प्रत्येक उचित उपसमुच्चय <math>S</math> जो एंटीमैट्रोइड से संबंधित है, उसमें <math>x</math> का मान सम्मिलित नहीं होता है, इसलिए, एंटीमेट्रोइड के पथ वास्तव में व्यवहारिक समुच्चय हैं जो उनके उचित व्यावहारिक उपसमुच्चय के संघों के बराबर नहीं हैं। इस प्रकार समतुल्य, समुच्चय का दिया गया समूह <math>\mathcal{P}</math> एंटीमैट्रोइड के पथों का समूह बनाता है यदि और केवल यदि, प्रत्येक के लिए <math>S</math> में <math>\mathcal{P}</math>, के उपसमुच्चय का संघ <math>S</math> में <math>\mathcal{P}</math> से कम तत्व है, जो <math>S</math> के लिए अपने आप आ जाता है।<ref>See {{harvtxt|Korte|Lovász|Schrader|1991}}, Theorem 3.13, p. 32, which defines paths as ''rooted sets'', sets with a distinguished element, and states an equivalent characterization on the families of rooted sets that form the paths of antimatroids.</ref> यदि ऐसा है तो, <math>\mathcal{F}</math> ही के उपसमुच्चय के यूनियनों का समूह <math>\mathcal{P}</math> है।{{sfnp|Korte|Lovász|Schrader|1991|loc=Lemma 3.12, p. 31}}

एक एंटीमैट्रोइड की औपचारिक भाषा की औपचारिकता में, सबसे लंबे तार को मूल शब्द कहा जाता है। प्रत्येक मूल शब्द पूरे वर्णमाला का क्रमचय बनाता है।{{sfnp|Korte|Lovász|Schrader|1991|pp=6, 22}} यदि <math>B</math> मूल शब्दों का समूह है, <math>\mathcal{L}</math> से परिभाषित किया जा सकता है <math>B</math> शब्दों के उपसर्गों के समुच्चय <math>B</math> के रूप में निर्भर करता हैं।<ref>See {{harvtxt|Korte|Lovász|Schrader|1991}}, p. 22: "any word in an antimatroid can be extended to a basic word".</ref>

यदि <math>\mathcal{F}</math> एंटीमैट्रोइड को परिभाषित करने वाली समुच्चय प्रणाली है <math>U</math> में समुच्चय के संघ के बराबर <math>\mathcal{F}</math>, फिर समुच्चय का समूह<math display=block>\mathcal{G} = \{U\setminus S\mid S\in \mathcal{F}\}</math>पूरक (समुच्चय सिद्धांत) में समुच्चय करने के लिए <math>\mathcal{F}</math> इसे कभी-कभी उत्तल ज्यामिति कहा जाता है और समुच्चय हो जाता है <math>\mathcal{G}</math> उत्तल समुच्चय कहलाते हैं। उदाहरण के लिए, शेलिंग एंटीमैट्रोइड में, उत्तल समुच्चय यूक्लिडियन अंतरिक्ष के उत्तल उपसमुच्चय के साथ दिए गए बिंदु समुच्चय के अंतः खण्ड हैं। उत्तल ज्यामिति को परिभाषित करने वाली समुच्चय प्रणाली को अंतखण्ड के नीचे बंद किया जाना चाहिए। किसी भी समुच्चय के लिए <math>S</math> में <math>\mathcal{G}</math> वह बराबर नहीं है <math>U</math> तत्व होना चाहिए <math>x</math> अंदर नही <math>S</math> जिसे जोड़ा जा सकता है <math>S</math> और समुच्चय बनाने के लिए <math>\mathcal{G}</math> का उपयोग किया जाता हैं।{{sfnp|Korte|Lovász|Schrader|1991|loc=Theorem 1.1, p. 21}}

एक [[ बंद करने वाला ऑपरेटर |बंद करने वाला ऑपरेटर]] के संदर्भ में उत्तल ज्यामिति <math>\tau</math> को भी परिभाषित किया जा सकता है, जो किसी भी उपसमुच्चय <math>U</math> को मैप करता है , इसके न्यूनतम बंद सुपरसमुच्चय के लिए निर्धारित किया जाता हैं। क्लोजर ऑपरेटर बनने के लिए, <math>\tau</math> निम्नलिखित गुण होने चाहिए:{{sfnp|Korte|Lovász|Schrader|1991|p=20}}

* <math>\tau(\emptyset)=\emptyset</math>: [[खाली सेट|रिक्त समुच्चय]] का क्लोजर रिक्त है।

* प्रत्येक उपसमुच्चय के लिए <math>S</math> का <math>U</math>, <math>S</math> का उपसमुच्चय <math>\tau(S)</math> और <math>\tau(S)=\tau\bigl(\tau(S)\bigr)</math> हैं।

* जब कभी भी <math>S\subset T\subset U</math>, <math>\tau(S)</math> का उपसमुच्चय <math>\tau(T)</math> है।

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

*यदि <math>S</math> का उपसमुच्चय है <math>U</math>, और <math>y</math> और <math>z</math> के विशिष्ट तत्व हैं <math>U</math> जिसका संबंध नहीं है <math>\tau(S)</math>, किन्तु <math>z</math> का है <math>\tau(S\cup\{y\})</math>, तब <math>y</math> का मान <math>\tau(S\cup\{z\})</math> नहीं है।{{sfnp|Korte|Lovász|Schrader|1991|p=20}}

इस स्वयंसिद्ध को संतुष्ट करने वाले क्लोजर ऑपरेशन को एंटी-एक्सचेंज क्लोजर कहा जाता है। यदि <math>S</math> एंटी-एक्सचेंज क्लोजर में बंद समुच्चय है, तो एंटी-एक्सचेंज स्वयंसिद्ध उन तत्वों पर आंशिक क्रम निर्धारित करता है जो इससे संबंधित नहीं हैं <math>S</math>, जहाँ <math>x\le y</math> आंशिक क्रम में जब <math>x</math> से संबंधित <math>\tau(S\cup\{y\})</math> मान के लिए <math>x</math> इस आंशिक क्रम का न्यूनतम तत्व है, तब <math>S\cup\{x\}</math> बन्द रहता है। अर्थात्, एंटी-एक्सचेंज क्लोजर के बंद समुच्चयों के समूह के पास संपत्ति है कि सार्वभौमिक समुच्चय के अतिरिक्त किसी भी समुच्चय के लिए तत्व है <math>x</math> इसे और बंद समुच्चय बनाने के लिए इसमें जोड़ा जा सकता है। यह संपत्ति एंटीमेट्रोइड्स की पहुंच क्षमता की संपत्ति का पूरक है, और तथ्य यह है कि बंद समुच्चयों के अंतः खण्ड बंद हैं संपत्ति के पूरक हैं कि एंटीमैट्रोइड में व्यावहारिक समुच्चयों के संघ संभव हैं। इसलिए, किसी भी एंटी-एक्सचेंज क्लोजर के बंद समुच्चय के पूरक एंटीमैट्रोइड बनाते हैं।{{sfnp|Korte|Lovász|Schrader|1991|loc=Theorem 1.1, p. 21}}

एंटीमैट्रोइड के प्रत्येक दो व्यावहारिक समुच्चयों में अद्वितीय कम से कम ऊपरी बाउंड (उनका संघ) और अद्वितीय सबसे बड़ा निचला बाउंड होता है (एंटीमैट्रोइड में समुच्चय का संघ जो दोनों में निहित होता है)। इसलिए, एंटीमैट्रोइड के व्यावहारिक समुच्चय, समुच्चय समावेशन द्वारा आंशिक क्रम, फिल्टर (आदेश) बनाते हैं। एंटीमैट्रोइड की विभिन्न महत्वपूर्ण विशेषताओं की व्याख्या फिल्टर-सैद्धांतिक शब्दों में की जा सकती है; उदाहरण के लिए एंटीमैट्रोइड के पथ फिल्टर (क्रम) #महत्वपूर्ण फिल्टर-सैद्धांतिक धारणाएं हैं। संबंधित फिल्टर के सम्मिलित-अप्रासंगिक तत्व हैं, और एंटीमैट्रोइड के मूल शब्द फिल्टर में [[अधिकतम श्रृंखला|अधिकतम श्रृंखलाओं]] के अनुरूप रहता हैं। इस प्रकार एंटीमैट्रोइड्स से उत्पन्न होने वाली फिल्टर, परिमित वितरण संबंधी फिल्टर को सामान्य करती है, और इसे कई अलग-अलग तरीकों से चित्रित किया जा सकता है।