Forcing graph
ग्राफ सिद्धांत में, एक बल ग्राफ वह है जिसका घनत्व यह निर्धारित करता है कि ग्राफ अनुक्रम अर्ध-यादृच्छिक है या नहीं। यह शब्द पहली बार 1989 में चुंग, ग्राहम और विल्सन द्वारा गढ़ा गया था, और ग्राफ अनुक्रमों में छद्म यादृच्छिकता के अध्ययन में ग्राफ को मजबूर करना एक महत्वपूर्ण भूमिका निभाता है। परिभाषाएँ चलो, सबग्राफ घनत्व के रूप में जाना जाता है (विशेष रूप से, का किनारे का घनत्व है)। ग्राफों के एक अनुक्रम को अर्ध-यादृच्छिक कहा जाता है, यदि सभी ग्राफों के लिए, किनारे का घनत्व कुछ तक पहुंचता है और बढ़ने के साथ पहुंचता है, तो किनारों की संख्या कहाँ है। सहज रूप से, इसका मतलब है कि दिए गए किनारे के घनत्व के साथ एक ग्राफ अनुक्रम में ग्राफ समरूपता की संख्या होती है जो एक यादृच्छिक ग्राफ अनुक्रम में उम्मीद की जाएगी। एक ग्राफ को फोर्सिंग कहा जाता है यदि सभी ग्राफ अनुक्रमों के लिए जहां अनंत तक जाता है, अर्ध-यादृच्छिक होता है यदि पहुँचता है। दूसरे शब्दों में, केवल एकल ग्राफ के समरूपता घनत्व की जाँच करके यह सत्यापित किया जा सकता है कि ग्राफ का एक क्रम अर्ध-यादृच्छिक है। ग्राफों की भाषा का उपयोग करके ग्राफ को मजबूर करने की दूसरी परिभाषा है। औपचारिक रूप से, एक ग्राफ को फोर्सिंग कहा जाता है यदि प्रत्येक ग्राफॉन ऐसा है जो स्थिर है। सहज ज्ञान से, यह समझ में आता है कि ये परिभाषाएँ संबंधित हैं। स्थिर ग्राफॉन एर्दोस-रेनी यादृच्छिक ग्राफ का प्रतिनिधित्व करता है, इसलिए कोई भी उम्मीद कर सकता है कि इसका अर्ध-यादृच्छिक ग्राफ के साथ घनिष्ठ संबंध होगा। वास्तव में, ये परिभाषाएँ समान हैं। उदाहरण विचार किए जाने वाले पहले बल ग्राफ 4-चक्र है, क्योंकि यह अर्ध-यादृच्छिकता की अन्य स्थितियों के साथ घनिष्ठ संबंध रखता है। यह चुंग, ग्राहम और विल्सन द्वारा एक ही पेपर में दिखाया गया था कि प्रत्येक सम चक्र और पूर्ण द्विदलीय ग्राफ के साथ फॉर्म मजबूर कर रहे हैं। कोनलोन, फॉक्स और सुदकोव ने इस अंतिम परिणाम का विस्तार करते हुए एक भाग में दो शीर्षों वाले सभी द्विदलीय ग्राफों को शामिल किया जो दूसरे भाग में पूर्ण हैं। ग्राफ का एक परिवार मजबूर कर रहा है अर्ध-यादृच्छिक है जब भी सभी के लिए पहुँचता है। मजबूर करने वाले परिवारों की विशेषता, मजबूर करने वाले ग्राफ की तुलना में बहुत अधिक चुनौतीपूर्ण है, इसलिए कुछ ऐसे हैं जो ज्ञात हैं। ज्ञात मजबूर करने वाले परिवारों में शामिल हैंः, जहाँ एक सकारात्मक पूर्णांक है;, जहाँ और सकारात्मक पूर्णांक हैं;, जहाँ; और, जहाँ और। बाध्यकारी अनुमान 2004 में स्कोकन और थोमा द्वारा प्रस्तुत किया गया था और 2010 में कॉनलॉन, फॉक्स और सुदकोव द्वारा औपचारिक रूप दिया गया था। यह ग्राफ़ को मजबूर करने के लिए एक लक्षण वर्णन प्रदान करता है, जिसे निम्नानुसार औपचारिक रूप दिया गया हैः इस दावे की एक दिशा सर्वविदित है। चुंग, ग्राहम और विल्सन ने दिखाया कि यदि एक ग्राफ में एक विषम चक्र है, तो यह मजबूर नहीं किया जा सकता है, इसलिए यदि एक ग्राफ मजबूर कर रहा है, तो यह द्विदलीय होना चाहिए। इसके अलावा, कॉनलॉन, फॉक्स और सुदकोव ने तर्क दिया कि हर जंगल के लिए दृष्टिकोण तब होता है जब लगभग नियमित (और जरूरी नहीं कि अर्ध-यादृच्छिक) ग्राफ अनुक्रम होते हैं। इस प्रकार, एक बल ग्राफ द्विदलीय होना चाहिए और कम से कम एक चक्र होना चाहिए। दूसरी दिशा अभी तक सिद्ध नहीं हुई है, लेकिन ऐसा कोई बल ग्राफ नहीं मिला है जिसमें ये दोनों गुण न हों। बाध्यकारी अनुमान सेडोरेंको के अनुमान का भी संकेत मिलता है, जो इस क्षेत्र में एक लंबे समय से चला आ रहा अनुमान है। यह ज्ञात है कि सभी बल ग्राफ सिडोरेंको हैं, इसलिए यदि बल अनुमान सही है, तो कम से कम एक चक्र वाले सभी द्विदलीय ग्राफ सिडोरेंको होंगे। चूँकि पेड़ सिडोरेंको हैं, इसलिए सभी द्विदलीय ग्राफ सिडोरेंको होंगे। संदर्भ ग्राफ परिवार