Flag algebra
फ्लैग अल्जेब्रा ग्राफ सिद्धांत के क्षेत्र में एक महत्वपूर्ण कम्प्यूटेशनल उपकरण हैं जिनके समरूपता घनत्व और संबंधित विषयों में अनुप्रयोगों की एक विस्तृत श्रृंखला है। मोटे तौर पर, वे समरूपता घनत्वों को जोड़ने और गुणा करने की धारणा को औपचारिक रूप देते हैं और कंप्यूटर के साथ ग्राफ समरूपता असमानताओं को अर्ध-परिमित प्रोग्रामिंग समस्याओं तक कम करके उन्हें हल करने के लिए एक रूपरेखा स्थापित करते हैं। मूल रूप से अलेक्जेंडर रेज़बोरोव द्वारा 2007 के एक पेपर में पेश की गई, यह विधि तब से कई कठिन, पहले से अनसुलझे ग्राफ सैद्धांतिक प्रश्नों को हल करने के लिए आई है। इनमें व्यवहार्य किनारे के घनत्व के क्षेत्र, त्रिभुज घनत्व जोड़े और त्रिभुज मुक्त ग्राफ में पेंटागन की अधिकतम संख्या के बारे में प्रश्न शामिल हैं। प्रेरणा ध्वज बीजगणित के सिद्धांत की प्रेरणा का श्रेय जॉन एड्रियन बॉन्डी और कैकेटा-हैगक्विस्ट अनुमान पर उनके काम को दिया जाता है, जहां उन्होंने अपने मुख्य विचारों को एक ग्राफ होमोमोर्फिज्म के माध्यम से चित्रित किया जो मेंटेल के प्रमेय के लिए स्वाद प्रमाण है। यह प्रमाण दोहरी गिनती के माध्यम से मेंटेल के पारंपरिक प्रमाण पर एक अनुकूलन है, सिवाय ग्राफ समरूपता घनत्व के संदर्भ में व्यक्त किए गए और यह दर्शाता है कि केवल घनत्व संबंधों के साथ कितनी जानकारी को कूटबद्ध किया जा सकता है। प्रमेय (मेंटेल): त्रिभुज-मुक्त ग्राफ में किनारे का घनत्व अधिक से अधिक होता है। दूसरे शब्दों में, चूंकि ग्राफ त्रिभुज-मुक्त है, 3 शीर्षों के बीच, वे या तो एक स्वतंत्र सेट, एक एकल प्रेरित किनारा, या लंबाई 2 का पथ बना सकते हैं। एक उपग्राफ के प्रेरित घनत्व के रूप में दर्शाते हुए, दोहरी गिनती से पता चलता हैः सहज रूप से, क्योंकि a में दो s एक साथ जुड़े होते हैं, और 3 बिंदुओं के सेट के बीच सामान्य शीर्ष को लेबल करने के 3 तरीके हैं। वास्तव में, इसे प्रेरित एस की संख्या को दोगुना गिनकर सख्ती से साबित किया जा सकता है। लेट करना शीर्षों की संख्या को दर्शाता है, हमारे पास हैः जहां लंबाई 2 का पथ है और इसके मध्य शीर्ष को लेबल किया गया है, और एस के घनत्व को उस बाधा के अधीन दर्शाता है जो लेबल किए गए शीर्ष का उपयोग किया जाता है, और इसे एक उचित प्रेरित उपलेख के रूप में तभी गिना जाता है जब इसका लेबल किया गया शीर्ष इसके साथ मेल खाता है। अब, ध्यान दें कि चूंकि दो एस चुनने की संभावना जहां बिना लेबल वाले शीर्ष मेल खाते हैं, कम है (कठोर होने के लिए, एक सीमा जो ली जानी चाहिए, इसलिए बड़े और बड़े ग्राफ के अनुक्रम पर एक सीमा कार्य के रूप में कार्य करता है। यह विचार ध्वज बीजगणित की वास्तविक परिभाषा के लिए महत्वपूर्ण होगा।) समाप्त करने के लिए, इसे हमारे मूल संबंध में वापस लाने के लिए कौची-श्वार्ज असमानता को लागू करें जो सहज रूप से परिकल्पना की गई थी। अंत में, ध्यान दें कि इसलिए इस प्रमाण के महत्वपूर्ण विचार जो ध्वज बीजगणित के सिद्धांत में सामान्यीकृत किए जाएंगे, वे हैं प्रतिस्थापन, जैसे कि लेबल किए गए ग्राफ घनत्वों का उपयोग, घनत्वों के केवल "सीमा मामले" पर विचार करना, और एक सार्थक परिणाम प्राप्त करने के लिए अंत में कौची को लागू करना। परिभाषा निषिद्ध उप-आलेखों के संग्रह को ठीक करें और-मुक्त आलेखों के आलेखों के समूह पर विचार करें। अब, एक प्रकार के आकार को लेबल किए गए शीर्षों के साथ एक ग्राफ के रूप में परिभाषित करें। आकार 0 के प्रकार को आम तौर पर के रूप में दर्शाया जाता है। सबसे पहले, हम एक-ध्वज, एक आंशिक रूप से लेबल किए गए ग्राफ को परिभाषित करते हैं जो ध्वज बीजगणित के सिद्धांत के लिए महत्वपूर्ण होगाः परिभाषाः एक-ध्वज एक जोड़ी है जहां एक अंतर्निहित, बिना लेबल वाला,-मुक्त ग्राफ है, जबकि शीर्षों पर एम्बेडिंग के लिए एक लेबल किए गए ग्राफ को परिभाषित करता है। - फ्लैग के सेट को होने और-फ्लैग के आकार के सेट को होने के लिए दर्शाएँ। एक उदाहरण के रूप में, ऊपर दिए गए मेंटेल के प्रमेय के प्रमाण से एक-ध्वज है जहां एक शीर्ष के अनुरूप आकार 1 का एक प्रकार है। झंडे को संतुष्ट करने के लिए, हम अंतर्निहित ग्राफ पर झंडे के घनत्व को निम्नलिखित तरीके से परिभाषित कर सकते हैंः परिभाषाः झंडे के घनत्व को सफलतापूर्वक यादृच्छिक रूप से इस तरह से एम्बेड करने की संभावना के रूप में परिभाषित किया गया है कि वे गैर-इंटरसेक्टिंग हैं और सभी को ठीक उसी तरह से लेबल किया गया है जैसे कि चालू है। अधिक सटीक रूप से, यादृच्छिक रूप से जोड़ीदार विच्छेद चुनें और इस संभावना के रूप में परिभाषित करें कि-ध्वज सभी के लिए समरूप है। ध्यान दें कि, जब एम्बेड किया जाता है,-फ्लैग कहाँ हैं, तो इसे पहले आकार के-फ्लैग में एम्बेड करके और फिर एम्बेड करके किया जा सकता है, जो सूत्र देता हैः इसे झंडों के सेट तक विस्तारित करने से श्रृंखला नियम मिलता हैः प्रमेय (श्रृंखला नियम): यदि झंडे हैं, तो ऐसे प्राकृतिक हैं जो आकार के झंडे में फिट होते हैं, और आकार के एक झंडे के साथ फिट होते हैं। याद रखें कि मेंटेल के लिए पिछले प्रमाण में रूप की शर्तों के रैखिक संयोजन शामिल थे। प्रासंगिक विचार अनंत की ओर रुख करने के साथ थोड़े अस्पष्ट थे, लेकिन स्पष्ट रूप से एक ऐसा अनुक्रम है जो सभी के लिए कुछ में अभिसरण करता है, जहां एक सीमा कार्यात्मक कहा जाता है। इस प्रकार, सभी संदर्भ वास्तव में कार्यात्मक सीमा को संदर्भित करते हैं। अब, ग्राफ समरूपता असमानताओं को विभिन्न s के साथ रैखिक संयोजन के रूप में लिखा जा सकता है, लेकिन उन्हें एकल शब्द के रूप में व्यक्त करना सुविधाजनक होगा। यह-फ्लैग के औपचारिक रैखिक संयोजनों के सेट को परिभाषित करने के लिए प्रेरित करता है, और अब इसे एक रैखिक कार्य तक बढ़ाया जा सकता है। हालांकि, केवल सीमित कार्यों की जांच करते समय पूर्ण स्थान का उपयोग करना व्यर्थ है, क्योंकि कुछ-झंडों के घनत्वों के बीच गैर-तुच्छ संबंध मौजूद हैं। विशेष रूप से, श्रृंखला नियम से पता चलता है कि यह हमेशा सच है। कर्नेल के इन सभी तत्वों से निपटने के बजाय, उपरोक्त रूप के अभिव्यक्तियों के समूह (यानी। जो एक एकल-ध्वज के साथ श्रृंखला नियम से प्राप्त किए गए हैं) और हमारे अंतिम विश्लेषण में उन्हें उद्धृत करते हैं। ये विचार एक फ्लैग बीजगणित की परिभाषा बनाने के लिए एकजुट होते हैंः परिभाषा (फ्लैग अल्जेब्रा): एक फ्लैग बीजगणित को द्वि-रेखीय प्रचालक से लैस-झंडों के रैखिक संयोजन के स्थान पर परिभाषित किया जाता है और किसी भी प्राकृतिक के लिए जो आकार के-झंडे में फिट होता है, प्रचालक को रैखिक रूप से विस्तारित करता है। यह जांचना बाकी है कि एक जोड़ी के लिए विकल्प मायने नहीं रखता है बशर्ते कि यह काफी बड़ा हो (इसे श्रृंखला नियम के साथ साबित किया जा सकता है) और साथ ही यदि ऐसा है, तो इसका मतलब है कि प्रचालक भागफल का सम्मान करता है और इस प्रकार वांछित स्थान पर एक अच्छी तरह से परिभाषित बीजगणित बनाता है। प्रचालक के लिए इस परिभाषा का एक महत्वपूर्ण परिणाम यह है कि गुणन को सीमा कार्यों पर माना जाता है। विशेष रूप से, एक सीमा कार्यात्मक के लिए, पहचान सही है। उदाहरण के लिए, यह दिखाया गया था कि मेंटेल के लिए हमारे प्रमाण में, और यह परिणाम इस कथन का केवल एक परिणाम है। अधिक आम तौर पर, यह तथ्य कि गुणक का अर्थ है कि सभी सीमा कार्यात्मक और के बीच बीजगणित समरूपता हैं। ऊपर दी गई परिभाषा---------------------------------------------------------------------------------------------------------------------------------------------- हालांकि, ज्यादातर समय, बिना लेबल वाले ग्राफ, या-फ्लैग, सबसे अधिक दिलचस्प होते हैं। पूर्व से उत्तरार्द्ध तक पहुँचने के लिए, नीचे की ओर प्रचालक को परिभाषित करें। नीचे की ओर प्रचालक को सबसे स्वाभाविक तरीके से परिभाषित किया गया हैः एक-ध्वज दिए जाने पर, उन्हें सौंपे गए लेबल को भूलने के परिणामस्वरूप-ध्वज माना जाता है। अब,-फ्लैग और बिना लेबल वाले ग्राफ के बीच एक प्राकृतिक मानचित्रण को परिभाषित करने के लिए, यह संभावना है कि यादृच्छिक रूप से लिए गए एक इंजेक्टिव मानचित्र में छवि समरूप है, और परिभाषित की गई है। रैखिक रूप से विस्तार करने से एक वैध रैखिक मानचित्र मिलता है जो बिना लेबल वाले झंडे के संयोजन के लिए-झंडे के संयोजन भेजता है। इसका सबसे महत्वपूर्ण परिणाम इसके औसत गुण हैं। विशेष रूप से, एक-फ्लैग और बिना लेबल वाले ग्राफ को ठीक करें, फिर यादृच्छिक रूप से एक एम्बेडिंग का चयन यादृच्छिक चर को परिभाषित करता है। यह दिखाया जा सकता है कि फ्लैग अल्जेब्रा के साथ अनुकूलन सभी रैखिक कार्य, बीजगणित समरूपता हैं। इसके अलावा, परिभाषा के अनुसार, किसी भी झंडे के लिए एक घनत्व सीमा का प्रतिनिधित्व करता है। इस प्रकार, कहें कि एक समरूपता सकारात्मक है यदि और केवल यदि, और मान लीजिए कि यह सकारात्मक समरूपता का समुच्चय है। कोई यह दिखा सकता है कि सीमा कार्यों का सेट बिल्कुल सकारात्मक समरूपता का सेट है, इसलिए यह सेट की बाद की परिभाषा को समझने के लिए पर्याप्त है। एक रैखिक संयोजन के लिए एक वैध ग्राफ समरूपता असमानता प्राप्त करने के लिए, इसे सभी संभावित रैखिक कार्यों पर गैर-नकारात्मक होने की आवश्यकता है, जिसका अर्थ यह होगा कि यह सभी ग्राफों के लिए सही है। इसे ध्यान में रखते हुए, प्रकार के शब्दार्थ शंकु को परिभाषित करें, एक ऐसा समूह जो एक बार फिर, सबसे अधिक रुचि का मामला है, जो बिना लेबल वाले ग्राफ के मामले से मेल खाता है। हालांकि, नीचे की ओर प्रचालक के पास मानचित्रण का गुण होता है, और यह दिखाया जा सकता है कि नीचे की छवि एक उपसमुच्चय है, जिसका अर्थ है कि प्रकार शब्दार्थ शंकु पर कोई भी परिणाम आसानी से बिना लेबल वाले ग्राफ में भी सामान्य हो जाता है। केवल सरलता से तत्वों में हेरफेर करके, शब्दार्थ शंकु के कई तत्व उत्पन्न किए जा सकते हैं। उदाहरण के लिए, चूंकि के तत्व-झंडे के लिए गैर-नकारात्मक हैं, इसलिए के तत्वों का कोई भी शंक्वाकार संयोजन का एक तत्व प्राप्त करेगा। शायद अधिक गैर-तुच्छ रूप से, के तत्वों के वर्गों का कोई भी शंक्वाकार संयोजन भी शब्दार्थ शंकु का एक तत्व प्राप्त करेगा। हालाँकि झंडे के वर्ग पाए जा सकते हैं जो मैन्युअल रूप से गैर-तुच्छ परिणामों का योग करते हैं, लेकिन अक्सर प्रक्रिया को स्वचालित करना आसान होता है। विशेष रूप से, बहुपदों के लिए फ्लैग अल्जेब्रा के लिए सम-ऑफ-स्क्वायर अनुकूलन में विचारों को अनुकूलित करना संभव है। के विस्तार में गैर-शून्य गुणांक के साथ सबसे बड़ा ध्वज होने के लिए एक वेक्टर की डिग्री को परिभाषित करें, और सभी विकल्पों पर एक वेक्टर की न्यूनतम डिग्री होने दें। इसके अलावा, सभी के लिए स्वयं को भेजने वाले कैनॉनिकल एम्बेडिंग के रूप में परिभाषित करें। ये परिभाषाएँ निम्नलिखित फ्लैग-अलजेब्रा एनालॉग को जन्म देती हैंः प्रमेय दिया गया है, तो कुछ के लिए मौजूद है यदि और केवल तभी जब एक सकारात्मक अर्ध-परिमित मैट्रिक्स ऐसा हो। इस प्रमेय के साथ, ग्राफ समरूपता समस्याओं को अब अर्ध-परिमित प्रोग्रामिंग में शिथिल किया जा सकता है जिन्हें कंप्यूटर के माध्यम से हल किया जा सकता है। उदाहरण के लिए, मेंटेल के प्रमेय को सबसे छोटा खोजने के रूप में फिर से व्यक्त किया जा सकता है। जैसा कि बहुत कम समझा गया है, इस रूप में प्रश्न पर प्रगति करना मुश्किल है, लेकिन ध्यान दें कि-झंडे और वैक्टर के वर्गों के शंकु संयोजन होते हैं, इसलिए इसके बजाय एक अर्ध-सीमित विश्राम लें। विशेष रूप से, इस बाधा के तहत कम करें कि-झंडे का एक शंकु संयोजन कहाँ है और सकारात्मक अर्ध-निश्चित है। इस नई अनुकूलन समस्या को एक सेमीडिफाइनाइट-प्रोग्रामिंग समस्या में बदला जा सकता है जिसे फिर मानक एल्गोरिदम के साथ हल किया जा सकता है। सामान्यीकरण फ्लैग अल्जेब्रा की विधि आसानी से कई ग्राफ जैसी संरचनाओं को सामान्य बनाती है। जैसा कि रेज़बोरोव ने अपने मूल लेख में लिखा था, झंडे को इसके बजाय परिमित मॉडल सिद्धांत के साथ वर्णित किया जा सकता है। ग्राफ के बजाय, केवल विधेय प्रतीकों के साथ एक सीमित संबंधपरक हस्ताक्षर में समानता के साथ कुछ गैर-आनुवंशिक सार्वभौमिक प्रथम-क्रम सिद्धांत के मॉडल का उपयोग किया जा सकता है। एक मॉडल, जो एक ग्राफ की हमारी पिछली धारणा को प्रतिस्थापित करता है, में ग्राउंड सेट होता है, जिसके तत्वों को शीर्ष कहा जाता है। अब, उप-मॉडल और मॉडल एम्बेडिंग को उपग्राफ और ग्राफ एम्बेडिंग के अनुरूप परिभाषित करते हुए, उपरोक्त सभी परिभाषाओं और प्रमेयों का लगभग सीधे मॉडल सिद्धांत की भाषा में अनुवाद किया जा सकता है। तथ्य यह है कि फ्लैग अल्जेब्रा के सिद्धांत का अच्छी तरह से सामान्यीकरण करने का मतलब है कि इसका उपयोग न केवल सरल ग्राफ में समस्याओं को हल करने के लिए किया जा सकता है, बल्कि निर्देशित ग्राफ और हाइपरग्राफ तक सीमित नहीं है। संदर्भ ग्राफ सिद्धांत