2025-11-14T13:52:11.419163

Eigenspace embeddings of imprimitive association schemes

Vidali
For a given symmetric association scheme $\mathcal{A}$ and its eigenspace $S_j$ there exists a mapping of vertices of $\mathcal{A}$ to unit vectors of $S_j$, known as the spherical representation of $\mathcal{A}$ in $S_j$, such that the inner products of these vectors only depend on the relation between the corresponding vertices; furthermore, these inner products only depend on the parameters of $\mathcal{A}$. We consider parameters of imprimitive association schemes listed as open cases in the list of parameters for quotient-polynomial graphs recently published by Herman and Maleki, and study embeddings of their substructures into some eigenspaces consistent with spherical representations of the putative association schemes. Using this, we obtain nonexistence for two parameter sets for $4$-class association schemes and one parameter sets for a $5$-class association scheme passing all previously known feasibility conditions, as well as uniqueness for two parameter sets for $5$-class association schemes.
academic

अप्राइमिटिव एसोसिएशन स्कीम्स की आइजेनस्पेस एम्बेडिंग्स

मूल जानकारी

  • पेपर ID: 2504.08733
  • शीर्षक: अप्राइमिटिव एसोसिएशन स्कीम्स की आइजेनस्पेस एम्बेडिंग्स
  • लेखक: जानोश विडाली (लुबलजाना विश्वविद्यालय, स्लोवेनिया)
  • वर्गीकरण: math.CO (संयोजन गणित)
  • प्रकाशन समय: 16 अक्टूबर 2025 को arXiv पर प्रस्तुत
  • पेपर लिंक: https://arxiv.org/abs/2504.08733

सारांश

दिए गए सममित एसोसिएशन स्कीम A\mathcal{A} और इसके आइजेनस्पेस SjS_j के लिए, एक मानचित्र मौजूद है जो A\mathcal{A} के शीर्षों को SjS_j में इकाई सदिशों में मानचित्रित करता है, जिसे A\mathcal{A} का SjS_j में गोलाकार प्रतिनिधित्व कहा जाता है, जिससे इन सदिशों का आंतरिक गुणनफल केवल संबंधित शीर्षों के बीच संबंध पर निर्भर करता है; इसके अलावा, ये आंतरिक गुणनफल केवल A\mathcal{A} के मापदंडों पर निर्भर करते हैं। यह पेपर हर्मन और मलेकी द्वारा हाल ही में प्रकाशित भागफल बहुपद ग्राफ मापदंड सूची में खुले मामलों के रूप में सूचीबद्ध अप्राइमिटिव एसोसिएशन स्कीम मापदंडों पर विचार करता है, कुछ आइजेनस्पेस में इसकी उप-संरचना एम्बेडिंग की समस्या का अध्ययन करता है, ये एम्बेडिंग्स मान्य एसोसिएशन स्कीम के गोलाकार प्रतिनिधित्व के साथ सुसंगत हैं। इस विधि का उपयोग करके, हम सभी ज्ञात व्यवहार्यता शर्तों से गुजरने वाले 4-वर्गीय एसोसिएशन स्कीम मापदंडों के दो समुच्चय और एक 5-वर्गीय एसोसिएशन स्कीम मापदंड समुच्चय की अस्तित्वहीनता को साबित करते हैं, साथ ही 5-वर्गीय एसोसिएशन स्कीम मापदंडों के दो समुच्चय की विशिष्टता को साबित करते हैं।

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

  1. समाधान की जाने वाली समस्या: यह पेपर एसोसिएशन स्कीम्स (association schemes) की अस्तित्वता और विशिष्टता की समस्या का अध्ययन करता है, विशेष रूप से अप्राइमिटिव एसोसिएशन स्कीम्स पर ध्यान केंद्रित करता है। एसोसिएशन स्कीम्स संयोजन गणित में महत्वपूर्ण वस्तुएं हैं, और इनका वर्गीकरण एक व्यापक रूप से खुली समस्या है।
  2. समस्या की महत्ता: एसोसिएशन स्कीम्स कोडिंग सिद्धांत, डिज़ाइन सिद्धांत और परिमित ज्यामिति जैसे कई क्षेत्रों के मूल संरचनाएं हैं। इन वस्तुओं का संपूर्ण वर्गीकरण इन क्षेत्रों की मूल संरचनाओं को समझने के लिए महत्वपूर्ण है। यहां तक कि दृढ़ नियमित ग्राफ (2-वर्गीय एसोसिएशन स्कीम्स) और दूरी-नियमित ग्राफ जैसे विशेष उप-परिवारों के लिए भी, संपूर्ण वर्गीकरण एक खुली समस्या बनी हुई है।
  3. मौजूदा विधियों की सीमाएं: पारंपरिक व्यवहार्यता शर्तें (जैसे हैंडशेकिंग लेम्मा, निरपेक्ष सीमाएं, क्रेइन मापदंडों की गैर-नकारात्मकता आदि) आवश्यक हैं लेकिन पर्याप्त नहीं हैं। कई मापदंड समुच्चय सभी ज्ञात व्यवहार्यता परीक्षणों से गुजरते हैं, लेकिन वास्तव में संबंधित एसोसिएशन स्कीम्स मौजूद नहीं हैं।
  4. अनुसंधान प्रेरणा: लेखक ने एक नई तकनीक विकसित की है—आइजेनस्पेस एम्बेडिंग विधि, जो एसोसिएशन स्कीम्स के गोलाकार प्रतिनिधित्व को उनके आइजेनस्पेस में अध्ययन करके मापदंड समुच्चय की व्यवहार्यता निर्धारित करती है। यह विधि विशेष रूप से अप्राइमिटिव एसोसिएशन स्कीम्स के लिए उपयुक्त है, क्योंकि उनके पास विश्लेषण के लिए छोटी उप-संरचनाएं हैं।

मुख्य योगदान

  1. आइजेनस्पेस एम्बेडिंग तकनीक विकसित की: एसोसिएशन स्कीम्स की उप-संरचना के आइजेनस्पेस में एम्बेडिंग का अध्ययन करके मापदंड समुच्चय की व्यवहार्यता निर्धारित करने के लिए एक नई विधि प्रस्तावित की।
  2. तीन अस्तित्वहीनता परिणाम साबित किए:
    • दो 4-वर्गीय एसोसिएशन स्कीम मापदंड समुच्चय: [[12, 4, 4, 24], 6, 0, 3; 0, 1; 2] और [[8, 8, 4, 24], 1, 0, 2; 2, 1; 1]
    • एक 5-वर्गीय एसोसिएशन स्कीम मापदंड समुच्चय: [[6, 18, 2, 6, 12], 1, 0, 2, 0; 0, 0, 3; 0, 1; 2]
  3. दो विशिष्टता परिणाम साबित किए:
    • 5-वर्गीय एसोसिएशन स्कीम मापदंड समुच्चय [[12, 2, 1, 12, 12], 6, 0, 4, 1; 0, 0, 1; 0, 1; 4]
    • 5-वर्गीय एसोसिएशन स्कीम मापदंड समुच्चय [[6, 4, 4, 12, 18], 3, 0, 0, 1; 0, 1, 0; 2, 0; 2]
  4. सहायक सॉफ्टवेयर उपकरण विकसित किए: SageMath के आधार पर eigenspace-embeddings सॉफ्टवेयर पैकेज विकसित किया, संबंधित एल्गोरिदम को लागू किया।
  5. हर्मन-मलेकी डेटाबेस का व्यवस्थित विश्लेषण किया: भागफल बहुपद ग्राफ मापदंड डेटाबेस पर व्यापक व्यवहार्यता परीक्षण किया, बड़ी संख्या में अव्यवहार्य मापदंड समुच्चय की पहचान की।

विधि विवरण

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

एसोसिएशन स्कीम के मापदंड समुच्चय को देखते हुए, यह निर्धारित करें कि क्या इन मापदंडों वाली एसोसिएशन स्कीम मौजूद है, और यदि मौजूद है, तो इसकी विशिष्टता निर्धारित करें। इनपुट प्रतिच्छेदन संख्याएं, आइजेनमैट्रिक्स या द्वैत आइजेनमैट्रिक्स जैसे मापदंड हैं, आउटपुट अस्तित्व/विशिष्टता का निर्णय है।

मॉडल आर्किटेक्चर

1. गोलाकार प्रतिनिधित्व सिद्धांत आधार

एसोसिएशन स्कीम A=(X,R)A = (X, R) और इसके आइजेनस्पेस SjS_j के लिए, गोलाकार प्रतिनिधित्व को परिभाषित करें:

  • प्रत्येक शीर्ष x∈Xx \in X को इकाई सदिश ux=nmjEj1xu_x = \sqrt{\frac{n}{m_j}}E_j 1_x में मानचित्रित करें
  • संबंध (x,y)∈Ri(x,y) \in R_i के लिए, ⟨ux,uy⟩=Qijmj\langle u_x, u_y \rangle = \frac{Q_{ij}}{m_j} है

2. एल्गोरिदम 1: आइजेनस्पेस एम्बेडिंग एल्गोरिदम

इनपुट: आइजेनस्पेस इंडेक्स j, संबंध मैट्रिक्स C
आउटपुट: इकाई सदिश गुणांक मैट्रिक्स U या विफलता
for x = 1 to n' do
    h ← 1
    for y = 1 to x-1 do
        d ← C_xy - Σ(k=1 to h-1) a_xk * a_yk
        if h ≤ m_j ∧ a_yh ≠ 0 then
            a_xh ← d/a_yh; h ← h+1
        else if d ≠ 0 then fail
    ||u_x||² की गणना करें और सत्यापित करें कि यह 1 के बराबर है

3. अप्राइमिटिव एसोसिएशन स्कीम्स की विशेष संरचना

गैर-तुच्छ प्राइमिटिव समुच्चय 0~\tilde{0} वाली अप्राइमिटिव एसोसिएशन स्कीम्स के लिए:

  • शीर्ष समुच्चय को समतुल्य वर्गों {Xℓ}\{X_\ell\} में विभाजित किया जाता है
  • प्रत्येक समतुल्य वर्ग पर प्रेरित उप-स्कीम समान मापदंड रखती है
  • इस संरचना का उपयोग करके छोटी उप-संरचनाओं का विश्लेषण किया जा सकता है

तकनीकी नवाचार बिंदु

  1. आइजेनस्पेस बाधाएं: यह आवश्यकता कि उप-संरचनाएं आइजेनस्पेस में एम्बेड हो सकें, पारंपरिक विधियों की तुलना में अधिक मजबूत बाधाएं प्रदान करती हैं।
  2. स्तरीय निर्माण रणनीति: छोटी उप-संरचनाओं से शुरू करके, क्रमिक रूप से विस्तारित करें, प्रत्येक चरण में एम्बेडिंग के अस्तित्व की जांच करें।
  3. कम्प्यूटेशनल बीजगणित विधि: सटीक गणना के लिए विस्तारित संख्या क्षेत्र FFF\sqrt{F} का उपयोग करें, प्रतीकात्मक गणना की जटिलता से बचें।
  4. लेम्मा 2 का अनुप्रयोग: विशिष्ट प्रकार की अप्राइमिटिव स्कीम्स के लिए, उप-संरचनाओं के बीच कनेक्शन की प्रतिबंधितता को साबित करें, जांच के लिए आवश्यक मामलों की संख्या में बहुत कमी लाएं।

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

डेटासेट

  • हर्मन-मलेकी डेटाबेस: 3-6 वर्गीय भागफल बहुपद ग्राफ के मापदंड सरणियां शामिल हैं
  • हनाकी-मियामोटो वर्गीकरण: छोटी शीर्ष संख्या वाली एसोसिएशन स्कीम्स का संपूर्ण वर्गीकरण
  • ज्ञात निर्माण: विभिन्न बीजगणितीय और ज्यामितीय निर्माणों से एसोसिएशन स्कीम्स

मूल्यांकन मेट्रिक्स

  • मापदंड समुच्चय की व्यवहार्यता (ज्ञात शर्तों को पास/विफल करना)
  • अस्तित्व (संबंधित एसोसिएशन स्कीम मौजूद/अनुपस्थित)
  • विशिष्टता (अद्वितीय/कई गैर-समरूपी स्कीम्स)

तुलना विधियां

पारंपरिक व्यवहार्यता शर्तें:

  • हैंडशेकिंग लेम्मा
  • बहुलता की पूर्णांकता
  • क्रेइन मापदंडों की गैर-नकारात्मकता
  • निरपेक्ष सीमाएं
  • निषिद्ध चतुर्भुज शर्त
  • भागफल स्कीम्स की व्यवहार्यता

कार्यान्वयन विवरण

  • SageMath कम्प्यूटेशनल बीजगणित प्रणाली के आधार पर
  • संख्या क्षेत्र गणना के लिए PARI का उपयोग करें
  • ग्राफ निर्माण और समरूपता परीक्षण के लिए nauty का उपयोग करें
  • पूर्णांक रैखिक प्रोग्रामिंग के लिए GLPK का उपयोग करें (ग्राफ रंगाई)

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

मुख्य परिणाम

अस्तित्वहीनता परिणाम

  1. QPG [[12, 4, 4, 24], 6, 0, 3; 0, 1; 2]:
    • 45 शीर्षों की 4-वर्गीय स्कीम
    • उप-संरचना कनेक्शन पैटर्न विश्लेषण के लिए लेम्मा 2 का उपयोग करें
    • पाया गया कि केवल एक 3-क्लिक कॉन्फ़िगरेशन S1S_1 में एम्बेड हो सकता है
    • लेकिन शेष शीर्षों के लिए कोई वैध एम्बेडिंग नहीं मिल सका
  2. QPG [[8, 8, 4, 24], 1, 0, 2; 2, 1; 1]:
    • 100 संभावित उप-स्कीम कॉन्फ़िगरेशन पर विचार किया
    • प्रत्येक मामले में 8000 उम्मीदवार शीर्षों की जांच की
    • कोई भी वैध इकाई सदिश प्रतिनिधित्व नहीं मिला
  3. QPG [[6, 18, 2, 6, 12], 1, 0, 2, 0; 0, 0, 3; 0, 1; 2]:
    • 45 शीर्षों की 5-वर्गीय स्कीम
    • ग्राफ निर्माण के माध्यम से 18 संभावित द्विपक्षीय ग्राफ मिले
    • इनमें से 7 को 2-आयामी उप-स्पेस में एम्बेड किया जा सकता है, लेकिन 3-क्लिक तक विस्तार करते समय सभी विफल हो गए

विशिष्टता परिणाम

  1. QPG [[12, 2, 1, 12, 12], 6, 0, 4, 1; 0, 0, 1; 0, 1; 4]:
    • 40 शीर्षों की 5-वर्गीय स्कीम
    • S1S_1 में गोलाकार प्रतिनिधित्व के माध्यम से संरचना को पूरी तरह निर्धारित किया
    • साबित किया कि यह इन मापदंडों वाली एकमात्र एसोसिएशन स्कीम है
  2. QPG [[6, 4, 4, 12, 18], 3, 0, 0, 1; 0, 1, 0; 2, 0; 2]:
    • 45 शीर्षों की 5-वर्गीय स्कीम
    • टोरस Z5×Z3×Z3Z_5 \times Z_3 \times Z_3 पर Cayley ग्राफ के रूप में वर्णित किया जा सकता है
    • स्वतः-समरूपता समूह का क्रम 77760 है

विलोपन प्रयोग

पेपर विभिन्न आयामों की आइजेनस्पेस को व्यवस्थित रूप से विश्लेषण करके विधि की प्रभावशीलता को सत्यापित करता है:

  • जब mjmˉjˉ>3\frac{m_j}{\bar{m}_{\bar{j}}} > 3 हो, तो बाधाएं आमतौर पर पर्याप्त मजबूत नहीं होती हैं
  • जब mjmˉjˉ≤3\frac{m_j}{\bar{m}_{\bar{j}}} \leq 3 हो, विशेष रूप से ≤52\leq \frac{5}{2} हो, तो बाधाएं बहुत सख्त हो जाती हैं

केस विश्लेषण

लेखक विधि को समझाने के लिए एक छोटा उदाहरण (8 शीर्षों की 3-वर्गीय स्कीम) प्रदान करते हैं:

  • इकाई सदिश गुणांक मैट्रिक्स UU का निर्माण किया
  • आंतरिक गुणनफल के माध्यम से संबंध मैट्रिक्स का पुनर्निर्माण किया
  • सत्यापित किया कि यह वास्तव में 3-घन Q3Q_3 की एसोसिएशन स्कीम से मेल खाता है

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

मुख्य अनुसंधान दिशाएं

  1. एसोसिएशन स्कीम्स वर्गीकरण: Brouwer आदि द्वारा दृढ़ नियमित ग्राफ और दूरी-नियमित ग्राफ के मापदंड तालिकाएं, Van Dam द्वारा 3-वर्गीय स्कीम्स पर अनुसंधान
  2. गोलाकार प्रतिनिधित्व अनुप्रयोग: Bannai आदि द्वारा गोलाकार कोड की विशिष्टता के लिए, Gavrilyuk और Suda का संबंधित कार्य
  3. भागफल बहुपद ग्राफ सिद्धांत: Fiol का मूल कार्य, Herman और Maleki का मापदंड डेटाबेस

इस पेपर के लाभ

  • पहली बार गोलाकार प्रतिनिधित्व को अप्राइमिटिव एसोसिएशन स्कीम्स की व्यवहार्यता अनुसंधान में व्यवस्थित रूप से लागू किया
  • कुशल कम्प्यूटेशनल विधि और सॉफ्टवेयर उपकरण विकसित किए
  • कई दीर्घकालीन खुली मापदंड समुच्चय समस्याओं को हल किया

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

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

  1. आइजेनस्पेस एम्बेडिंग विधि एसोसिएशन स्कीम्स के अनुसंधान के लिए एक शक्तिशाली नया उपकरण प्रदान करती है
  2. कई मापदंड समुच्चय जो पारंपरिक व्यवहार्यता शर्तों से गुजरते हैं, वास्तव में अव्यवहार्य हैं
  3. कुछ मापदंड समुच्चयों के लिए, संबंधित एसोसिएशन स्कीम्स की विशिष्टता को साबित किया जा सकता है

सीमाएं

  1. कम्प्यूटेशनल जटिलता: विधि की कम्प्यूटेशनल लागत शीर्ष संख्या के साथ घातीय रूप से बढ़ती है
  2. अनुप्रयोग की सीमा: मुख्य रूप से अप्राइमिटिव स्कीम्स के लिए उपयुक्त है, प्राइमिटिव स्कीम्स पर प्रभाव सीमित है
  3. आयाम सीमा: प्रभावी होने के लिए आइजेनस्पेस आयाम अपेक्षाकृत छोटा होना चाहिए

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

  1. बड़े पैमाने की समस्याओं तक विस्तार करें
  2. अधिक कुशल एल्गोरिदम विकसित करें
  3. अन्य प्रकार की संयोजन संरचनाओं पर लागू करें
  4. मशीन लर्निंग विधियों के साथ संयोजन करें

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

शक्तियां

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

कमियां

  1. स्केलेबिलिटी सीमा: विधि की कम्प्यूटेशनल जटिलता बड़े पैमाने की समस्याओं पर इसके अनुप्रयोग को सीमित करती है
  2. सैद्धांतिक विश्लेषण अपर्याप्त: विधि के अनुप्रयोग शर्तों के सैद्धांतिक लक्षण वर्णन की कमी है
  3. सामान्यता समस्या: मुख्य रूप से विशिष्ट प्रकार की अप्राइमिटिव स्कीम्स के लिए, सामान्यता में सुधार की आवश्यकता है

प्रभाव

  1. शैक्षणिक मूल्य: एसोसिएशन स्कीम्स सिद्धांत के लिए नई अनुसंधान उपकरण और विधियां प्रदान करता है
  2. व्यावहारिक मूल्य: सॉफ्टवेयर उपकरण अन्य शोधकर्ताओं द्वारा उपयोग किए जा सकते हैं
  3. क्षेत्र प्रगति: विशिष्ट समस्याओं को हल करता है, इस क्षेत्र के विकास को आगे बढ़ाता है

अनुप्रयोग परिदृश्य

  • छोटे से मध्यम आकार की अप्राइमिटिव एसोसिएशन स्कीम्स विश्लेषण
  • भागफल बहुपद ग्राफ की अस्तित्व और विशिष्टता अनुसंधान
  • कोडिंग सिद्धांत और डिज़ाइन सिद्धांत में संबंधित समस्याएं
  • परिमित ज्यामिति में संबद्ध संरचनाओं का अनुसंधान

संदर्भ

पेपर 39 महत्वपूर्ण संदर्भों का हवाला देता है, जो एसोसिएशन स्कीम्स सिद्धांत, गोलाकार प्रतिनिधित्व, कम्प्यूटेशनल विधियों आदि कई पहलुओं को कवर करते हैं, जिनमें मुख्य संदर्भ शामिल हैं:

  • Brouwer, Cohen, Neumaier की शास्त्रीय पाठ्यपुस्तक《Distance-regular graphs》
  • Bannai आदि द्वारा गोलाकार प्रतिनिधित्व विशिष्टता पर अग्रणी कार्य
  • Herman और Maleki द्वारा भागफल बहुपद ग्राफ मापदंडों पर नवीनतम अनुसंधान
  • Delsarte द्वारा एसोसिएशन स्कीम्स की बीजगणितीय विधियों पर मूलभूत कार्य