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

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{Short description|Mathematical system of orderings or sets}}
{{Short description|Mathematical system of orderings or sets}}
[[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> Antimatroids आमतौर पर [[क्रिप्टोमोर्फिज्म]] हैं, या तो ऐसी प्रक्रिया के संभावित राज्यों को मॉडलिंग करने वाली [[सेट प्रणाली]] के रूप में, या [[औपचारिक भाषा]] के रूप में विभिन्न अनुक्रमों को मॉडलिंग करते हैं जिसमें तत्व शामिल हो सकते हैं।
[[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>
रॉबर्ट पी. दिलवर्थ (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>


एंटीमैट्रोइड्स को सेट सिस्टम के रूप में परिभाषित करने वाले सिद्धांत मैट्रोइड्स के समान हैं, लेकिन जबकि मैट्रोइड्स को मैट्रोइड # स्वतंत्र सेट, बेस और सर्किट द्वारा परिभाषित किया जाता है, एंटीमैट्रोइड्स को एंटी-एक्सचेंज स्वयंसिद्ध द्वारा परिभाषित किया जाता है, जिससे उनका नाम प्राप्त होता है।
एंटीमैट्रोइड्स को समुच्चय सिस्टम के रूप में परिभाषित करने वाले सिद्धांत मैट्रोइड्स के समान हैं, किन्तु जबकि मैट्रोइड्स को मैट्रोइड # स्वतंत्र समुच्चय, बेस और सर्किट द्वारा परिभाषित किया जाता है, एंटीमैट्रोइड्स को एंटी-एक्सचेंज स्वयंसिद्ध द्वारा परिभाषित किया जाता है, जिससे उनका नाम प्राप्त होता है।
Anti[[matroid]]s [[लालची]] और [[अर्ध-मॉड्यूलर जाली]] के विशेष मामले के रूप में देखा जा सकता है, और [[आंशिक आदेश]]ों और वितरण संबंधी जाली के सामान्यीकरण के रूप में देखा जा सकता है।
 
एंटीमैट्रोइड्स समतुल्य हैं, पूरक (सेट थ्योरी) द्वारा, 'उत्तल [[ज्यामिति]]' के लिए, ज्यामिति में [[उत्तल सेट]]ों का संयोजी अमूर्त।
एंटीमैट्रोइड्स [[लालची]] और [[अर्ध-मॉड्यूलर जाली]] के विशेष स्थिति के रूप में देखा जा सकता है, और [[आंशिक आदेश]]ों और वितरण संबंधी जाली के सामान्यीकरण के रूप में देखा जा सकता है।
एंटीमैट्रोइड्स समतुल्य हैं, पूरक (समुच्चय थ्योरी) द्वारा, 'उत्तल [[ज्यामिति]]' के लिए, ज्यामिति में [[उत्तल सेट|उत्तल समुच्चय]]ों का संयोजी अमूर्त।


[[जॉब शॉप शेड्यूलिंग]], सिमुलेशन में संभावित घटना क्रम, [[ कृत्रिम होशियारी |कृत्रिम होशियारी]] में टास्क प्लानिंग और मानव शिक्षार्थियों के ज्ञान की अवस्थाओं में मॉडल पूर्ववर्ती बाधाओं के लिए एंटीमैट्रोइड्स लागू किए गए हैं।
[[जॉब शॉप शेड्यूलिंग]], सिमुलेशन में संभावित घटना क्रम, [[ कृत्रिम होशियारी |कृत्रिम होशियारी]] में टास्क प्लानिंग और मानव शिक्षार्थियों के ज्ञान की अवस्थाओं में मॉडल पूर्ववर्ती बाधाओं के लिए एंटीमैट्रोइड्स लागू किए गए हैं।


== परिभाषाएँ ==
== परिभाषाएँ ==
एक एंटीमैट्रोइड को परिमित परिवार के रूप में परिभाषित किया जा सकता है <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> निम्नलिखित दो गुणों के साथ, परिमित समुच्चय, जिसे व्यवहार्य समुच्चय कहा जाता है:<ref>See e.g. {{harvtxt|Kempner|Levit|2003}}, Definition 2.1 and Proposition 2.3, p. 2.</ref>
* किसी भी दो संभव सेटों का [[संघ (सेट सिद्धांत)]] भी संभव है। वह है, <math>\mathcal{F}</math> यूनियनों के तहत क्लोजर (गणित) है।
* किसी भी दो संभव समुच्चयों का [[संघ (सेट सिद्धांत)|संघ (समुच्चय सिद्धांत)]] भी संभव है। वह है, <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>S</math> गैर-खाली संभव समुच्चय है, तो <math>S</math> तत्व होता है <math>x</math> जिसके लिए <math>S\setminus\{x\}</math> (हटाने से गठित समुच्चय <math>x</math> से <math>S</math>) भी संभव है। वह है, <math>\mathcal{F}</math> [[सुलभ सेट प्रणाली|सुलभ समुच्चय प्रणाली]] है।


Antimatroids की औपचारिक भाषा के रूप में समकक्ष परिभाषा भी है, जो कि [[स्ट्रिंग (कंप्यूटर विज्ञान)]] के सेट के रूप में [[प्रतीक]]ों के परिमित वर्णमाला से परिभाषित है। इस समुच्चय से संबंधित स्ट्रिंग को भाषा का शब्द कहा जाता है। भाषा <math>\mathcal{L}</math> एंटीमैट्रोइड को परिभाषित करने से निम्नलिखित गुणों को पूरा करना चाहिए:{{sfnp|Korte|Lovász|Schrader|1991|p=22}}
एंटीमैट्रोइड्स की औपचारिक भाषा के रूप में समकक्ष परिभाषा भी है, जो कि [[स्ट्रिंग (कंप्यूटर विज्ञान)]] के समुच्चय के रूप में [[प्रतीक]]ों के परिमित वर्णमाला से परिभाषित है। इस समुच्चय से संबंधित स्ट्रिंग को भाषा का शब्द कहा जाता है। भाषा <math>\mathcal{L}</math> एंटीमैट्रोइड को परिभाषित करने से निम्नलिखित गुणों को पूरा करना चाहिए:{{sfnp|Korte|Lovász|Schrader|1991|p=22}}
* वर्णमाला का प्रत्येक प्रतीक कम से कम शब्द में आता है <math>\mathcal{L}</math>.
* वर्णमाला का प्रत्येक प्रतीक कम से कम शब्द में आता है <math>\mathcal{L}</math>.
* का प्रत्येक शब्द <math>\mathcal{L}</math> प्रत्येक प्रतीक की अधिकतम प्रति शामिल है। इस गुण वाली भाषा को सामान्य कहा जाता है।{{sfnp|Korte|Lovász|Schrader|1991|p=5}}
* का प्रत्येक शब्द <math>\mathcal{L}</math> प्रत्येक प्रतीक की अधिकतम प्रति सम्मिलित है। इस गुण वाली भाषा को सामान्य कहा जाता है।{{sfnp|Korte|Lovász|Schrader|1991|p=5}}
* प्रत्येक [[उपसर्ग (कंप्यूटर विज्ञान)]] शब्द में <math>\mathcal{L}</math> में भी है <math>\mathcal{L}</math>. इस संपत्ति वाली भाषा को वंशानुगत कहा जाता है।{{sfnp|Korte|Lovász|Schrader|1991|p=5}}
* प्रत्येक [[उपसर्ग (कंप्यूटर विज्ञान)]] शब्द में <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>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}}
परिभाषा के इन दो रूपों की समानता को निम्नानुसार देखा जा सकता है। यदि <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|प्लानर पॉइंट सेट का गोलाबारी क्रम। कुछ बिंदुओं को हटा दिए जाने के बाद रेखा खंड उत्तल पतवार के किनारों को दिखाते हैं।]]निम्नलिखित प्रणालियाँ एंटीमैट्रोइड्स के उदाहरण प्रदान करती हैं:
[[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>
: एकल स्ट्रिंग के उपसर्ग, और इन उपसर्गों में प्रतीकों के समुच्चय, एंटीमैट्रोइड बनाते हैं। उदाहरण के लिए स्ट्रिंग द्वारा परिभाषित चेन एंटीमैट्रोइड <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}}
: एक परिमित [[आंशिक रूप से आदेशित सेट|आंशिक रूप से आदेशित समुच्चय]] के निचले समुच्चय एंटीमैट्रोइड बनाते हैं, जिसमें एंटीमैट्रोइड के पूर्ण-लंबाई वाले शब्द आंशिक क्रम के रैखिक एक्सटेंशन बनाते हैं।{{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>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> ऑर्डरिंग फॉर्म में [[ गुट (ग्राफ सिद्धांत) |गुट (ग्राफ सिद्धांत)]] । कॉर्डल ग्राफ के पूर्ण उन्मूलन क्रम के उपसर्ग एंटीमैट्रोइड बनाते हैं।<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>
Line 36: Line 37:
: चिप-फायरिंग गेम जैसे कि [[एबेलियन सैंडपाइल मॉडल]] को [[निर्देशित ग्राफ]] द्वारा परिभाषित किया जाता है, साथ ही इसके शीर्ष पर चिप्स की प्रणाली होती है। जब भी शीर्ष पर चिप्स की संख्या <math>v</math> कम से कम उतना बड़ा है जितना कि किनारों की संख्या <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>
: चिप-फायरिंग गेम जैसे कि [[एबेलियन सैंडपाइल मॉडल]] को [[निर्देशित ग्राफ]] द्वारा परिभाषित किया जाता है, साथ ही इसके शीर्ष पर चिप्स की प्रणाली होती है। जब भी शीर्ष पर चिप्स की संख्या <math>v</math> कम से कम उतना बड़ा है जितना कि किनारों की संख्या <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}}
एक एंटीमैट्रोइड के समुच्चय थ्योरिटिक स्वयंसिद्धीकरण में कुछ विशेष समुच्चय होते हैं जिन्हें पथ कहा जाता है जो पूरे एंटीमैट्रोइड को निर्धारित करते हैं, इस अर्थ में कि एंटीमैट्रोइड के समुच्चय वास्तव में पथों के संघ हैं।{{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>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>
एक एंटीमैट्रोइड की औपचारिक भाषा की औपचारिकता में, सबसे लंबे तार को मूल शब्द कहा जाता है। प्रत्येक मूल शब्द पूरे वर्णमाला का क्रमचय बनाता है।{{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>
== उत्तल ज्यामिति ==
== उत्तल ज्यामिति ==
{{See also|Convex set|Convex geometry|Closure operator}}
{{See also|उत्तल सेट|उत्तल ज्यामिति|क्लोजर ऑपरेटर}}
अगर <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>\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</math> जो किसी भी सबसमुच्चय को मैप करता है <math>U</math> इसके न्यूनतम बंद सुपरसमुच्चय के लिए। क्लोजर ऑपरेटर बनने के लिए, <math>\tau</math> निम्नलिखित गुण होने चाहिए:{{sfnp|Korte|Lovász|Schrader|1991|p=20}}
* <math>\tau(\emptyset)=\emptyset</math>: [[खाली सेट]] का क्लोजर खाली है।
* <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</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\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>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}}
इस स्वयंसिद्ध को संतुष्ट करने वाले क्लोजर ऑपरेशन को एंटी-एक्सचेंज क्लोजर कहा जाता है। यदि <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}}


अप्रत्यक्ष रेखांकन जिसमें उत्तल सेट (उपसमुच्चय के उपसमुच्चय जिसमें उपसमुच्चय में कोने के बीच सभी सबसे छोटे रास्ते होते हैं) उत्तल ज्यामिति बनाते हैं, बिल्कुल टॉलेमिक रेखांकन होते हैं।{{sfnp|Farber|Jamison|1986}}
अप्रत्यक्ष रेखांकन जिसमें उत्तल समुच्चय (उपसमुच्चय के उपसमुच्चय जिसमें उपसमुच्चय में कोने के बीच सभी सबसे छोटे रास्ते होते हैं) उत्तल ज्यामिति बनाते हैं, बिल्कुल टॉलेमिक रेखांकन होते हैं।{{sfnp|Farber|Jamison|1986}}


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


* विवरण मूल रूप से माना जाता है {{harvtxt|Dilworth|1940}} चिंता जाली (आदेश)#महत्वपूर्ण जाली-सैद्धांतिक धारणा| प्रत्येक तत्व के लिए <math>x</math> एंटीमैट्रोइड का, अद्वितीय अधिकतम संभव सेट मौजूद है <math>S_x</math> जिसमें शामिल नहीं है <math>x</math>: <math>S_x</math> सम्‍मिलित नहीं सभी संभव सेटों के संघ के रूप में निर्मित किया जा सकता है <math>x</math>. यह सेट <math>S_x</math> स्वचालित रूप से मिलने-अपूरणीय है, जिसका अर्थ है कि यह किसी भी दो बड़े जाली तत्वों का मिलन नहीं है। यह सच है क्योंकि का हर संभव सुपरसेट <math>S_x</math> रोकना <math>x</math>, और इसलिए यह संभव सुपरसेट के हर चौराहे के बारे में भी सच है। मनमाना जाली के प्रत्येक तत्व को मीट-इरिड्यूसिबल सेट के मिलन के रूप में विघटित किया जा सकता है, अक्सर कई तरीकों से, लेकिन जाली में प्रत्येक तत्व एंटीमैट्रोइड के अनुरूप होता है। <math>T</math> मीट-इरिड्यूसिबल सेट का अनूठा न्यूनतम परिवार है जिसका मिलन है <math>T</math>; इस परिवार में सेट शामिल हैं <math>S_x</math> तत्वों के लिए <math>x</math> ऐसा है कि <math>T\cup\{x\}</math> व्यवहार्य है। अर्थात्, जाली में अद्वितीय मिल-इरेड्यूसबल अपघटन होते हैं।
* विवरण मूल रूप से माना जाता है {{harvtxt|दिलवर्थ|1940}} चिंता जाली (आदेश)#महत्वपूर्ण जाली-सैद्धांतिक धारणा| प्रत्येक तत्व के लिए <math>x</math> एंटीमैट्रोइड का, अद्वितीय अधिकतम संभव समुच्चय सम्मिलित है <math>S_x</math> जिसमें सम्मिलित नहीं है <math>x</math>: <math>S_x</math> सम्‍मिलित नहीं सभी संभव समुच्चयों के संघ के रूप में निर्मित किया जा सकता है <math>x</math>. यह समुच्चय <math>S_x</math> स्वचालित रूप से मिलने-अपूरणीय है, जिसका अर्थ है कि यह किसी भी दो बड़े जाली तत्वों का मिलन नहीं है। यह सच है क्योंकि का हर संभव सुपरसमुच्चय <math>S_x</math> रोकना <math>x</math>, और इसलिए यह संभव सुपरसमुच्चय के हर चौराहे के बारे में भी सच है। मनमाना जाली के प्रत्येक तत्व को मीट-इरिड्यूसिबल समुच्चय के मिलन के रूप में विघटित कि