Some Stability Results on Graphs

तकनीकी सारांश: ग्राफ पर स्थिरता के परिणाम

समस्या विवरण
यह शोध पत्र शास्त्रीय वास्तविक फलन सिद्धांत (classical real function theory) से ग्राफ सिद्धांत के क्षेत्र में हाइयर्स-उलम स्थिरता सिद्धांत (Hyers-Ulam stability theory) के विस्तार को संबोधित करता है। शास्त्रीय विश्लेषण में, हाइयर्स-उलम स्थिरता इस बात की जांच करती है कि क्या एक फलन जो किसी विशिष्ट कार्यात्मक गुण (जैसे कि योगात्मकता, एकतलता, या उत्तलता) को लगभग संतुष्ट करता है, वह एक ऐसे फलन के निकट है जो उस गुण को सटीक रूप से संतुष्ट करता है। लेखक भारित ग्राफों (weighted graphs) के आधार पर इस ढांचे को अनुकूलित करने का लक्ष्य रखते हैं। विशेष रूप से, वे ग्राफ भारों के साथ असतत कार्यात्मक असमानताओं (discrete functional inequalities) के आधार पर "लगभग" एकतल (monotone), उप-योगात्मक (subadditive), और उत्तल (convex) ग्राफों को परिभाषित करते हैं। केंद्रीय समस्या यह निर्धारित करना है कि यदि कोई ग्राफ इन त्रुटि सीमा $\varepsilon$ के भीतर लगभग इन असमानताओं को संतुष्ट करता है, तो क्या उसी शीर्ष (vertex) और किनारा (edge) सेट वाला एक संगत ग्राफ मौजूद है जो सटीक संरचनात्मक गुण को संतुष्ट करता है, ताकि उनके भार फलनों (weight functions) के बीच का अंतर $\varepsilon$ के एक फलन द्वारा सीमित हो।

कार्यप्रणाली
लेखक एक गैर-भारित ग्राफ $G(V, E)$ और उसके गैर-रिक्त उपग्राफों $\mathcal{H}$ के ढांचे के भीतर कार्य करते हैं। इन उपग्राफों के लिए एक भार फलन $w: \mathcal{H} \to \mathbb{R}^+$ सौंपा जाता है। कार्यप्रणाली में शामिल है:

1. अनुमानित गुणों को परिभाषित करना:
   • अनुमानित एकतलता (Approximate Monotonicity): एक ग्राफ अनुमानित रूप से एकतल है यदि $H \subset H'$ होने पर $w(H) \leq w(H') + \varepsilon$ हो।
   • अनुमानित उप-योग्यता (Approximate Subadditivity): एक ग्राफ अनुमानित रूप से उप-योगात्मक है यदि किसी भी विभाजन $H = \bigcup H_i$ के लिए $w(H) \leq \sum w(H_i) + \varepsilon$ हो।
   • अनुमानित उत्तलता (Approximate Convexity): इसे द्वितीय-क्रम की एकतलता के समान परिभाषित किया गया है, जहाँ श्रृंखलाओं $H_1 \subseteq H \subseteq H_2$ के लिए $2w(H) \leq w(H_1) + w(H_2) + \varepsilon$ होता है।
2. रचनात्मक प्रमाण (Constructive Proofs): लेखक सटीक गुणों को संतुष्ट करने वाले नए भार फलनों ($\tilde{w}$, $\underline{w}$, $\hat{w}$) को परिभाषित करने के लिए रचनात्मक विधियों का उपयोग करते हैं।
   • एकतलता के लिए, वे एक सुपरसेट (superset) के इन्फिमम (infimum) और एक सुधार पद (correction term) के रूप में नया भार परिभाषित करते हैं।
   • उप-योग्यता के लिए, वे एक उपग्राफ के सभी संभावित विभाजनों के इन्फिमम का उपयोग करके एक "उप-योगात्मक लघुतम" (subadditive minorant) का निर्माण करते हैं।
   • उत्तलता के लिए, वे मध्यवर्ती उपग्राफों पर इन्फिमम लेकर परिभाषित भारों के एक पुनरावृत्ति अनुक्रम (iterative sequence) का उपयोग करते हैं, और इस अनुक्रम के एक उत्तल भार फलन की ओर अभिसरण (convergence) को सिद्ध करते हैं।
3. सैंडविच प्रमेय (Sandwich Theorems): प्रमाण अक्सर "सैंडविच" असमानताओं को स्थापित करने पर निर्भर करते हैं, जो यह दिखाते हैं कि मूल अनुमानित भार फलन सटीक संरचनात्मक गुणों से प्राप्त निचले और ऊपरी आउंड (bound) के बीच स्थित है, जिससे विचलन सीमित हो जाता है।

प्रमुख योगदान और परिणाम
यह शोध पत्र तीन संरचनात्मक गुणों के अनुरूप तीन प्राथमिक प्रमेय स्थापित करता है:

• एकतलता की स्थिरता (प्रस्ताव 1.1):
  यदि एक भारित ग्राफ $G(V, E, w)$ त्रुटि $\varepsilon$ के साथ अनुमानित रूप से एकतल है, तो एक ही शीर्ष और किनारा सेट वाला एक एकतल (बढ़ता हुआ) ग्राफ $G(V, E, \tilde{w})$ मौजूद है, जिससे $\|w - \tilde{w}\| \leq \varepsilon/2$ है। इसका विलोम भी सिद्ध किया गया है: यदि एक भार फलन और एक एकतल भार फलन के बीच की दूरी $\leq \varepsilon/2$ है, तो मूल फलन अनुमानित रूप से एकतल है।

• उप-योग्यता की स्थिरता (प्रमेय 1.2):
  यदि एक ग्राफ त्रुटि $\varepsilon$ के साथ अनुमानित रूप से उप-योगात्मक है, तो एक उप-योगात्मक ग्राफ $G(V, E, \underline{w})$ मौजूद है जिससे $\|w - \underline{w}\| < \varepsilon$ है। प्रमाण में एक उप-योगात्मक लघुतम का निर्माण करना और यह प्रदर्शित करना शामिल है कि मूल भार फलन इस लघुतम और इसके विभाजनों के योग द्वारा सीमित है।

• उत्तलता की स्थिरता (प्रमेय 1.3):
  त्रुटि $\varepsilon$ वाले अनुमानित उत्तल ग्राफ के लिए, लेखक एक उत्तल ग्राफ $G(V, E, \hat{w})$ के अस्तित्व को सिद्ध करते हैं जो निम्नलिखित असमानता को संतुष्ट करता है:
  $$\inf_{H \in \mathcal{H}} w(H) - \frac{\varepsilon}{2} \leq \hat{w}(H) \leq w(H) + \frac{\varepsilon}{2}$$
  यह परिणाम भार फलनों के एक अभिसारी अनुक्रम के माध्यम से एक गैर-तुच्छ उत्तल लघुतम का निर्माण करके और एकतलता के मामले के समान एक अपघटन तर्क का उपयोग करके प्राप्त किया गया है।

महत्व और दावे
लेखक दावा करते हैं कि यह कार्य सफलतापूर्वक ग्राफ सिद्धांत में हाइयर्स-उलम प्रकार की स्थिरता विशेषताओं को एकीकृत करता है। प्राथमिक महत्व इस बात में निहित है कि यह प्रदर्शित करना है कि एक अनुमानित संरचित ग्राफ और एक सटीक रूप से संरचित समकक्ष के बीच का "भार अंतर" संबद्ध त्रुटि $\varepsilon$ पर रैखिक रूप से निर्भर करता है और महत्वपूर्ण रूप से नहीं बदलता है।

यह शोध पत्र एक मध्यम दायरे को बनाए रखता है, जो शीर्ष या किनारे सेट की कार्डिनैलिटी (cardinality) पर प्रतिबंध लगाए बिना सामान्य ग्राफों के लिए इन सटीक समकक्षों के सैद्धांतिक अस्तित्व पर ध्यान केंद्रित करता है। लेखक स्पष्ट रूप से कहते हैं कि परिणामों को परिमित (finite) ग्राफों के लिए अनुकूलित किया जा सकता है। वे पाठ के भीतर विशिष्ट वास्तविक दुनिया के अनुप्रयोगों या प्रयोगात्मक सत्यापन का प्रस्ताव नहीं करते हैं। इसके बजाय, वे भविष्य के अनुसंधान दिशाओं की पहचान करते हैं, जैसे कि विशिष्ट ग्राफ वर्गों (जैसे कि ट्री, बाइपार्टाइट, रेगुलर, या पूर्ण ग्राफ) के लिए अधिक सटीक, केस-विशिष्ट नॉर्म बाउंड्स (norm bounds) की जांच करना और सिद्धांत की प्रयोज्यता को व्यापक बनाने के लिए त्रुटि पद को एक अदिश $\varepsilon$ से एक बहु-आयामी फलन में सामान्यीकृत करना।