ज्यामितीय जाली: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Join-meet algebra on matroid flats}} | {{Short description|Join-meet algebra on matroid flats}} | ||
[[matroid|मेटारोइड]] और [[जाली | [[matroid|मेटारोइड]] और [[जाली (आदेश)]] गणित में, '''ज्यामितीय जाली''' [[परिमित सेट]] परमाणु (आदेश सिद्धांत) [[अर्ध-मॉड्यूलर जाली]] है और मेटारोइड जाली परिमितता की धारणा के बिना परमाणु अर्ध-मॉड्यूलर जाली है। इस प्रकार जियोमेट्रिक जाली और मैट्रोइड जाली, क्रमशः परिमित और अनंत मेटारोइड के फ्लैटों के जाली बनाते हैं और प्रत्येक ज्यामितीय या मेटारोइड जाली इस प्रकार से मेटारोइड से आती है। | ||
== परिभाषा == | == परिभाषा == | ||
जाली (आदेश) [[आंशिक रूप से आदेशित सेट|आंशिक रूप से आदेशित समूह]] है जिसमें कोई भी दो तत्व होते हैं <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>. | ||
* तत्व <math>x</math> अन्य तत्व को | * तत्व <math>x</math> अन्य तत्व को सम्मिलित करता है <math>y</math> (के रूप में लिखा गया है <math>x :> y</math> या <math> y <: x</math>) यदि <math>x > y</math> और कोई तत्व नहीं है तब <math>z</math> दोनों से भिन्न होता है <math>x</math> और <math>y</math> जिससे कि <math>x > z > y</math>. | ||
* न्यूनतम तत्व के आवरण को परमाणु (आदेश सिद्धांत) कहा जाता है। | * न्यूनतम तत्व के आवरण को परमाणु (आदेश सिद्धांत) कहा जाता है। | ||
* | * जाली [[परमाणुवादी (आदेश सिद्धांत)]] है यदि प्रत्येक तत्व परमाणुओं के कुछ समूह का सर्वोच्च है। | ||
* पोसेट को | * पोसेट को तब श्रेणीकृत कहा जाता है जब उसे रैंक फ़ंक्शन दिया जा सकता है <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>, इसका रैंक फ़ंक्शन पहचान का पालन करता है।<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 | ||
| last1 = Maeda | first1 = F. | | last1 = Maeda | first1 = F. | ||
| last2 = Maeda | first2 = S. | | last2 = Maeda | first2 = S. | ||
| Line 27: | Line 27: | ||
| publisher = Courier Dover Publications | | publisher = Courier Dover Publications | ||
| title = Matroid Theory | | title = Matroid Theory | ||
| year = 2010}}.</ref> ज्यामितीय | | year = 2010}}.</ref> ज्यामितीय जाली परिमित मैट्रॉइड जाली है।<ref name="w10-51">{{harvtxt|Welsh|2010}}, p. 51.</ref> | ||
: | : सामान्यतः अनेक लेखक केवल परिमित मैट्रॉइड जाली पर विचार करते हैं और दोनों के लिए "ज्यामितीय जाली" और "मैट्रोइड जाली" शब्दों का उपयोग करते हैं।<ref>{{citation|title=Lattice Theory|volume=25|series=Colloquium Publications|publisher=American Mathematical Society|first=Garrett|last=Birkhoff|authorlink=Garrett Birkhoff|edition=3rd|year=1995|isbn=9780821810255|page=80|url=https://books.google.com/books?id=0Y8d-MdtVwkC&pg=PA80}}.</ref> | ||
== जाली बनाम मैट्रोइड्स == | |||
ज्यामितीय जाली (परिमित, सरल) मेटारोइड के समान्तर हैं, और मेटारोइड lattices परिमितता की धारणा के बिना सरल मेटारोइड के समान्तर हैं (अनंत मेटारोइड की उचित परिभाषा के अनुसार; ऐसी अनेक परिभाषाएं हैं)। पत्राचार यह है कि मैट्रॉइड के तत्व जाली के परमाणु हैं और जाली का तत्व 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 सेट के लिए। | |||
किसी दिए गए रैंक के [[अधिकतम तत्व]] सेट को 'फ्लैट्स' कहा जाता है। दो फ्लैटों का चौराहा फिर से फ्लैट है, जो फ्लैटों के जोड़े पर सबसे बड़ी निचली बाध्य कार्रवाई को परिभाषित करता है; कोई भी फ्लैटों की जोड़ी के कम से कम ऊपरी बाउंड को उनके संघ के (अद्वितीय) अधिकतम सुपरसेट के रूप में परिभाषित कर सकता है जिसमें उनके संघ के समान रैंक है। इस तरह, मैट्रॉइड के फ्लैट मैट्रोइड | किसी दिए गए रैंक के [[अधिकतम तत्व]] सेट को 'फ्लैट्स' कहा जाता है। दो फ्लैटों का चौराहा फिर से फ्लैट है, जो फ्लैटों के जोड़े पर सबसे बड़ी निचली बाध्य कार्रवाई को परिभाषित करता है; कोई भी फ्लैटों की जोड़ी के कम से कम ऊपरी बाउंड को उनके संघ के (अद्वितीय) अधिकतम सुपरसेट के रूप में परिभाषित कर सकता है जिसमें उनके संघ के समान रैंक है। इस तरह, मैट्रॉइड के फ्लैट मैट्रोइड जाली बनाते हैं, या (यदि मैट्रॉइड परिमित है) ज्यामितीय जाली।<ref name="w10-51"/> | ||
इसके विपरीत यदि <math>L</math> मैट्रॉइड | इसके विपरीत यदि <math>L</math> मैट्रॉइड जाली है, कोई भी अपने परमाणुओं के सेट पर रैंक फ़ंक्शन को परिभाषित कर सकता है, परमाणुओं के सेट के रैंक को सेट के सबसे बड़े निचले बाउंड के जाली रैंक के रूप में परिभाषित कर सकता है। यह रैंक फ़ंक्शन आवश्यक रूप से मोनोटोनिक और सबमॉड्यूलर है, इसलिए यह मैट्रॉइड को परिभाषित करता है। यह मैट्रॉइड आवश्यक रूप से सरल है, जिसका अर्थ है कि प्रत्येक दो-तत्व सेट में रैंक दो है।<ref name="w10-51"/> | ||
ये दो निर्माण, | ये दो निर्माण, जाली से साधारण मैट्रॉइड और मैट्रॉइड से जाली के, दूसरे के विपरीत होते हैं: ज्यामितीय जाली या साधारण मैट्रॉइड से प्रारंभ होकर, और के बाद दोनों निर्माण करते हुए, जाली या मैट्रॉइड देता है मूल के लिए आइसोमोर्फिक है।<ref name="w10-51"/> | ||
== द्वैत == | == द्वैत == | ||
ज्यामितीय | ज्यामितीय जाली के लिए द्वैत की दो अलग-अलग प्राकृतिक धारणाएँ हैं <math>L</math>: दोहरी मेटारोइड, जो इसके आधार के आधार पर मेटारोइड के आधार के [[पूरक (सेट सिद्धांत)]] सेट करता है <math>L</math>, और [[द्वैत (आदेश सिद्धांत)]], वह जाली जिसमें समान तत्व होते हैं <math>L</math> विपरीत क्रम में। वे समान नहीं हैं, और वास्तव में दोहरी जाली सामान्यतः ज्यामितीय जाली नहीं होती है: परमाणु होने की संपत्ति ऑर्डर-रिवर्सल द्वारा संरक्षित नहीं होती है। {{harvtxt|Cheung|1974}} ज्यामितीय जाली के आसन्न को परिभाषित करता है <math>L</math> (या इससे परिभाषित मैट्रॉइड) न्यूनतम ज्यामितीय जाली है जिसमें दोहरी जाली है <math>L</math> [[ आदेश एम्बेडिंग |आदेश एम्बेडिंग]] है|ऑर्डर-एम्बेडेड। कुछ मैट्रोइड्स में संलग्नक नहीं होते हैं; उदाहरण वामोस मैट्रोइड है।<ref>{{citation | ||
| last = Cheung | first = Alan L. C. | | last = Cheung | first = Alan L. C. | ||
| doi = 10.4153/CMB-1974-066-5 | doi-access=free | | doi = 10.4153/CMB-1974-066-5 | doi-access=free | ||
| Line 58: | Line 56: | ||
== अतिरिक्त गुण == | == अतिरिक्त गुण == | ||
ज्यामितीय | ज्यामितीय जाली का प्रत्येक अंतराल (दिए गए निचले और ऊपरी बाध्य तत्वों के मध्य जाली का सबसेट) स्वयं ज्यामितीय है; ज्यामितीय जाली का अंतराल लेना संबंधित मैट्रोइड के [[ माथेरॉइड माइनर |माथेरॉइड माइनर]] बनाने के अनुरूप है। ज्यामितीय जाली जाली के पूरक हैं, और अंतराल संपत्ति के कारण वे अपेक्षाकृत पूरक भी हैं।<ref>{{harvtxt|Welsh|2010}}, pp. 55, 65–67.</ref> | ||
प्रत्येक परिमित | प्रत्येक परिमित जाली ज्यामितीय जाली का उप-वर्ग है।<ref>{{harvtxt|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.</ref> | ||
Revision as of 13:45, 2 May 2023
मेटारोइड और जाली (आदेश) गणित में, ज्यामितीय जाली परिमित सेट परमाणु (आदेश सिद्धांत) अर्ध-मॉड्यूलर जाली है और मेटारोइड जाली परिमितता की धारणा के बिना परमाणु अर्ध-मॉड्यूलर जाली है। इस प्रकार जियोमेट्रिक जाली और मैट्रोइड जाली, क्रमशः परिमित और अनंत मेटारोइड के फ्लैटों के जाली बनाते हैं और प्रत्येक ज्यामितीय या मेटारोइड जाली इस प्रकार से मेटारोइड से आती है।
परिभाषा
जाली (आदेश) आंशिक रूप से आदेशित समूह है जिसमें कोई भी दो तत्व होते हैं और दोनों में कम से कम ऊपरी सीमा होती है, जिसे ज्वाइन या अंतिम कहा जाता है अतः जिसे द्वारा निरूपित किया जाता है और सबसे बड़ी निचली सीमा, जिसे मिलना या सबसे कम कहा जाता है, इसे द्वारा दर्शाया जाता है।
- निम्नलिखित परिभाषाएं सामान्यतः आंशिक रूप से आदेशित समूह पर प्रयुक्त होती हैं, केवल जाली नहीं, अतिरिक्त इसके कि जहां अन्यथा कहा गया होता है।
- न्यूनतम तत्व के लिए , कोई तत्व नहीं है ऐसा है कि .
- तत्व अन्य तत्व को सम्मिलित करता है (के रूप में लिखा गया है या ) यदि और कोई तत्व नहीं है तब दोनों से भिन्न होता है और जिससे कि .
- न्यूनतम तत्व के आवरण को परमाणु (आदेश सिद्धांत) कहा जाता है।
- जाली परमाणुवादी (आदेश सिद्धांत) है यदि प्रत्येक तत्व परमाणुओं के कुछ समूह का सर्वोच्च है।
- पोसेट को तब श्रेणीकृत कहा जाता है जब उसे रैंक फ़ंक्शन दिया जा सकता है इसके तत्वों को पूर्णांकों में मानचित्र जाता है, जैसे कि जब कभी भी , और भी जब कभी भी .
- जब वर्गीकृत पोसेट में निचला तत्व होता है, तब सामान्यता के हानि के बिना यह मान सकता है कि इसकी रैंक शून्य है। इस स्थिति में, परमाणु रैंक वाले तत्व हैं।
- प्रत्येक के लिए श्रेणीबद्ध जाली अर्ध-मॉड्यूलर होता है, यदि और , इसका रैंक फ़ंक्शन पहचान का पालन करता है।[1]
- मैट्रॉइड जाली वह जाली है जो परमाणु और अर्ध-मॉड्यूलर दोनों है।[2][3] ज्यामितीय जाली परिमित मैट्रॉइड जाली है।[4]
- सामान्यतः अनेक लेखक केवल परिमित मैट्रॉइड जाली पर विचार करते हैं और दोनों के लिए "ज्यामितीय जाली" और "मैट्रोइड जाली" शब्दों का उपयोग करते हैं।[5]
जाली बनाम मैट्रोइड्स
ज्यामितीय जाली (परिमित, सरल) मेटारोइड के समान्तर हैं, और मेटारोइड lattices परिमितता की धारणा के बिना सरल मेटारोइड के समान्तर हैं (अनंत मेटारोइड की उचित परिभाषा के अनुसार; ऐसी अनेक परिभाषाएं हैं)। पत्राचार यह है कि मैट्रॉइड के तत्व जाली के परमाणु हैं और जाली का तत्व x मैट्रॉइड के फ्लैट से मेल खाता है जिसमें मैट्रॉइड के वे तत्व होते हैं जो परमाणु होते हैं ज्यामितीय जाली की तरह, मैट्रॉइड को मैट्रोइड रैंक के साथ संपन्न किया जाता है, किन्तु यह फ़ंक्शन मेट्रॉइड तत्वों के सेट को जाली तत्व को इसके तर्क के रूप में लेने के अतिरिक्त संख्या में मैप करता है। मैट्रॉइड का रैंक फ़ंक्शन मोनोटोनिक होना चाहिए (सेट में तत्व जोड़ने से इसकी रैंक कभी कम नहीं हो सकती है) और यह सबमॉड्यूलर फ़ंक्शन होना चाहिए, जिसका अर्थ है कि यह सेमीमॉड्यूलर रैंक वाले जाली के समान असमानता का पालन करता है:
मेटारोइड तत्वों के X और Y सेट के लिए। किसी दिए गए रैंक के अधिकतम तत्व सेट को 'फ्लैट्स' कहा जाता है। दो फ्लैटों का चौराहा फिर से फ्लैट है, जो फ्लैटों के जोड़े पर सबसे बड़ी निचली बाध्य कार्रवाई को परिभाषित करता है; कोई भी फ्लैटों की जोड़ी के कम से कम ऊपरी बाउंड को उनके संघ के (अद्वितीय) अधिकतम सुपरसेट के रूप में परिभाषित कर सकता है जिसमें उनके संघ के समान रैंक है। इस तरह, मैट्रॉइड के फ्लैट मैट्रोइड जाली बनाते हैं, या (यदि मैट्रॉइड परिमित है) ज्यामितीय जाली।[4]
इसके विपरीत यदि मैट्रॉइड जाली है, कोई भी अपने परमाणुओं के सेट पर रैंक फ़ंक्शन को परिभाषित कर सकता है, परमाणुओं के सेट के रैंक को सेट के सबसे बड़े निचले बाउंड के जाली रैंक के रूप में परिभाषित कर सकता है। यह रैंक फ़ंक्शन आवश्यक रूप से मोनोटोनिक और सबमॉड्यूलर है, इसलिए यह मैट्रॉइड को परिभाषित करता है। यह मैट्रॉइड आवश्यक रूप से सरल है, जिसका अर्थ है कि प्रत्येक दो-तत्व सेट में रैंक दो है।[4]
ये दो निर्माण, जाली से साधारण मैट्रॉइड और मैट्रॉइड से जाली के, दूसरे के विपरीत होते हैं: ज्यामितीय जाली या साधारण मैट्रॉइड से प्रारंभ होकर, और के बाद दोनों निर्माण करते हुए, जाली या मैट्रॉइड देता है मूल के लिए आइसोमोर्फिक है।[4]
द्वैत
ज्यामितीय जाली के लिए द्वैत की दो अलग-अलग प्राकृतिक धारणाएँ हैं : दोहरी मेटारोइड, जो इसके आधार के आधार पर मेटारोइड के आधार के पूरक (सेट सिद्धांत) सेट करता है , और द्वैत (आदेश सिद्धांत), वह जाली जिसमें समान तत्व होते हैं विपरीत क्रम में। वे समान नहीं हैं, और वास्तव में दोहरी जाली सामान्यतः ज्यामितीय जाली नहीं होती है: परमाणु होने की संपत्ति ऑर्डर-रिवर्सल द्वारा संरक्षित नहीं होती है। Cheung (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.
