तंग अवधि
मीट्रिक ज्यामिति में, मीट्रिक स्थान M का मीट्रिक लिफ़ाफ़ा या टाइट स्पान एक इंजेक्शन मीट्रिक स्थान है जिसमें M एम्बेड किया जा सकता है। कुछ अर्थों में इसमें एम के बिंदुओं के बीच के सभी बिंदु होते हैं, जो यूक्लिडियन अंतरिक्ष में स्थापित बिंदु के उत्तल हल के समान होते हैं। टाइट स्पान को कभी-कभी 'M' के इंजेक्शन एनवेलप या हाइपरकोनवेक्स हल के रूप में भी जाना जाता है। इसे इंजेक्शन पतवार भी कहा जाता है, लेकिन बीजगणित में एक मॉड्यूल (गणित) के इंजेक्शन हल के साथ भ्रमित नहीं होना चाहिए, एक अवधारणा जिसमें 'आर'-मॉड्यूल की श्रेणी (गणित) के सापेक्ष समान विवरण होता है मीट्रिक रिक्त स्थान।
तंग अवधि का वर्णन सबसे पहले किसके द्वारा किया गया था Isbell (1964), और 1960 के दशक में W. Holsztyński|Holsztyński द्वारा इसका अध्ययन और प्रयोग किया गया था। इसे बाद में द्वारा स्वतंत्र रूप से फिर से खोजा गया Dress (1984) और Chrobak & Larmore (1994); देखना Chepoi (1997) इस इतिहास के लिए। तंग अवधि टी-सिद्धांत के केंद्रीय निर्माणों में से एक है।
परिभाषा
एक मीट्रिक स्थान की तंग अवधि को निम्नानुसार परिभाषित किया जा सकता है। चलो (एक्स, डी) एक मीट्रिक स्थान बनें, और टी (एक्स) एक्स पर 'चरम कार्यों' का सेट बनें, जहां हम एक्स पर 'एक्सट्रीमल फ़ंक्शन' कहते हैं, जिसका मतलब एक्स से 'आर' तक एक फ़ंक्शन एफ है वह
- किसी भी एक्स के लिए, एक्स में वाई, डी (एक्स, वाई) ≤ एफ (एक्स) + एफ (वाई), और
- X में प्रत्येक x के लिए, f(x) = sup{d(x,y) - f(y):y in X}.[1]: 124
विशेष रूप से (ऊपर संपत्ति 1 में x = y लेने पर) सभी x के लिए f(x) ≥ 0। ऊपर दी गई पहली आवश्यकता की व्याख्या करने का एक तरीका यह है कि f कुछ नए बिंदु से X के बिंदुओं तक संभावित दूरी के एक सेट को परिभाषित करता है जो कि (X, d) में दूरियों के साथ त्रिकोण असमानता को पूरा करना चाहिए। दूसरी आवश्यकता बताती है कि त्रिभुज असमानता का उल्लंघन किए बिना इनमें से किसी भी दूरी को कम नहीं किया जा सकता है।
(एक्स, डी) का 'टाइट स्पैन' मीट्रिक स्पेस (टी (एक्स), δ) है, जहां
चरम कार्यों की समतुल्य परिभाषाएँ
एक्स से 'आर' तक एक फ़ंक्शन एफ के लिए पहली आवश्यकता को पूरा करने के लिए, दूसरी आवश्यकता के निम्नलिखित संस्करण समतुल्य हैं:
- X में प्रत्येक x के लिए, f(x) = sup{d(x,y) - f(y):y in X}.
- f उपरोक्त पहली आवश्यकता के संबंध में बिंदुवार न्यूनतम है, अर्थात, X से 'R' तक किसी भी फ़ंक्शन g के लिए ऐसा है कि d(x,y) ≤ g(x) + g(y) सभी x,y in X के लिए , अगर g≤f बिन्दुवार, तो f=g.[2]: 93, Proposition 4.6.2 [Note 1][Note 2][3]: Lemma 5.1
- एक्स = ∅ या एक्स में मौजूद है जैसे एक्स में सभी एक्स के लिए, एफ (एक्स) ≤ डी (ए, एक्स)।[4]
मूल गुण और उदाहरण
- एक्स में सभी एक्स के लिए,
- एक्स में प्रत्येक एक्स के लिए, अतिवादी है। (सबूत: समरूपता और त्रिभुज असमानता#मेट्रिक स्पेस का उपयोग करें।)[Note 3]
- यदि X परिमित है, तो X से 'R' तक किसी भी फ़ंक्शन f के लिए जो पहली आवश्यकता को पूरा करता है, दूसरी आवश्यकता इस शर्त के बराबर है कि X में प्रत्येक x के लिए, X में y मौजूद है जैसे कि f(x) + एफ (वाई) = डी (एक्स, वाई)। (अगर तो दोनों स्थितियाँ सत्य हैं। अगर तब श्रेष्ठता प्राप्त की जाती है, और पहली आवश्यकता का तात्पर्य समानता से है।)
- कहें |X|=2, और विशिष्ट ए, बी चुनें जैसे कि एक्स={ए,बी}। तब का उत्तल पतवार है{{(a,1),(b,0)},{(a,0),(b,1)}}. [तस्वीर जोड़ें। कैप्शन: यदि एक्स = {0,1}, तो {(0,1),(1,0)} का उत्तल पतवार है।][5]: 124
- X पर प्रत्येक चरम कार्य f कातेतोव है:[6][7]: Section 2 f पहली आवश्यकता को पूरा करता है और या समकक्ष, f पहली आवश्यकता को पूरा करता है और (1-लिप्सचिट्ज़ निरंतरता है), या समकक्ष, f पहली आवश्यकता को संतुष्ट करता है और [2]: Proof of Proposition 4.6.1 [Note 4]
- T(X)⊆कॉम्पैक्ट हॉउसडॉर्फ स्पेस#सामान्यीकरण|C(X) पर निरंतर कार्य। (लिप्सचिट्ज़ कार्य निरंतर हैं।)
- टी (एक्स) समान है। (X के 1-लिप्सचिट्ज़ होने पर प्रत्येक चरम कार्य से अनुसरण करता है; cf. इक्विकंटिन्यूटी # उदाहरण।)
- X पर प्रत्येक केटोव कार्य चरम नहीं है। उदाहरण के लिए, ए, बी को अलग होने दें, एक्स = {ए, बी}, डी = ([x≠y]) देंx,y in X एक्स पर असतत मीट्रिक बनें, और f = {(ए, 1), (बी, 2)} दें। फिर एफ कातेतोव है लेकिन चरम नहीं है। (यह लगभग तत्काल है कि f कटेटोव है। f चरम नहीं है क्योंकि यह इस खंड की तीसरी बुलेट में संपत्ति को विफल करता है।)
- यदि d परिबद्ध है, तो T(X) में प्रत्येक f परिबद्ध है। वास्तव में, T(X) में प्रत्येक f के लिए, (टिप्पणी ) (उपर्युक्त खंड में तीसरे समकक्ष संपत्ति से अनुसरण करता है।)
- यदि d अपरिबद्ध है, तो T(X) में प्रत्येक f अपरिबद्ध है। (पहली आवश्यकता से अनुसरण करता है।)
- बिंदुवार सीमा के तहत बंद है। किसी भी बिंदुवार अभिसरण के लिए
- अगर (एक्स, डी) कॉम्पैक्ट है, तो (टी (एक्स), δ) कॉम्पैक्ट है।[8][2]: Proposition 4.6.3 (सबूत: एक्सट्रीम वैल्यू थ्योरम#मैट्रिक और टोपोलॉजिकल स्पेस का सामान्यीकरण|एक्सट्रीम-वैल्यू प्रमेय का मतलब है कि डी, एक फंक्शन के रूप में निरंतर होना घिरा हुआ है, इसलिए (पिछली गोली देखें) C(X) का परिबद्ध उपसमुच्चय है। हमने दिखाया है कि टी (एक्स) समान है, इसलिए अर्जेला-एस्कोली प्रमेय का अर्थ है कि टी (एक्स) अपेक्षाकृत कॉम्पैक्ट है। हालाँकि, पिछली बुलेट का तात्पर्य T(X) के तहत बंद है मानदंड, चूंकि अभिसरण का अर्थ बिंदुवार अभिसरण है। इस प्रकार टी (एक्स) कॉम्पैक्ट है।)
- X से 'R' तक के किसी भी फ़ंक्शन g के लिए जो पहली आवश्यकता को पूरा करता है, T(X) में f मौजूद है जैसे कि f≤g बिंदुवार।[2]: Lemma 4.4
- एक्स पर किसी भी चरम समारोह एफ के लिए, [2]: Proposition 4.6.1 [Note 5]
- T(X) में किसी भी f,g के लिए अंतर से संबंधित , यानी, बंधा हुआ है। (उपरोक्त गोली का प्रयोग करें।)
- कुराटोव्स्की मानचित्र[5]: 125 एक आइसोमेट्री है। (जब X=∅, परिणाम स्पष्ट होता है। जब X≠∅, विपरीत त्रिकोण असमानता का अर्थ परिणाम होता है।)
- मान लीजिए कि T(X) में f है। X में किसी a के लिए, यदि f(a)=0, तो f=e(a).[3]: Lemma 5.1 (एक्स में प्रत्येक एक्स के लिए हमारे पास है एफ की न्यूनतमता (उपरोक्त खंड में दूसरा समकक्ष लक्षण वर्णन) और तथ्य यह है कि इसके बाद की पहली आवश्यकता को पूरा करता है )
- (X,d) अतिशयोक्तिपूर्ण मीट्रिक स्थान है यदि और केवल यदि (T(X),δ) अतिशयोक्तिपूर्ण है।[3]: Theorem 5.3
हाइपरकोन्वेक्सिटी गुण
- (टी(एक्स),δ) और दोनों इंजेक्शन मेट्रिक स्पेस हैं।[2]: Proposition 4.7.1
- किसी भी वाई के लिए ऐसा है अतिउत्तल नहीं है।[2]: Proposition 4.7.2 ((टी (एक्स), δ) (एक्स, डी) का एक अतिउत्तल पतवार है।)
- होने देना के साथ एक अतिउत्तल मीट्रिक स्थान हो और . अगर सभी के लिए मैं साथ तब अतिउत्तल नहीं है और (टी(एक्स),δ) आइसोमेट्री#आइसोमेट्री परिभाषा हैं।[2]: Proposition 4.7.1 ((एक्स, डी) का प्रत्येक हाइपरकॉन्वेक्स हल (टी (एक्स), δ) के साथ आइसोमेट्रिक है।)
उदाहरण
- कहें |X|=3, विशिष्ट a, b, c चुनें जैसे कि X={a,b,c}, और मान लीजिए i=d(a,b), j=d(a,c), k=d (बी, सी)। तब कहाँ [तस्वीर जोड़ें। कैप्शन: अगर X={0,1,2}, तो T(X)=conv{(,,),(,,)} u conv{(,,),(,,)} u conv{(,, ),(,,)} अक्षर Y के आकार का है] (Cf. [5]: 124 )
यदि विमान में बिंदुओं का एक सेट, टैक्सीकैब ज्यामिति के साथ, एक जुड़ा हुआ ऑर्थोगोनल उत्तल पतवार है, तो वह पतवार बिंदुओं की तंग अवधि के साथ मेल खाता है।* आंकड़ा विमान में 16 बिंदुओं का एक सेट एक्स दिखाता है; इन बिंदुओं से एक परिमित मीट्रिक स्थान बनाने के लिए, हम मैनहट्टन दूरी का उपयोग करते हैं (ℓ1 दूरी)।[9] आकृति में दिखाया गया नीला क्षेत्र ऑर्थोगोनल उत्तल पतवार है, बिंदु z का सेट ऐसा है कि शीर्ष के रूप में z के साथ चार बंद चतुर्भुजों में से प्रत्येक में X का एक बिंदु होता है। ऐसा कोई भी बिंदु z तंग अवधि के बिंदु से मेल खाता है: फलन f(x) एक बिंदु z के अनुरूप f(x) = d(z,x) है। मैनहट्टन मीट्रिक के लिए त्रिकोण असमानता द्वारा, इस फॉर्म का एक फ़ंक्शन मैनहट्टन-मीट्रिक विमान में किसी भी z के लिए तंग अवधि की संपत्ति 1 को संतुष्ट करता है। टाइट स्पैन की संपत्ति 2 दिखाने के लिए, X में कुछ बिंदु x पर विचार करें; हमें X में y इस तरह खोजना चाहिए कि f(x)+f(y)=d(x,y). लेकिन यदि x शीर्ष के रूप में z वाले चार चतुर्थांशों में से एक में है, तो y को विपरीत चतुर्थांश में किसी भी बिंदु के रूप में लिया जा सकता है, इसलिए गुण 2 भी संतुष्ट होता है। इसके विपरीत यह दिखाया जा सकता है कि तंग अवधि का प्रत्येक बिंदु इस तरह से इन बिंदुओं के ऑर्थोगोनल उत्तल हल में एक बिंदु से मेल खाता है। हालांकि, उच्च आयामों में मैनहट्टन मीट्रिक के साथ पॉइंट सेट के लिए, और डिस्कनेक्ट किए गए ऑर्थोगोनल हल्स के साथ प्लानर पॉइंट सेट के लिए, टाइट स्पैन ऑर्थोगोनल उत्तल हल से भिन्न होता है।
टाइट स्पैन का आयाम जब X परिमित है
ऊपर दी गई परिभाषा n () आर में इंगित करता हैX, आयाम n का एक वास्तविक सदिश स्थान। दूसरी ओर, यदि हम T(X) के आयाम को बहुफलकीय संकुल मानते हैं, Develin (2006) ने दिखाया कि, मीट्रिक पर उपयुक्त सामान्य स्थिति धारणा के साथ, यह परिभाषा n/3 और n/2 के बीच आयाम वाले स्थान की ओर ले जाती है।
वैकल्पिक परिभाषाएँ
इसके उप-स्थान के उद्देश्य से एक मीट्रिक स्थान की धारणा के आधार पर एक वैकल्पिक परिभाषा का वर्णन किया गया था Holsztyński (1968), जिन्होंने यह साबित किया कि बैनच स्पेस का इंजेक्शन लिफाफा, बनच स्पेस की श्रेणी में, तंग अवधि के साथ मेल खाता है (रैखिक संरचना को भूलने के बाद)। यह प्रमेय मनमाने ढंग से बनच रिक्त स्थान से सी (एक्स) के बनच स्थान तक कुछ समस्याओं को कम करने की अनुमति देता है, जहां एक्स एक कॉम्पैक्ट स्थान है।
Develin & Sturmfels (2004) अंतरिक्ष में प्रत्येक बिंदु से एक दूसरे बिंदु तक दूरी के वैक्टरों के उष्णकटिबंधीय ज्यामिति के रूप में एक सीमित मीट्रिक अंतरिक्ष की तंग अवधि की वैकल्पिक परिभाषा प्रदान करने का प्रयास किया। हालांकि, बाद में उसी वर्ष उन्होंने इरेटम में स्वीकार किया Develin & Sturmfels (2004a) कि, जबकि उष्णकटिबंधीय उत्तल पतवार में हमेशा तंग फैलाव होता है, यह इसके साथ मेल नहीं खा सकता है।
अनुप्रयोग
- Dress, Huber & Moulton (2001) जैविक डेटा से फाइलोजेनेटिक्स में टाइट स्पैन के अनुप्रयोगों का वर्णन करें।
- टाइट स्पैन के-सर्वर समस्या के लिए कई ऑनलाइन एल्गोरिदम में एक भूमिका निभाता है।[10] *Sturmfels & Yu (2004) मेट्रिक स्पेस को छह बिंदुओं तक वर्गीकृत करने के लिए टाइट स्पैन का उपयोग करता है।
- Chepoi (1997) कट मीट्रिक ्स को अधिक सामान्य परिमित मीट्रिक स्थानों में पैक करने के परिणामों को साबित करने के लिए टाइट स्पैन का उपयोग करता है।
यह भी देखें
- Kuratowski एंबेडिंग, किसी भी मीट्रिक स्पेस को Banach स्पेस में एम्बेड करना, जिसे Kuratowski मैप के समान परिभाषित किया गया है
- इंजेक्शन मीट्रिक स्थान
टिप्पणियाँ
- ↑ Dress, Huber & Moulton (2001).
- ↑ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 Khamsi, Mohamed A.; Kirk, William A. (2001). मेट्रिक स्पेस और फिक्स्ड पॉइंट थ्योरी का परिचय. Wiley.
- ↑ 3.0 3.1 3.2 Dress, Andreas; Huber, Katharina T.; Koolen, Jacobus; Moulton, Vincent; Spillner, Andreas (2012). बेसिक फाइलोजेनेटिक कॉम्बिनेटरिक्स. Cambridge University Press. ISBN 978-0-521-76832-0.
- ↑ Kirk, William; Shahzad, Naseer (2014). डिस्टेंस स्पेस में फिक्स्ड पॉइंट थ्योरी. Springer. p. 24. ISBN 978-3-319-10926-8.
- ↑ 5.0 5.1 5.2 Huson, Daniel H.; Rupp, Regula; Scornavacca, Celine (2010). Phylogenetic Networks: Conceps, Algorithms and Applications. Cambridge University Press. ISBN 978-0-521-75596-2.
- ↑ Deza, Michel Marie; Deza, Elena (2014). दूरियों का विश्वकोश (Third ed.). Springer. p. 47. ISBN 978-3-662-44341-5.
- ↑ Melleray, Julien (2008). "उरीसोहन अंतरिक्ष के कुछ ज्यामितीय और गतिशील गुण". Topology and Its Applications. 155 (14): 1531–1560. doi:10.1016/j.topol.2007.04.029.
- ↑ Benyamini, Yoav; Lindenstrauss, Joram (2000). ज्यामितीय गैर रेखीय कार्यात्मक विश्लेषण. American Mathematical Society. p. 32. ISBN 978-0-8218-0835-1.
- ↑ In two dimensions, the Manhattan distance is isometric after rotation and scaling to the [[Lp space#General_ℓp-space|ℓ∞ distance]], so with this metric the plane is itself injective, but this equivalence between ℓ1 and ℓ∞ does not hold in higher dimensions.
- ↑ Chrobak & Larmore (1994).
- ↑ Khamsi and Kirk use this condition in their definition.
- ↑ Khamsi and Kirk's proof shows one implication of the equivalence to the condition immediately above. The other implication is not difficult to show.
- ↑ I.e., the Kuratowski map We will introduce the Kuratowski map below.
- ↑ The supremum is achieved with y=x.
- ↑ The supremum is achieved with y=x.
संदर्भ
- Chepoi, Victor (1997), "A TX approach to some results on cuts and metrics", Advances in Applied Mathematics, 19 (4): 453–470, doi:10.1006/aama.1997.0549.
- Chrobak, Marek; Larmore, Lawrence L. (1994), "Generosity helps or an 11-competitive algorithm for three servers", Journal of Algorithms, 16 (2): 234–263, doi:10.1006/jagm.1994.1011, S2CID 15169525.
- Develin, Mike (2006), "Dimensions of tight spans", Annals of Combinatorics, 10 (1): 53–61, arXiv:math.CO/0407317, doi:10.1007/s00026-006-0273-y, S2CID 92984638.
- Develin, Mike; Sturmfels, Bernd (2004), "Tropical convexity" (PDF), Documenta Mathematica, 9: 1–27, doi:10.4171/dm/154, S2CID 64471.
- Develin, Mike; Sturmfels, Bernd (2004a), "Erratum for "Tropical Convexity"" (PDF), Documenta Mathematica, 9: 205–206, doi:10.4171/dm/154, S2CID 64471.
- Dress, Andreas W. M. (1984), "Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups", Advances in Mathematics, 53 (3): 321–402, doi:10.1016/0001-8708(84)90029-X.
- Dress, Andreas W. M.; Huber, K. T.; Moulton, V. (2001), "Metric spaces in pure and applied mathematics" (PDF), Documenta Mathematica (Proceedings Quadratic Forms LSU): 121–139.
- Holsztyński, Włodzimierz (1968), "Linearisation of isometric embeddings of Banach Spaces. Metric Envelopes.", Bull. Acad. Polon. Sci., 16: 189–193.
- Isbell, J. R. (1964), "Six theorems about injective metric spaces", Comment. Math. Helv., 39: 65–76, doi:10.1007/BF02566944, S2CID 121857986.
- Sturmfels, Bernd; Yu, Josephine (2004), "Classification of Six-Point Metrics", The Electronic Journal of Combinatorics, 11: R44, arXiv:math.MG/0403147, Bibcode:2004math......3147S, doi:10.37236/1797, S2CID 6733896.
बाहरी संबंध
- Joswig, Michael, Tight spans.