ज्यामितीय जाली: Difference between revisions
No edit summary |
|||
| Line 3: | Line 3: | ||
== परिभाषा == | == परिभाषा == | ||
जाली (आदेश) [[आंशिक रूप से आदेशित सेट|आंशिक रूप से आदेशित समूह]] है जिसमें कोई भी दो तत्व होते हैं जैसे <math>x</math> और <math>y</math> दोनों में कम से कम ऊपरी सीमा होती है, जिसे संयोजित या [[ अंतिम |अंतिम]] कहा जाता है अतः जिसे <math>x\vee y</math> द्वारा निरूपित किया जाता है और सबसे बड़ी निचली सीमा, जिसे मिलना या | जाली (आदेश) [[आंशिक रूप से आदेशित सेट|आंशिक रूप से आदेशित समूह]] है जिसमें कोई भी दो तत्व होते हैं जैसे <math>x</math> और <math>y</math> दोनों में कम से कम ऊपरी सीमा होती है, जिसे संयोजित या [[ अंतिम |अंतिम]] कहा जाता है अतः जिसे <math>x\vee y</math> द्वारा निरूपित किया जाता है और सबसे बड़ी निचली सीमा, जिसे मिलना या सबसे कम कहा जाता है, इसे <math>x\wedge y</math> द्वारा दर्शाया जाता है। | ||
: निम्नलिखित परिभाषाएं सामान्यतः [[आंशिक रूप से आदेशित सेट|आंशिक रूप से आदेशित समूह]] पर प्रयुक्त होती हैं, केवल जाली नहीं, इसके अतिरिक्त कि जहां अन्यथा कहा गया होता है। | : निम्नलिखित परिभाषाएं सामान्यतः [[आंशिक रूप से आदेशित सेट|आंशिक रूप से आदेशित समूह]] पर प्रयुक्त होती हैं, केवल जाली नहीं, इसके अतिरिक्त कि जहां अन्यथा कहा गया होता है। | ||
* [[न्यूनतम तत्व]] के लिए <math>x</math>, कोई तत्व नहीं है <math>y</math> ऐसा है कि <math>y < x</math>. | * [[न्यूनतम तत्व]] के लिए <math>x</math>, कोई तत्व नहीं है <math>y</math> ऐसा है कि <math>y < x</math>. | ||
| Line 9: | Line 9: | ||
* न्यूनतम तत्व के आवरण को परमाणु (आदेश सिद्धांत) कहा जाता है। | * न्यूनतम तत्व के आवरण को परमाणु (आदेश सिद्धांत) कहा जाता है। | ||
* जाली [[परमाणुवादी (आदेश सिद्धांत)]] है यदि प्रत्येक तत्व परमाणुओं के कुछ समूह का सर्वोच्च है। | * जाली [[परमाणुवादी (आदेश सिद्धांत)]] है यदि प्रत्येक तत्व परमाणुओं के कुछ समूह का सर्वोच्च है। | ||
* पोसेट को तब श्रेणीकृत कहा जाता है जब उसे श्रेणी | * पोसेट को तब श्रेणीकृत कहा जाता है जब उसे श्रेणी फलन दिया जा सकता है <math>r(x)</math> इसके तत्वों को पूर्णांकों में मानचित्र जाता है, जैसे कि <math>r(x)>r(y)</math> जब कभी भी <math>x>y</math>, और भी <math>r(x)=r(y)+1</math> जब कभी भी <math>x :> y</math>. | ||
: जब वर्गीकृत पोसेट में निचला तत्व होता है, तब सामान्यता के हानि के बिना यह मान सकता है कि इसकी श्रेणी शून्य है। इस स्थिति में, परमाणु श्रेणी वाले तत्व हैं। | : जब वर्गीकृत पोसेट में निचला तत्व होता है, तब सामान्यता के हानि के बिना यह मान सकता है कि इसकी श्रेणी शून्य है। इस स्थिति में, परमाणु श्रेणी वाले तत्व हैं। | ||
* प्रत्येक के लिए श्रेणीबद्ध जाली अर्ध-मॉड्यूलर होता है, यदि <math>x</math> और <math>y</math>, इसके श्रेणी | * प्रत्येक के लिए श्रेणीबद्ध जाली अर्ध-मॉड्यूलर होता है, यदि <math>x</math> और <math>y</math>, इसके श्रेणी फलन पहचान का पालन करता है।<ref>{{harvtxt|Birkhoff|1995}}, Theorem 15, p. 40. More precisely, Birkhoff's definition reads "We shall call P (upper) semimodular when it satisfies: If ''a''≠''b'' both cover ''c'', then there exists a ''d''∈''P'' which covers both ''a'' and ''b''" (p.39). Theorem 15 states: "A graded lattice of finite length is semimodular if and only if ''r''(''x'')+''r''(''y'')≥''r''(''x''∧''y'')+''r''(''x''∨''y'')".</ref> | ||
:: <math>r(x)+r(y)\ge r(x\wedge y)+r(x\vee y). \, </math> | :: <math>r(x)+r(y)\ge r(x\wedge y)+r(x\vee y). \, </math> | ||
* मैट्रोइड जाली वह जाली है जो परमाणु और अर्ध-मॉड्यूलर दोनों है।<ref>{{citation | * मैट्रोइड जाली वह जाली है जो परमाणु और अर्ध-मॉड्यूलर दोनों है।<ref>{{citation | ||
| Line 32: | Line 32: | ||
ज्यामितीय जाली (परिमित, सरल) मैट्रोइड के समान्तर हैं और मैट्रोइड जाली परिमितता की धारणा के बिना सरल मैट्रोइड के समान्तर हैं (अनंत मैट्रोइड की उचित परिभाषा के अनुसार; ऐसी अनेक परिभाषाएं हैं)। पत्राचार यह है कि मैट्रोइड के तत्व जाली के परमाणु हैं और जाली का तत्व x मैट्रोइड के फ्लैट से मेल खाता है जिसमें मैट्रोइड के वह तत्व होते हैं जो परमाणु <math>a \leq x.</math> होते हैं। | ज्यामितीय जाली (परिमित, सरल) मैट्रोइड के समान्तर हैं और मैट्रोइड जाली परिमितता की धारणा के बिना सरल मैट्रोइड के समान्तर हैं (अनंत मैट्रोइड की उचित परिभाषा के अनुसार; ऐसी अनेक परिभाषाएं हैं)। पत्राचार यह है कि मैट्रोइड के तत्व जाली के परमाणु हैं और जाली का तत्व x मैट्रोइड के फ्लैट से मेल खाता है जिसमें मैट्रोइड के वह तत्व होते हैं जो परमाणु <math>a \leq x.</math> होते हैं। | ||
ज्यामितीय जाली की भांति, मैट्रोइड को | ज्यामितीय जाली की भांति, मैट्रोइड को मैट्रोइड श्रेणी के साथ संपन्न किया जाता है, किन्तु यह फलन मेट्रॉइड तत्वों के समूह को जाली तत्व को इसके तर्क के रूप में लेने के अतिरिक्त संख्या में मैप करता है। इस प्रकार मैट्रोइड का श्रेणी फलन मोनोटोनिक होना चाहिए (समूह में तत्व जोड़ने से इसकी श्रेणी कभी कम नहीं हो सकती है) और यह सबमॉड्यूलर फलन होता है। जिसका अर्थ है कि यह अर्ध-मॉड्यूलर श्रेणी वाले जाली के समान असमानता का पालन करता है। | ||
:<math>r(X)+r(Y)\ge r(X\cap Y)+r(X\cup Y)</math> | :<math>r(X)+r(Y)\ge r(X\cap Y)+r(X\cup Y)</math> | ||
मैट्रोइड तत्वों के X और Y समूह के लिए किसी दिए गए श्रेणी के | मैट्रोइड तत्वों के X और Y समूह के लिए किसी दिए गए श्रेणी के अधिकतम तत्व समूह को 'फ्लैट्स' कहा जाता है। दो फ्लैटों का चौराहा फिर से फ्लैट है, जो फ्लैटों के जोड़े पर सबसे बड़ी निचली बाध्य क्रिया को परिभाषित करता है। चूँकि कोई भी फ्लैटों की जोड़ी के कम से कम ऊपरी बाउंड को उनके संघ के (अद्वितीय) अधिकतम समूहों के रूप में परिभाषित कर सकता है जिसमें उनके संघ के समान श्रेणी है। इस प्रकार मैट्रोइड के फ्लैट मैट्रोइड जाली बनाते हैं या (यदि मैट्रोइड परिमित है) ज्यामितीय जाली बनाते है।<ref name="w10-51" /> | ||
इसके विपरीत यदि <math>L</math> मैट्रोइड जाली है, कोई भी अपने परमाणुओं के समूह पर श्रेणी | इसके विपरीत यदि <math>L</math> मैट्रोइड जाली है, कोई भी अपने परमाणुओं के समूह पर श्रेणी फलन को परिभाषित कर सकता है, परमाणुओं के समूह के श्रेणी को समूह के सबसे बड़े निचले बाउंड के जाली श्रेणी के रूप में परिभाषित कर सकता है। यह श्रेणी फलन आवश्यक रूप से मोनोटोनिक और सबमॉड्यूलर है, इसलिए यह मैट्रोइड को परिभाषित करता है। यह मैट्रोइड आवश्यक रूप से सरल है, जिसका अर्थ है कि प्रत्येक दो-तत्व समूह में श्रेणी दो है।<ref name="w10-51" /> | ||
यह दो निर्माण, जाली से साधारण मैट्रोइड और मैट्रोइड से जाली के, दूसरे के विपरीत होते हैं। इस प्रकार ज्यामितीय जाली या साधारण मैट्रोइड से प्रारंभ होकर और बाद के दोनों निर्माण करते हुए जाली या मैट्रोइड देता है, जो मूल के लिए आइसोमोर्फिक है।<ref name="w10-51" /> | यह दो निर्माण, जाली से साधारण मैट्रोइड और मैट्रोइड से जाली के, दूसरे के विपरीत होते हैं। इस प्रकार ज्यामितीय जाली या साधारण मैट्रोइड से प्रारंभ होकर और बाद के दोनों निर्माण करते हुए जाली या मैट्रोइड देता है, जो मूल के लिए आइसोमोर्फिक है।<ref name="w10-51" /> | ||
Revision as of 12:51, 3 May 2023
मैट्रोइड और जाली (आदेश) गणित में, ज्यामितीय जाली परिमित सेट परमाणु (आदेश सिद्धांत) अर्ध-मॉड्यूलर जाली है और मैट्रोइड जाली परिमितता की धारणा के बिना परमाणु अर्ध-मॉड्यूलर जाली है। इस प्रकार ज्यामितीय जाली और मैट्रोइड जाली, क्रमशः परिमित और अनंत मैट्रोइड के फ्लैटों की जाली बनाते हैं और प्रत्येक ज्यामितीय या मैट्रोइड जाली इस प्रकार से मैट्रोइड से आती है।
परिभाषा
जाली (आदेश) आंशिक रूप से आदेशित समूह है जिसमें कोई भी दो तत्व होते हैं जैसे और दोनों में कम से कम ऊपरी सीमा होती है, जिसे संयोजित या अंतिम कहा जाता है अतः जिसे द्वारा निरूपित किया जाता है और सबसे बड़ी निचली सीमा, जिसे मिलना या सबसे कम कहा जाता है, इसे द्वारा दर्शाया जाता है।
- निम्नलिखित परिभाषाएं सामान्यतः आंशिक रूप से आदेशित समूह पर प्रयुक्त होती हैं, केवल जाली नहीं, इसके अतिरिक्त कि जहां अन्यथा कहा गया होता है।
- न्यूनतम तत्व के लिए , कोई तत्व नहीं है ऐसा है कि .
- तत्व अन्य तत्व को सम्मिलित करता है (के रूप में लिखा गया है या ) यदि और कोई तत्व नहीं है तब दोनों से भिन्न होता है और जिससे कि .
- न्यूनतम तत्व के आवरण को परमाणु (आदेश सिद्धांत) कहा जाता है।
- जाली परमाणुवादी (आदेश सिद्धांत) है यदि प्रत्येक तत्व परमाणुओं के कुछ समूह का सर्वोच्च है।
- पोसेट को तब श्रेणीकृत कहा जाता है जब उसे श्रेणी फलन दिया जा सकता है इसके तत्वों को पूर्णांकों में मानचित्र जाता है, जैसे कि जब कभी भी , और भी जब कभी भी .
- जब वर्गीकृत पोसेट में निचला तत्व होता है, तब सामान्यता के हानि के बिना यह मान सकता है कि इसकी श्रेणी शून्य है। इस स्थिति में, परमाणु श्रेणी वाले तत्व हैं।
- प्रत्येक के लिए श्रेणीबद्ध जाली अर्ध-मॉड्यूलर होता है, यदि और , इसके श्रेणी फलन पहचान का पालन करता है।[1]
- मैट्रोइड जाली वह जाली है जो परमाणु और अर्ध-मॉड्यूलर दोनों है।[2][3] ज्यामितीय जाली परिमित मैट्रोइड जाली है।[4]
- सामान्यतः अनेक लेखक केवल परिमित मैट्रोइड जाली पर विचार करते हैं और दोनों के लिए "ज्यामितीय जाली" और "मैट्रोइड जाली" शब्दों का उपयोग करते हैं।[5]
जाली बनाम मैट्रोइड्स
ज्यामितीय जाली (परिमित, सरल) मैट्रोइड के समान्तर हैं और मैट्रोइड जाली परिमितता की धारणा के बिना सरल मैट्रोइड के समान्तर हैं (अनंत मैट्रोइड की उचित परिभाषा के अनुसार; ऐसी अनेक परिभाषाएं हैं)। पत्राचार यह है कि मैट्रोइड के तत्व जाली के परमाणु हैं और जाली का तत्व x मैट्रोइड के फ्लैट से मेल खाता है जिसमें मैट्रोइड के वह तत्व होते हैं जो परमाणु होते हैं।
ज्यामितीय जाली की भांति, मैट्रोइड को मैट्रोइड श्रेणी के साथ संपन्न किया जाता है, किन्तु यह फलन मेट्रॉइड तत्वों के समूह को जाली तत्व को इसके तर्क के रूप में लेने के अतिरिक्त संख्या में मैप करता है। इस प्रकार मैट्रोइड का श्रेणी फलन मोनोटोनिक होना चाहिए (समूह में तत्व जोड़ने से इसकी श्रेणी कभी कम नहीं हो सकती है) और यह सबमॉड्यूलर फलन होता है। जिसका अर्थ है कि यह अर्ध-मॉड्यूलर श्रेणी वाले जाली के समान असमानता का पालन करता है।
मैट्रोइड तत्वों के X और Y समूह के लिए किसी दिए गए श्रेणी के अधिकतम तत्व समूह को 'फ्लैट्स' कहा जाता है। दो फ्लैटों का चौराहा फिर से फ्लैट है, जो फ्लैटों के जोड़े पर सबसे बड़ी निचली बाध्य क्रिया को परिभाषित करता है। चूँकि कोई भी फ्लैटों की जोड़ी के कम से कम ऊपरी बाउंड को उनके संघ के (अद्वितीय) अधिकतम समूहों के रूप में परिभाषित कर सकता है जिसमें उनके संघ के समान श्रेणी है। इस प्रकार मैट्रोइड के फ्लैट मैट्रोइड जाली बनाते हैं या (यदि मैट्रोइड परिमित है) ज्यामितीय जाली बनाते है।[4]
इसके विपरीत यदि मैट्रोइड जाली है, कोई भी अपने परमाणुओं के समूह पर श्रेणी फलन को परिभाषित कर सकता है, परमाणुओं के समूह के श्रेणी को समूह के सबसे बड़े निचले बाउंड के जाली श्रेणी के रूप में परिभाषित कर सकता है। यह श्रेणी फलन आवश्यक रूप से मोनोटोनिक और सबमॉड्यूलर है, इसलिए यह मैट्रोइड को परिभाषित करता है। यह मैट्रोइड आवश्यक रूप से सरल है, जिसका अर्थ है कि प्रत्येक दो-तत्व समूह में श्रेणी दो है।[4]
यह दो निर्माण, जाली से साधारण मैट्रोइड और मैट्रोइड से जाली के, दूसरे के विपरीत होते हैं। इस प्रकार ज्यामितीय जाली या साधारण मैट्रोइड से प्रारंभ होकर और बाद के दोनों निर्माण करते हुए जाली या मैट्रोइड देता है, जो मूल के लिए आइसोमोर्फिक है।[4]
द्वैत
ज्यामितीय जाली के लिए द्वैत की दो भिन्न-भिन्न प्राकृतिक धारणाएँ हैं ।
- : दोहरी मैट्रोइड, जिसका आधार इसके अनुरूप मैट्रोइड के आधार के पूरक (समूह सिद्धांत) समूह करता है।
- और द्वैत (आदेश सिद्धांत), वह जाली जिसमें समान तत्व होते हैं।
- विपरीत क्रम में। वह समान नहीं हैं और वास्तव में दोहरी जाली सामान्यतः ज्यामितीय जाली नहीं होती है अतः परमाणु होने की संपत्ति विपरीत-क्रम द्वारा संरक्षित नहीं होती है। इस प्रकार चेउंग (1974) ज्यामितीय जाली के आसन्न को परिभाषित करता है।
- (या इससे परिभाषित मैट्रोइड) न्यूनतम ज्यामितीय जाली है जिसमें दोहरी जाली है।
- ऑर्डर-एम्बेडेड है। अतः कुछ मैट्रोइड्स में संलग्नक नहीं होते हैं; उदाहरण के लिए, वामोस मैट्रोइड है।[6]
अतिरिक्त गुण
ज्यामितीय जाली का प्रत्येक अंतराल (दिए गए निचले और ऊपरी बाध्य तत्वों के मध्य जाली का समूह) स्वयं ज्यामितीय है। इस प्रकार ज्यामितीय जाली का अंतराल लेना संबंधित मैट्रोइड के माथेरॉइड माइनर बनाने के अनुरूप है। ज्यामितीय जाली जाली के पूरक हैं और अंतराल संपत्ति के कारण वे अपेक्षाकृत पूरक भी हैं।[7]
प्रत्येक परिमित जाली ज्यामितीय जाली का उप-वर्ग है।[8]
संदर्भ
- ↑ Birkhoff (1995), Theorem 15, p. 40. More precisely, Birkhoff's definition reads "We shall call P (upper) semimodular when it satisfies: If a≠b both cover c, then there exists a d∈P which covers both a and b" (p.39). Theorem 15 states: "A graded lattice of finite length is semimodular if and only if r(x)+r(y)≥r(x∧y)+r(x∨y)".
- ↑ Maeda, F.; Maeda, S. (1970), Theory of Symmetric Lattices, Die Grundlehren der mathematischen Wissenschaften, Band 173, New York: Springer-Verlag, MR 0282889.
- ↑ Welsh, D. J. A. (2010), Matroid Theory, Courier Dover Publications, p. 388, ISBN 9780486474397.
- ↑ 4.0 4.1 4.2 4.3 Welsh (2010), p. 51.
- ↑ Birkhoff, Garrett (1995), Lattice Theory, Colloquium Publications, vol. 25 (3rd ed.), American Mathematical Society, p. 80, ISBN 9780821810255.
- ↑ Cheung, Alan L. C. (1974), "Adjoints of a geometry", Canadian Mathematical Bulletin, 17 (3): 363–365, correction, ibid. 17 (1974), no. 4, 623, doi:10.4153/CMB-1974-066-5, MR 0373976.
- ↑ Welsh (2010), pp. 55, 65–67.
- ↑ Welsh (2010), p. 58; Welsh credits this result to Robert P. Dilworth, who proved it in 1941–1942, but does not give a specific citation for its original proof.
