एंटीमैट्रोइड: 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> एंटीमैट्रोइड्स सामान्यतः [[क्रिप्टोमोर्फिज्म]] हैं, या तो ऐसी प्रक्रिया के संभावित स्थितियों को मॉडलिंग करने वाली [[सेट प्रणाली|समुच्चय प्रणाली]] के रूप में, या [[औपचारिक भाषा]] के रूप में विभिन्न अनुक्रमों को मॉडलिंग करते हैं जिसमें तत्व सम्मिलित हो सकते हैं।

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

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

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

* यदि <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> एंटीमैट्रोइड को परिभाषित करने से निम्नलिखित गुणों को पूरा करना चाहिए:{{sfnp|Korte|Lovász|Schrader|1991|p=22}}

परिभाषा के इन दो रूपों की समानता को निम्नानुसार देखा जा सकता है। यदि <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}}

: चिप-फायरिंग गेम जैसे कि [[एबेलियन सैंडपाइल मॉडल]] को [[निर्देशित ग्राफ]] द्वारा परिभाषित किया जाता है, साथ ही इसके शीर्ष पर चिप्स की प्रणाली होती है। जब भी शीर्ष पर चिप्स की संख्या <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}}

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

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

* एक दूसरा लक्षण वर्णन फिल्टर में अंतरालों की चिंता करता है, फिल्टर तत्वों की जोड़ी द्वारा परिभाषित उप-वर्ग <math>x\le y</math> सभी फिल्टर तत्वों से मिलकर <math>z</math> साथ <math>x\le z\le y</math>. अंतराल [[परमाणु (आदेश सिद्धांत)]] है यदि इसमें प्रत्येक तत्व परमाणुओं का जुड़ाव है (नीचे के तत्व के ऊपर न्यूनतम तत्व <math>x</math>), और यह [[बूलियन बीजगणित (संरचना)]] है यदि यह परिमित समुच्चय के [[ सत्ता स्थापित |सत्ता स्थापित]] के फिल्टर के लिए आइसोमोर्फिक है। एंटीमैट्रोइड के लिए, प्रत्येक अंतराल जो कि परमाणुवादी है, बूलियन भी है।

ये तीन विशेषताएँ समतुल्य हैं: अद्वितीय मिल-इरेड्यूसिबल अपघटन के साथ किसी भी फिल्टर में बूलियन परमाणु अंतराल होता है और इसमें सम्मिलित-वितरण होता है, बूलियन परमाणु अंतराल के साथ किसी भी फिल्टर में अद्वितीय मिल-इरेड्यूसिबल अपघटन होता है और यह वितरण-वितरण होता है, किसी भी जोड़-वितरण फिल्टर में अद्वितीय होता है मीट-इरेड्यूसिबल अपघटन और बूलियन परमाणु अंतराल।<ref>{{harvtxt|Adaricheva|Gorbunov|Tumanov|2003}}, Theorems 1.7 and 1.9; {{harvtxt|Armstrong|2009}}, Theorem 2.7.</ref> इस प्रकार, हम इन तीन गुणों में से किसी के साथ फिल्टर को जोड़-वितरण के रूप में संदर्भित कर सकते हैं। कोई भी एंटीमैट्रोइड परिमित जॉइन-डिस्ट्रीब्यूटिव फिल्टर को जन्म देता है, और कोई भी परिमित जॉइन-डिस्ट्रीब्यूटिव लैटिस इस तरह से एंटीमैट्रोइड से आता है।<ref>{{harvtxt|Edelman|1980}}, Theorem 3.3; {{harvtxt|Armstrong|2009}}, Theorem 2.8.</ref> इस प्रकार परिमित ज्वाइन-डिस्ट्रीब्यूटिव लैटिस का और समकक्ष लक्षण वर्णन यह है कि वे [[ वर्गीकृत पोसेट |वर्गीकृत पोसमुच्चय]] हैं (किसी भी दो अधिकतम श्रृंखलाओं की लंबाई समान है), और अधिकतम श्रृंखला की लंबाई फिल्टर के मिल-इरेड्यूसबल तत्वों की संख्या के बराबर होती है।<ref>{{harvtxt|Monjardet|1985}} credits a dual form of this characterization to several papers from the 1960s by S. P. Avann.</ref> परिमित जोड़-वितरण फिल्टर का प्रतिनिधित्व करने वाले एंटीमैट्रोइड को फिल्टर से पुनर्प्राप्त किया जा सकता है: एंटीमैट्रॉइड के तत्वों को फिल्टर के मीट-इरिड्यूसिबल तत्वों और किसी भी तत्व के अनुरूप व्यावहारिक समुच्चय के रूप में लिया जा सकता है। <math>x</math> फिल्टर में मिलने-इरेड्यूसबल तत्वों का समुच्चय होता है <math>y</math> ऐसा है कि <math>y</math> से अधिक या बराबर नहीं है <math>x</math> फिल्टर में प्रयोग किया जाता हैं।

[[कॉक्सेटर समूह|कॉक्समुच्चयर समूह]] के तत्वों पर आंशिक आदेशों को परिभाषित करने की समस्या से प्रेरित होकर, {{harvtxt|आर्मस्ट्रांग|2009}} ने एंटीमैट्रोइड्स का अध्ययन किया जो सुपरसॉल्वेबल लैटिस भी हैं। सुपरसॉल्वेबल एंटीमैट्रोइड को तत्वों के कुल ऑर्डर संग्रह और इन तत्वों के समुच्चय के समूह द्वारा परिभाषित किया गया है। समूह को रिक्त समुच्चय सम्मिलित करना चाहिए। इसके अतिरिक्त, इसमें संपत्ति होनी चाहिए कि यदि दो समुच्चय हो <math>A</math> और <math>B</math> समूह से संबंधित हैं, यदि [[सेट-सैद्धांतिक अंतर|समुच्चय-सैद्धांतिक अंतर]] <math>B\setminus A</math> रिक्त नहीं है, और यदि <math>x</math> का सबसे छोटा तत्व है <math>B\setminus A</math>, तब <math>A\cup\{x\}</math> समूह का भी है। जैसा कि आर्मस्ट्रांग ने देखा है, इस प्रकार के समुच्चयों का कोई भी समूह एंटीमैट्रोइड बनाता है। आर्मस्ट्रांग एंटीमैट्रोइड्स का फिल्टर-सैद्धांतिक लक्षण वर्णन भी प्रदान करता है जो यह निर्माण बना सकता है।{{sfnp|Armstrong|2009}}

यदि <math>\mathcal{A}</math> और <math>\mathcal{B}</math> दो एंटीमैट्रोइड्स हैं, दोनों को तत्वों के ही ब्रह्मांड पर समुच्चय के समूह के रूप में वर्णित किया गया है, फिर और एंटीमैट्रोइड, का जुड़ाव <math>\mathcal{A}</math> और <math>\mathcal{B}</math>, इस प्रकार बनाया जा सकता है:<math display=block>\mathcal{A}\vee\mathcal{B} = \{ S\cup T \mid S\in\mathcal{A}\wedge T\in\mathcal{B}\}.</math>यह एंटीमैट्रोइड्स के फिल्टर-सैद्धांतिक लक्षण वर्णन में सम्मिलित होने की तुलना में अलग ऑपरेशन है: यह दो एंटीमैट्रोइड्स को और एंटीमैट्रोइड बनाने के लिए जोड़ता ह