[2504.18427] इंडिपेंडेंट सेट्स पर ग्लॉबर डायनेमिक्स का सबएक्सपोनेंशियल और पैरामीटराइज्ड मिक्सिंग टाइम्स

मैलोरी मारिन द्वारा लिखित सबएक्सपोनेंशियल एंड पैरामीटराइज्ड मिक्सिंग टाइम्स ऑफ ग्लौबर डायनेमिक्स ऑन इंडिपेंडेंट सेट्स शीर्षक वाले पेपर का एक पीडीएफ देखें।

पीडीएफ देखें
HTML (प्रयोगात्मक)

अमूर्त:ग्राफ $G$ को देखते हुए, हार्ड-कोर मॉडल अपने स्वतंत्र सेटों पर संभाव्यता वितरण को परिभाषित करता है, आकार $k$ के प्रत्येक सेट को $\frac{\lambda^k}{Z}$ की संभावना निर्दिष्ट करता है, जहां $\lambda>0$ एक पैरामीटर है जिसे \emph{fugacity} के रूप में जाना जाता है और $Z$ एक सामान्यीकरण स्थिरांक है। ग्लॉबर डायनेमिक्स एक सरल मार्कोव श्रृंखला है जो इस वितरण में परिवर्तित होती है और कुशल नमूनाकरण को सक्षम बनाती है। इसका \emph{मिश्रण समय}, स्थिर वितरण तक पहुंचने के लिए आवश्यक चरणों की संख्या, विभिन्न ग्राफ वर्गों में व्यापक रूप से अध्ययन किया गया है, अधिकांश पिछले काम में बहुपद और घातीय मिश्रण समय के बीच द्विभाजन पर जोर दिया गया है, जिसमें ग्राफ के विरल वर्गों पर विशेष ध्यान दिया गया है। कम्प्यूटेशनल जटिलता के लिए आधुनिक सुक्ष्म दृष्टिकोण से प्रेरित होकर, हम डिस्क ग्राफ़ जैसे ज्यामितीय चौराहे ग्राफ़ पर ग्लौबर गतिशीलता के उपघातीय मिश्रण समय की जांच करते हैं। हम आगे दो संरचनात्मक मापदंडों के संबंध में मानकीकृत मिश्रण समय का अध्ययन करते हैं जो घने ग्राफ़ में भी छोटे रह सकते हैं: वृक्ष-स्वतंत्रता संख्या और पथ-स्वतंत्रता संख्या। डायर, ग्रीनहिल और मुलर के परिणाम के आधार पर, हम दिखाते हैं कि ग्लौबर गतिशीलता बंधे हुए पथ-स्वतंत्रता संख्या के ग्राफ़ पर बहुपद समय में और अर्ध-बहुपद समय में मिश्रित होती है जब पेड़-स्वतंत्रता संख्या सीमित होती है। इसके अलावा, हम आचरण तर्क के माध्यम से साबित करते हैं कि दोनों सीमाएं सख्त हैं, जिससे उनके काम में उठाए गए एक प्रश्न का समाधान हो जाता है। यह कार्य हार्ड-कोर मॉडल से नमूना लेने के लिए एक सरल और कुशल एल्गोरिदम प्रदान करता है। शास्त्रीय दृष्टिकोणों के विपरीत जो स्पष्ट रूप से ज्यामितीय अभ्यावेदन या पेड़ अपघटन या विभाजक पेड़ जैसे अपघटन के निर्माण पर निर्भर करते हैं, हमारे विश्लेषण के लिए केवल मिश्रण समय सीमा स्थापित करने के लिए उनके अस्तित्व की आवश्यकता होती है – इन संरचनाओं का उपयोग सीधे एल्गोरिथ्म द्वारा नहीं किया जाता है।