दिए गए परिधि के नए छोटे नियमित ग्राफ: पिंजरे की समस्या और उससे आगे

मूल जानकारी

• पेपर ID: 2511.07247
• शीर्षक: New small regular graphs of given girth: the cage problem and beyond
• लेखक: Geoffrey Exoo, Jan Goedgebeur, Jorik Jooken, Louis Stubbe, Tibo Van den Eede
• वर्गीकरण: math.CO (संयोजन गणित), cs.DM (असतत गणित)
• प्रकाशन तिथि: 25 नवंबर 2011
• पेपर लिंक: https://arxiv.org/abs/2511.07247

सारांश

पिंजरे की समस्या (cage problem) न्यूनतम शीर्ष संख्या वाले $(k,g)$-ग्राफ खोजने पर केंद्रित है, अर्थात् $k$-नियमित ग्राफ जिसकी परिधि (girth) $g$ हो। मूल उद्देश्य $n(k,g)$ (इस प्रकार के ग्राफ की न्यूनतम कोटि) निर्धारित करना और संबंधित चरम ग्राफ की पहचान करना है। यह पेपर पिंजरे की समस्या और इसके कई प्रकारों का कम्प्यूटेशनल दृष्टिकोण से अध्ययन करता है, चार पूरक ग्राफ जनन एल्गोरिदम विकसित करता है: उत्थान (lifts) पर आधारित संपूर्ण जनन, निषेध खोज अनुमान, पर्वत आरोहण अनुमान और विच्छेदन तकनीक। इन विधियों का उपयोग करके, शास्त्रीय पिंजरे की समस्या के 11 मामलों के लिए नई ऊपरी सीमाएं स्थापित की गई हैं: $n(3,16) \leq 936$, $n(3,17) \leq 2048$, $n(4,9) \leq 270$, $n(4,10) \leq 320$, $n(4,11) \leq 713$, $n(5,9) \leq 1116$, $n(6,11) \leq 7783$, $n(8,7) \leq 774$, $n(10,7) \leq 1608$, $n(12,7) \leq 2890$, $n(14,7) \leq 4716$। ये परिणाम कई 22 वर्ष पुरानी सीमाओं में सुधार करते हैं, विशेष रूप से $n(4,10)$ को 384 से घटाकर 320 करना एक महत्वपूर्ण सुधार है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या की परिभाषा

1. मूल समस्या: पिंजरे की समस्या $(k,g)$-पिंजरे खोजती है, अर्थात् न्यूनतम शीर्ष संख्या $n(k,g)$ वाला $k$-नियमित ग्राफ जिसकी परिधि $g$ हो। परिधि ग्राफ में सबसे छोटे चक्र की लंबाई है।
2. समस्या का महत्व:
   • सैद्धांतिक महत्व: पिंजरे चरम ग्राफ सिद्धांत के केंद्रीय अध्ययन विषय हैं, Moore सीमा जैसे शास्त्रीय सिद्धांत से घनिष्ठ रूप से संबंधित
   • व्यावहारिक अनुप्रयोग: विरल और अत्यधिक सममित संरचनाएं संचार नेटवर्क डिजाइन, त्रुटि सुधार कोड, क्रिप्टोग्राफी आदि क्षेत्रों में मूल्यवान हैं
   • नेटवर्क डिजाइन: उच्च दक्षता वाली समान सूचना प्रसार, केंद्रीय नोड पर अधिभार से बचाव, और विफलता के प्रति मजबूती प्रदान करने वाली टोपोलॉजी संरचनाएं
3. मौजूदा विधियों की सीमाएं:
   • अधिकांश पैरामीटर जोड़ी $(k,g)$ के लिए सटीक मान $n(k,g)$ अज्ञात है
   • मौजूदा सीमाएं कई वर्षों से अपरिवर्तित हैं (कुछ सीमाएं 22 वर्ष पुरानी हैं)
   • Moore ग्राफ केवल $g \in \{3,4,5,6,8,12\}$ के लिए संभव हैं
   • कम्प्यूटेशनल जटिलता $k$ और $g$ के साथ तेजी से बढ़ती है
4. अनुसंधान प्रेरणा:
   • आधुनिक कम्प्यूटेशनल क्षमता और अनुकूलन एल्गोरिदम का उपयोग करके दीर्घकालीन अपरिवर्तित सीमाओं में सुधार
   • पिंजरे की समस्या और इसके प्रकारों को संभालने के लिए व्यवस्थित कम्प्यूटेशनल विधियां विकसित करना
   • ठोस ग्राफ उदाहरण निर्माण के माध्यम से सैद्धांतिक अनुसंधान के लिए साक्ष्य प्रदान करना (जैसे सम परिधि पिंजरों की द्विपक्षीयता अनुमान)

मूल योगदान

1. एल्गोरिदम ढांचा: चार पूरक ग्राफ जनन एल्गोरिदम विकसित किए गए
   • विद्युत ग्राफ उत्थान पर आधारित बैकट्रैकिंग एल्गोरिदम (BTA)
   • निषेध खोज अनुमान (TS)
   • पर्वत आरोहण अनुमान
   • विच्छेदन तकनीक
2. शास्त्रीय पिंजरे की समस्या में सफलता: 11 नई ऊपरी सीमाएं स्थापित की गई, जिनमें शामिल हैं:
   • $n(4,10) \leq 320$ (384 से काफी कम)
   • $n(3,16) \leq 936$ (960 से सुधार)
   • $n(3,17) \leq 2048$ (2176 से सुधार)
   • पहली बार $n(4,11)$ और $n(6,11)$ के लिए गैर-तुच्छ ऊपरी सीमाएं
3. प्रकार समस्याओं में प्रगति:
   • किनारा परिधि नियमित (egr) ग्राफ: 21 नई सीमाएं (2 सटीक सीमाएं)
   • शीर्ष परिधि नियमित (vgr) ग्राफ: 29 नई सीमाएं (7 सटीक सीमाएं)
   • $(k,g,g+1)$-ग्राफ: 6 नई सीमाएं
   • $(k,g)$-स्पेक्ट्रम: 34 पहले से अनसुलझे कोटि निर्धारित किए गए
4. कम्प्यूटेशनल संसाधन और पुनरुत्पादनीयता:
   • लगभग 5 CPU वर्ष की कम्प्यूटेशनल कार्य
   • सभी कोड और डेटा GitHub पर सार्वजनिक
   • पूर्ण सत्यापन और स्वास्थ्य जांच प्रदान करता है

विधि विवरण

कार्य परिभाषा

इनपुट: नियमित डिग्री $k$, परिधि $g$, वैकल्पिक अतिरिक्त बाधाएं (जैसे शीर्ष/किनारा परिधि नियमितता)

आउटपुट: शर्तों को पूरा करने वाला न्यूनतम कोटि ग्राफ, या सुधारी गई ऊपरी सीमा $n(k,g)$

बाधाएं: ग्राफ $k$-नियमित होना चाहिए (प्रत्येक शीर्ष की डिग्री $k$) और परिधि कम से कम $g$ (सबसे छोटे चक्र की लंबाई $\geq g$)

मूल तकनीक: विद्युत ग्राफ उत्थान (Voltage Graph Lifts)

मूल सिद्धांत

आधार ग्राफ $G=(V,E)$, समूह $\Gamma$ और विद्युत असाइनमेंट $\alpha: A \rightarrow \Gamma$ ($A$ निर्देशित किनारों का समूह) दिया गया है, उत्थान ग्राफ $G_\alpha$ का शीर्ष समूह है: $V(G_\alpha) = \{u_s | u \in V, s \in \Gamma\}$

प्रत्येक चाप $(u,v) \in A$ और प्रत्येक $s \in \Gamma$ के लिए, चाप $(u_s, v_{s \cdot \alpha(a)}) \in A(G_\alpha)$ मौजूद है।

मुख्य गुण

1. नियमितता संरक्षण (अवलोकन 1): $G$ $k$-नियमित है यदि और केवल यदि $G_\alpha$ $k$-नियमित है
2. संयोजकता आवश्यक शर्त (अवलोकन 2): यदि $G$ असंयुक्त है, तो $G_\alpha$ असंयुक्त है
3. परिधि गणना (प्रस्ताव 1): $G_\alpha$ की परिधि $G$ के निर्देशित ग्राफ में सबसे छोटे बंद गैर-प्रतिवर्ती पथ (शुद्ध विद्युत $0_\Gamma$) की लंबाई के बराबर है
4. जनन वृक्ष सरलीकरण (प्रस्ताव 2): जनन वृक्ष पर सभी विद्युत को $0_\Gamma$ पर सेट किया जा सकता है बिना उत्थान ग्राफ की समरूपता वर्ग को बदले

एल्गोरिदम 1: बैकट्रैकिंग एल्गोरिदम (BTA)

संरचित बहिष्करण नियम

संरचना-आधारित बहिष्करण (विद्युत असाइनमेंट से स्वतंत्र):

1. अर्ध-किनारा बाधा: अर्ध-किनारे के अनुरूप चाप केवल क्रम 2 के समूह तत्वों को असाइन कर सकते हैं
2. जनन वृक्ष अनुकूलन: जनन वृक्ष $T$ चुनें, इसके किनारों की विद्युत को $0_\Gamma$ पर सेट करें
3. चक्र-आधारित बहिष्करण: गैर-वृक्ष किनारों के लिए, यदि विद्युत $a$ असाइन करने से लंबाई $(q+1)s$ का चक्र बनता है (जहां $a^s=0_\Gamma$) और यह लक्ष्य परिधि से कम है, तो विद्युत को बहिष्कृत करें

असाइनमेंट-आधारित बहिष्करण (आंशिक विद्युत असाइनमेंट पर निर्भर):

1. विहित जांच (एल्गोरिदम 1):
   • समूह स्वतः-समरूपता $\phi_\Gamma$ और किनारा स्वतः-समरूपता $\phi_G$ का उपयोग करें
   • केवल शब्दकोशीय रूप से न्यूनतम प्रतिनिधि रखें
   • यदि आंशिक असाइनमेंट विहित नहीं है, तो इसके सभी पूर्णन को बहिष्कृत किया जा सकता है
2. वृद्धिशील परिधि सत्यापन (एल्गोरिदम 2):
   • केवल नई असाइनमेंट किनारों का उपयोग करने वाले बंद गैर-प्रतिवर्ती पथों की जांच करें
   • वृद्धिशील संपत्ति का उपयोग करके दक्षता में सुधार करें

एल्गोरिदम प्रवाह (एल्गोरिदम 3)

BTA(G, Γ, g_min):
  1. संरचनात्मक जांच निष्पादित करें, संभव विद्युत समूह N निर्धारित करें
  2. विद्युत असाइनमेंट को पुनरावर्ती रूप से करें:
     - प्रत्येक उपयोगी चाप d के लिए, N(d) में प्रत्येक विद्युत का प्रयास करें
     - परिधि जांच और विहित जांच लागू करें
     - यदि पास हो, अगले चाप को पुनरावर्ती रूप से संभालें
     - बैकट्रैक करते समय स्थिति को पुनः स्थापित करें
  3. पूर्ण असाइनमेंट के बाद, उत्थान ग्राफ का निर्माण करें और फ़िल्टर करें

एल्गोरिदम 2: निषेध खोज (TS)

प्रेरणा

BTA बड़े उदाहरणों के लिए कम्प्यूटेशनल ओवरहेड बड़ा है, TS अनुमान के माध्यम से आशाजनक विद्युत असाइनमेंट की खोज करता है।

मुख्य घटक

पड़ोस परिभाषा: बिल्कुल एक किनारे के अनुरूप समूह तत्व को बदलने वाले सभी वैकल्पिक असाइनमेंट

लागत फ़ंक्शन:

1. परिधि-आधारित ($c_{girth}$): $c_{girth} = \sum_{i=1}^m f(q_i, a_i), \quad f(q,a) = \begin{cases} \frac{1}{q \cdot \text{Ord}(a)} & \text{यदि } \text{Ord}(a) \neq 1 \\ C & \text{अन्यथा} \end{cases}$ जहां $C$ बड़ी दंड स्थिरांक है, $m$ नमूना पथों की संख्या है
2. नियमितता-आधारित ($c_{reg}$): $c_{reg} = \min\left[\text{Var}(f_V), \text{Var}(f_D)\right]$ जहां $f_V$ और $f_D$ क्रमशः शीर्ष और चाप परिधि चक्रों में दिखाई देने की आवृत्ति हैं

निषेध सूची: हाल के संशोधन संचालन को संग्रहीत करता है, तत्काल वापसी को रोकता है, लंबाई $3|\Gamma|$

विक्षोभ तंत्र: जब स्थानीय इष्टतम में फंस जाए, तो यादृच्छिक संशोधन लागू करके बाहर निकलें

हाइपरपैरामीटर सेटिंग (तालिका 1)

• किनारा/समूह स्वतः-समरूपता संख्या सीमा: 200/2000
• BTA और TS समय सीमा: प्रत्येक 20 सेकंड/उदाहरण
• पड़ोस न्यूनतम परिधि: $g_{nbr} = g_{min} - 2$ (परिधि समस्या) या $g_{nbr} = g_{min}$ (नियमितता समस्या)

एल्गोरिदम 3: पर्वत आरोहण अनुमान

पूर्ववर्ती विधियों से अंतर: आधार ग्राफ और विद्युत असाइनमेंट दोनों को एक साथ खोजता है

प्रवाह:

1. $n$ अलग-थलग शीर्षों से शुरू करें
2. प्रत्येक पुनरावृत्ति में:
   • सभी संभावित जोड़े जाने वाले चाप जोड़ी और विद्युत असाइनमेंट $t \in T(G)$ पर विचार करें
   • $|T(G_t)|$ को अधिकतम करने वाले संशोधन को चुनें (लालची रणनीति)
3. जांचें कि क्या उत्थान ग्राफ रिकॉर्ड तोड़ता है

एल्गोरिदम 4: विच्छेदन तकनीक

मूल विचार: पहले से ज्ञात छोटे $(k,g+1)$-ग्राफ से शीर्ष हटाएं, फिर $k$-नियमित पूरा करने के लिए किनारे जोड़ें

विशिष्ट रणनीति:

1. परिधि 7, सम डिग्री $8 \leq k \leq 14$:
   • $(k,8)$-पिंजरे से दूरी 4 वाले दो शीर्ष $u,v$ हटाएं
   • $N_1(u), N_1(v), N_2(u,v)$ हटाएं
   • विच्छेदन समूह आकार: $3k$ (de Ruiter और Biggs के $3k-1$ से सुधार)
2. परिधि 11:
   • $(4,12)$-पिंजरे से: दूरी 6 वाले $u,v$ हटाएं, $N_1(u), N_1(v), N_3(u,v)$ और $N_2(u) \cap N_4(v)$ में एक शीर्ष हटाएं, $3k+3$ शीर्ष विच्छेदित करें
   • $(6,12)$-पिंजरे से: समान रणनीति, $5k-1$ शीर्ष विच्छेदित करें

प्रायोगिक सेटअप

कम्प्यूटेशनल संसाधन

• कुल कम्प्यूटेशन: लगभग 5 CPU वर्ष
• बुनियादी ढांचा: Flemish Supercomputer Center (VSC)
• कार्यान्वयन भाषा: C++ पर आधारित (अनुमानित, स्पष्ट रूप से नहीं कहा गया)

आधार ग्राफ और समूहों का जनन

1. समूह: GAP सिस्टम का उपयोग करके सभी क्रम $n < 1024$ के गैर-समरूपी समूह जनित करें
2. आधार ग्राफ:
   • multigraph जनक का विस्तार (multigraph+)
   • समानांतर किनारों, पाश और अर्ध-किनारों वाले संयुक्त नियमित ग्राफ जनित करें
   • Nauty का उपयोग करके समरूपी ग्राफ हटाएं

सत्यापन रणनीति

1. इनपुट सत्यापन:
   • समूह: सीधे GAP से प्राप्त
   • आधार ग्राफ: pregraph जनक के साथ तुलना (कोटि 13 तक)
2. अनुकूलन सही्यता:
   • प्रत्येक अनुकूलन को अलग से अक्षम करें (ग्राफ स्वतः-समरूपता, समूह स्वतः-समरूपता, परिधि सीमा)
   • जनित गैर-समरूपी उत्थान ग्राफ संख्या की सामंजस्य जांचें
3. संपूर्णता सत्यापन:
   • तीन स्वतंत्र कार्यान्वयन के साथ तुलना:
     • $K_{1,3}$ आधार निर्माण
     • Gray और Theta ग्राफ उत्थान
     • ब्लॉक चक्रीय ग्राफ जनक (चक्रीय समूह उत्थान के समतुल्य)
   • सभी मामलों में आउटपुट पूरी तरह से सामंजस्यपूर्ण

फ़िल्टरिंग प्रवाह

1. संयोजकता जांच
2. समरूपता फ़िल्टरिंग: Nauty का उपयोग करके विहित प्रतिनिधित्व निर्माण करें
3. परिधि और नियमितता सत्यापन: 29 में एल्गोरिदम का उपयोग करें

प्रायोगिक परिणाम

मुख्य परिणाम: शास्त्रीय पिंजरे की समस्या (तालिका 2)

महत्वपूर्ण सुधार

विच्छेदन तकनीक के परिणाम

• $(8,7) \leq 774$ (777 से 3 शीर्ष सुधार)
• $(10,7) \leq 1608$ (1611 से 3 शीर्ष सुधार)
• $(12,7) \leq 2890$ (2893 से 3 शीर्ष सुधार)
• $(14,7) \leq 4716$ (4719 से 3 शीर्ष सुधार)

मुख्य खोजें

1. $(4,10)$ की सफलता: 384 से 320 तक, 16.7% की कमी, सबसे आश्चर्यजनक सुधार
2. द्विपक्षीयता साक्ष्य: नए $(3,16)$ और $(4,10)$ ग्राफ दोनों द्विपक्षीय हैं, "सम परिधि पिंजरे द्विपक्षीय होने चाहिए" अनुमान का समर्थन करते हैं
3. निर्माण विवरण (चित्र 4):
   • $(3,16)$: समूह $C_{13} \rtimes C_9$ (क्रम 117), आधार ग्राफ 8 शीर्ष
   • $(4,10)$: समूह $C_5 \times D_4$ (क्रम 40), आधार ग्राफ 8 शीर्ष

प्रकार समस्याओं के परिणाम

किनारा परिधि नियमित ग्राफ (तालिका 3)

• 21 नई सीमाएं, जिनमें 2 सटीक सीमाएं (ऊपरी और निचली सीमा समान):
  • $n(4,5,4) = 30$ (नई निर्धारित)
  • कई $(6,5,\lambda_e)$ मामलों के लिए पहली बार ऊपरी सीमा

शीर्ष परिधि नियमित ग्राफ (तालिका 4)

• 29 नई सीमाएं, जिनमें 7 सटीक सीमाएं:
  • $n(3,7,1) = n(3,7,2) = n(3,7,4) = 42$
  • $n(4,5,1) = n(4,5,6) = n(4,5,7) = 30$
  • कई $(4,6,\lambda_v)$ मामलों में बड़ा सुधार

$(k,g)$-स्पेक्ट्रम (तालिका 5)

• 34 पहले से अनसुलझे कोटि निर्धारित किए गए
• मुख्य रूप से केंद्रित:
  • $(3,11)$ और $(3,12)$: 7 नए कोटि
  • $(4,7)$ और $(4,8)$: 12 नए कोटि
  • $(5,7)$: 24 नए कोटि (184 से 256 तक)

$(g+1)$-चक्र-मुक्त ग्राफ (तालिका 6)

• 6 नई सीमाएं:
  • $n(3,11,12) \leq 228$ (272 से सुधार)
  • $n(3,13,14) \leq 600$ (800 से सुधार)
  • $n(3,15,16) \leq 1760$ (2162 से सुधार)

एल्गोरिदम दक्षता विश्लेषण

समय आवंटन रणनीति

• प्रत्येक आधार ग्राफ-समूह संयोजन: BTA 20 सेकंड, TS 20 सेकंड
• TS प्रारंभिक समाधान खोज: 2 सेकंड
• ग्राफ स्वतः-समरूपता खोज: 2 सेकंड

एल्गोरिदम पूरकता

1. BTA: छोटे उदाहरणों के लिए पूर्ण संपूर्णता, पूर्ण खोज सुनिश्चित करता है
2. TS: बड़े उदाहरणों के लिए अनुमान नमूना, अच्छी स्केलेबिलिटी
3. पर्वत आरोहण: आधार ग्राफ और असाइनमेंट दोनों को अनुकूलित करता है, लचीलापन अधिक
4. विच्छेदन: ज्ञात बड़े ग्राफ का उपयोग करता है, लक्षित दृष्टिकोण

संबंधित कार्य

शास्त्रीय पिंजरे की समस्या अनुसंधान

1. सैद्धांतिक सीमाएं:
   • Moore सीमा (1963): मूल निचली सीमा
   • Sauer (1967): $n(k,g) < n(k,g+1)$ असमानता
   • Wong (1982): पिंजरे समीक्षा
2. निर्माण विधियां:
   • Balaban (1972-1973): $(3,10)$ और $(3,11)$ पिंजरे
   • Benson (1966): $(k,12)$ पिंजरे
   • Biggs श्रृंखला कार्य: कई छोटी परिधि ग्राफ
3. कम्प्यूटेशनल विधियां:
   • McKay आदि (1998): पिंजरों के लिए तेजी से बैकट्रैकिंग
   • Exoo (2002-2020): विद्युत ग्राफ तकनीक
   • de Ruiter & Biggs (2015): पूर्णांक प्रोग्रामिंग और विच्छेदन

उत्थान सिद्धांत

• Gross & Tucker (1987): टोपोलॉजिकल ग्राफ सिद्धांत आधार
• Exoo & Jajcay (2011): विद्युत ग्राफ उत्थान की परिधि सिद्धांत
• यह पेपर: व्यवस्थित अनुकूलन और अनुमान विधियों का विस्तार

प्रकार समस्याएं

1. परिधि नियमित ग्राफ:
   • Jajcay आदि (2018): किनारा परिधि नियमित ग्राफ
   • Jajcay आदि (2024): शीर्ष परिधि नियमित ग्राफ
   • Goedgebeur & Jooken (2025): संपूर्ण जनन
2. स्पेक्ट्रम समस्या:
   • Eze आदि (2025): $(k,g)$-स्पेक्ट्रम की सिद्धांत और कम्प्यूटेशनल विधियां
3. छोटे चक्र-मुक्त ग्राफ:
   • Eze आदि (2026): $(k,g,g+1)$-ग्राफ और पिंजरे समस्या से संबंध

इस पेपर के लाभ

1. व्यवस्थित ढांचा: पिंजरे समस्या और कई प्रकारों को एकीकृत रूप से संभालता है
2. एल्गोरिदम पूरकता: चार विधियां विभिन्न आकार और विशेषताओं को कवर करती हैं
3. महत्वपूर्ण सुधार: दीर्घकालीन रिकॉर्ड तोड़ता है
4. खुले संसाधन: कोड और डेटा पूरी तरह से सार्वजनिक

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

1. शास्त्रीय पिंजरे की समस्या में सफलता:
   • 11 नई ऊपरी सीमाएं, जिनमें $(4,10)$ सबसे महत्वपूर्ण सुधार (384→320)
   • कुछ सीमाएं 22 वर्ष बाद पहली बार सुधारी गई
   • पहली बार $(4,11)$ और $(6,11)$ के लिए गैर-तुच्छ ऊपरी सीमाएं
2. प्रकार समस्याओं में प्रगति:
   • किनारा/शीर्ष परिधि नियमित ग्राफ: 50 नई सीमाएं (9 सटीक सीमाएं)
   • $(k,g)$-स्पेक्ट्रम: 34 नई निर्धारित कोटि
   • $(g+1)$-चक्र-मुक्त ग्राफ: 6 सुधारी गई सीमाएं
3. पद्धति योगदान:
   • उत्थान पर आधारित व्यवस्थित एल्गोरिदम ढांचा
   • संरचित और असाइनमेंट-आधारित बहिष्करण नियम
   • अनुमान और संपूर्ण विधियों का प्रभावी संयोजन

सीमाएं

1. कम्प्यूटेशनल जटिलता:
   • बड़े $(k,g)$ पैरामीटर अभी भी कठिन हैं
   • बड़ी कम्प्यूटेशनल संसाधन आवश्यकता (5 CPU वर्ष)
   • अनुमान विधियां इष्टतम समाधान खोजने की गारंटी नहीं देती
2. विधि प्रयोज्यता सीमा:
   • उत्थान विधि उपयुक्त आधार ग्राफ और समूह के अस्तित्व पर निर्भर करती है
   • विच्छेदन तकनीक को ज्ञात बड़े ग्राफ की आवश्यकता है
   • कुछ पैरामीटर संयोजन में सुधार नहीं हुआ (जैसे $(3,9)$, $(4,7)$ आदि ज्ञात पिंजरे)
3. सैद्धांतिक अंतराल:
   • अधिकांश मामलों में ऊपरी-निचली सीमा में बड़ा अंतर
   • नई निचली सीमा में सुधार नहीं दिया गया
   • कुछ पैरामीटरों के लिए ऊपरी सीमा अभी भी "?" (अज्ञात) चिह्नित है
4. हाइपरपैरामीटर संवेदनशीलता:
   • समय सीमा, निषेध सूची आकार आदि को अनुभव से समायोजित करना पड़ता है
   • हाइपरपैरामीटर अनुकूलन का व्यवस्थित अध्ययन नहीं किया गया

भविष्य की दिशाएं

1. सैद्धांतिक दिशा:
   • नए निर्माणों से अनंत परिवार प्राप्त करना
   • Moore सीमा और इसके प्रकारों में सुधार
   • सम परिधि पिंजरों की द्विपक्षीयता अनुमान को साबित या खंडित करना
2. एल्गोरिदम सुधार:
   • अधिक कुशल परिधि गणना एल्गोरिदम विकसित करना
   • मशीन लर्निंग-सहायक अनुमान डिजाइन की खोज
   • आधुनिक बहु-कोर आर्किटेक्चर के लिए एल्गोरिदम समांतरीकरण
3. विच्छेदन तकनीक का सामान्यीकरण:
   • विच्छेदन समूह चयन रणनीति का व्यवस्थितकरण
   • अधिक $(k,g)$ पैरामीटर जोड़ियों तक विस्तार
   • विच्छेदन विधि की प्रभावशीलता का सैद्धांतिक विश्लेषण
4. अनुप्रयोग अन्वेषण:
   • नई खोजी गई ग्राफों को नेटवर्क डिजाइन में लागू करना
   • त्रुटि सुधार कोड में अनुप्रयोग की खोज
   • क्रिप्टोग्राफी संबंधित गुणों का अनुसंधान

गहन मूल्यांकन

मजबूत पहलू

1. महत्वपूर्ण प्रायोगिक योगदान:
   • 22 वर्ष पुरानी रिकॉर्ड तोड़ी, विशेष रूप से $(4,10)$ में बड़ा सुधार
   • बड़ी संख्या में ठोस निर्माण प्रदान किए, सैद्धांतिक अनुसंधान के लिए सामग्री
   • कुछ पैरामीटरों के लिए पहली बार गैर-तुच्छ सीमाएं
2. पद्धति नवाचार:
   • व्यवस्थित बहिष्करण नियम: संरचित और असाइनमेंट-आधारित बहिष्करण खोज स्थान को काफी कम करते हैं
   • एल्गोरिदम पूरकता: BTA, TS, पर्वत आरोहण और विच्छेदन विभिन्न परिस्थितियों को कवर करते हैं
   • वृद्धिशील सत्यापन: एल्गोरिदम 2 की वृद्धिशील परिधि जांच दक्षता में सुधार करती है
   • विहित जांच: समरूपता का उपयोग करके अनावश्यक गणना से बचना
3. प्रायोगिक डिजाइन कठोरता:
   • बहु-स्तरीय सत्यापन रणनीति (इनपुट, अनुकूलन, संपूर्णता)
   • तीन स्वतंत्र कार्यान्वयन के साथ तुलना
   • विस्तृत हाइपरपैरामीटर सेटिंग विवरण
   • पूर्ण पुनरुत्पादनीयता समर्थन
4. अनुसंधान व्यापकता:
   • केवल शास्त्रीय समस्या पर नहीं, चार प्रकारों का व्यवस्थित अध्ययन
   • कई प्रकारों के लिए पहली बार ऊपरी सीमाएं स्थापित
   • एकीकृत ढांचा विभिन्न समस्याओं को संभालता है
5. खुली विज्ञान अभ्यास:
   • कोड और डेटा पूरी तरह से सार्वजनिक (GitHub)
   • ग्राफ House of Graphs डेटाबेस में शामिल
   • सत्यापन योग्य प्रमाण पत्र (निर्मित ग्राफ)

कमजोरियां

1. सीमित सैद्धांतिक गहराई:
   • मुख्य रूप से कम्प्यूटेशनल/प्रायोगिक कार्य, गहरे सैद्धांतिक अंतर्दृष्टि की कमी
   • नई निचली सीमा या सैद्धांतिक विश्लेषण नहीं दिया गया
   • कुछ पैरामीटरों में सुधार क्यों महत्वपूर्ण है इसकी सैद्धांतिक व्याख्या नहीं
2. विधि पूर्णता:
   • अनुमान विधियां (TS, पर्वत आरोहण) पूर्ण गारंटी नहीं देती
   • हाइपरपैरामीटर चयन अनुभव पर निर्भर, व्यवस्थित अध्ययन नहीं
   • विभिन्न एल्गोरिदम के सैद्धांतिक गारंटी या अभिसरण विश्लेषण नहीं
3. प्रायोगिक रिपोर्ट विवरण:
   • विभिन्न एल्गोरिदम के विशिष्ट योगदान की रिपोर्ट नहीं
   • चलने के समय का विस्तृत विश्लेषण नहीं
   • विफल मामलों या कठिन उदाहरणों की चर्चा नहीं
4. स्केलेबिलिटी समस्याएं:
   • बड़े $k$ और $g$ के लिए विधि व्यवहार्यता स्पष्ट नहीं
   • पैरामीटर वृद्धि के साथ कम्प्यूटेशनल संसाधन आवश्यकता के नियम विश्लेषण नहीं
   • कुछ परिणाम "≥100" चिह्नित हैं जो पूर्ण अन्वेषण नहीं दर्शाता
5. लेखन संगठन:
   • तकनीकी विवरण घने हैं, गैर-विशेषज्ञों के लिए पठनीयता चुनौतीपूर्ण
   • कुछ एल्गोरिदम विवरण अधूरे हैं (जैसे एल्गोरिदम 4 के लिए छद्मकोड नहीं)
   • परिणाम तालिकाएं कई हैं लेकिन एकीकृत सारांश विश्लेषण की कमी

प्रभाव

1. शैक्षणिक प्रभाव:
   • उच्च: पिंजरे समस्या शास्त्रीय चरम ग्राफ सिद्धांत समस्या है, दीर्घकालीन रिकॉर्ड सुधार महत्वपूर्ण है
   • 57-Moore ग्राफ जैसी प्रसिद्ध खुली समस्याओं के लिए अप्रत्यक्ष अनुसंधान मार्ग
   • विधि अन्य चरम ग्राफ समस्याओं तक सामान्यीकृत हो सकती है
2. व्यावहारिक मूल्य:
   • मध्यम: नए ग्राफ नेटवर्क टोपोलॉजी डिजाइन, त्रुटि सुधार कोड में उपयोगी
   • खुला स्रोत उपकरण अन्य शोधकर्ताओं के लिए उपलब्ध
   • एल्गोरिदम ढांचा संबंधित संयोजन अनुकूलन समस्याओं पर लागू हो सकता है
3. पुनरुत्पादनीयता:
   • उत्कृष्ट: पूर्ण कोड और डेटा सार्वजनिक
   • विस्तृत सत्यापन रणनीति विश्वसनीयता बढ़ाती है
   • ठोस निर्माण स्वतंत्र रूप से सत्यापित हो सकते हैं
4. अनुवर्ती अनुसंधान संभावना:
   • नए निर्माण अनंत परिवार की खोज को प्रेरित कर सकते हैं
   • एल्गोरिदम ढांचा अन्य ग्राफ जनन समस्याओं पर लागू हो सकता है
   • प्रकार समस्याओं के पहले परिणाम नई अनुसंधान दिशाएं खोलते हैं

प्रयोज्य परिदृश्य

1. सीधे अनुप्रयोग:
   • नेटवर्क डिजाइन में छोटे उच्च परिधि नियमित ग्राफ की आवश्यकता
   • LDPC कोड जैसे त्रुटि सुधार कोड निर्माण
   • कुंजी साझाकरण जैसे क्रिप्टोग्राफी अनुप्रयोग
2. अनुसंधान उपकरण:
   • चरम ग्राफ सिद्धांत की कम्प्यूटेशनल प्रयोग
   • ग्राफ समरूपता और विहित रूपांतरण एल्गोरिदम परीक्षण
   • संयोजन अनुकूलन अनुमान के लिए बेंचमार्क परीक्षण
3. शिक्षण संसाधन:
   • शुद्ध गणित में कम्प्यूटेशनल विधियों के अनुप्रयोग का प्रदर्शन
   • एल्गोरिदम डिजाइन और अनुकूलन के केस अध्ययन
   • खुली विज्ञान और पुनरुत्पादनीय अनुसंधान के उदाहरण
4. सामान्यीकरण क्षेत्र:
   • अन्य चरम ग्राफ समस्याएं (Ramsey संख्या, Turán समस्या आदि)
   • बाधा संतुष्टि समस्याएं
   • संयोजन डिजाइन और कोडिंग सिद्धांत

संदर्भ (चयनित)

1. मूल सिद्धांत:
   • 45 Sachs (1963): $(k,g)$-ग्राफ सभी $k \geq 2, g \geq 3$ के लिए अस्तित्व का प्रमाण
   • 31 Gross & Tucker (1987): टोपोलॉजिकल ग्राफ सिद्धांत और उत्थान सिद्धांत
   • 47 Wong (1982): पिंजरे व्यापक समीक्षा
2. कम्प्यूटेशनल विधियां:
   • 24 Exoo आदि (2011): $(3,11)$ और $(4,7)$ पिंजरों की कम्प्यूटेशनल निर्धारण
   • 38 McKay आदि (1998): तेजी से बैकट्रैकिंग सिद्धांत
   • 15 de Ruiter & Biggs (2015): पूर्णांक प्रोग्रामिंग विधि
3. नवीनतम प्रगति:
   • 22 Exoo & Jajcay (2011): विद्युत ग्राफ उत्थान की परिधि सिद्धांत
   • 29 Goedgebeur & Jooken (2025): किनारा परिधि नियमित ग्राफ का संपूर्ण जनन
   • 34 Jajcay आदि (2024): शीर्ष परिधि नियमित ग्राफ
4. उपकरण:
   • 37 McKay & Piperno (2014): Nauty ग्राफ समरूपता सॉफ्टवेयर
   • 27 GAP सिस्टम: समूह सिद्धांत गणना
   • 12 House of Graphs: ग्राफ डेटाबेस

समग्र मूल्यांकन: यह उच्च गुणवत्ता वाला कम्प्यूटेशनल संयोजन गणित पेपर है जो व्यवस्थित एल्गोरिदम विकास और बड़े पैमाने पर कम्प्यूटेशनल प्रयोग के माध्यम से शास्त्रीय पिंजरे समस्या और इसके प्रकारों पर महत्वपूर्ण प्रायोगिक प्रगति प्राप्त करता है। पद्धति में नवाचार (विशेष रूप से बहिष्करण नियम और एल्गोरिदम पूरकता) और कठोर सत्यापन रणनीति मुख्य शक्तियां हैं। हालांकि सैद्धांतिक गहराई सीमित है, लेकिन इसके प्रायोगिक योगदान, खुली विज्ञान अभ्यास और क्षेत्र को आगे बढ़ाने के प्रभाव इसे इस क्षेत्र का महत्वपूर्ण योगदान बनाते हैं। चरम ग्राफ सिद्धांत, ग्राफ एल्गोरिदम या संयोजन अनुकूलन में काम करने वाले शोधकर्ताओं के लिए, यह पेपर मूल्यवान विधियां और संसाधन प्रदान करता है।