पाले ग्राफ

Paley graph
The Paley graph of order 13
Named after	Raymond Paley
Vertices	q ≡ 1 mod 4, q prime power
Edges	q(q − 1)/4
Diameter	2
Properties	Strongly regular Conference graph Self-complementary
Notation	QR(q)
Table of graphs and parameters

गणित में, पाले ग्राफ़ घने ग्राफ़ अप्रत्यक्ष ग्राफ़ होते हैं जो एक उपयुक्त परिमित क्षेत्र के सदस्यों से तत्वों के जोड़े को जोड़कर बनाए जाते हैं जो द्विघात अवशेषों से भिन्न होते हैं। पाले ग्राफ़ सम्मेलन ग्राफ के एक अनंत परिवार का निर्माण करते हैं, जो सममित सम्मेलन मैट्रिक्स के एक अनंत परिवार का उत्पादन करते हैं। पाले ग्राफ़ ग्राफ़-सैद्धांतिक उपकरण को द्विघात अवशेषों के संख्या सिद्धांत पर प्रयुक्त करने की अनुमति देते हैं, और इसमें रोचक गुण होते हैं जो उन्हें ग्राफ़ सिद्धांत में अधिक उपयोगी बनाते हैं।

रेमंड पाले के नाम पर पाले ग्राफ रखे गए हैं। वे द्विघात अवशेषों से हैडमार्ड मैट्रिक्स के निर्माण के लिए पाले निर्माण से निकटता से संबंधित हैं (पाले 1933).

द्वारा स्वतंत्र रूप से उन्हें ग्राफ के रूप में प्रस्तुत किया गया था साक्स (1962) और Erdős & Rényi (1963). होर्स्ट सैक्स उनकी आत्म-पूरक गुणों के लिए उनमें रुचि रखते थे, जबकि पॉल एर्डोस | एर्डोस और अल्फ्रेड रेनी | रेनी ने उनकी समरूपता का अध्ययन किया।

पाले ने पाले को डिग्राफ दिया रेखांकन के निर्देशित ग्राफ़ एनालॉग्स हैं जो एंटीसिमेट्रिक कॉन्फ़्रेंस मैट्रिक्स उत्पन्न करते हैं। द्वारा उनका परिचय कराया गया ग्राहम & स्पेंसर (1971) (साक्स, एर्डोस और रेनी से स्वतंत्र) टूर्नामेंट (ग्राफ सिद्धांत) के निर्माण के एक विधियों के रूप में एक ऐसी संपत्ति के साथ जिसे पहले केवल रैंडम टूर्नामेंट द्वारा आयोजित किया जाता था: एक पाले डिग्राफ में, कोने के हर छोटे उपसमुच्चय पर किसी अन्य शीर्ष का प्रभुत्व होता है .

परिभाषा

q को एक प्रमुख शक्ति होने दें q = 1 (मॉड 4)। अर्थात्, q को या तो एक पायथागॉरियन प्राइम (1 मॉड 4 के अनुरूप एक प्राइम सर्वांगसम) की मनमानी शक्ति या विषम गैर-पाइथागोरस प्राइम की एक सम शक्ति होनी चाहिए। q के इस विकल्प का अर्थ है कि अद्वितीय परिमित क्षेत्र 'F_q' में_q क्रम q का, तत्व −1 का एक वर्गमूल है।

अब V = F_q को जाने

$E=\left\{\{a,b\}\ :\ a-b\in (\mathbf {F} _{q}^{\times })^{2}\right\}$.

यदि एक जोड़ी {a, b} को E में सम्मिलित किया गया है, तो इसे इसके दो तत्वों के क्रम में सम्मिलित किया गया है। के लिए, a − b = −(b − a), और  −1 एक वर्ग है, जिससे यह पता चलता है कि a − b एक वर्ग है अगर और केवल अगर b − a एक वर्ग है।

परिभाषा के अनुसार G = (V, E) क्रम q का पाले ग्राफ़ है।

उदाहरण

q = 13 के लिए, फ़ील्ड 'F'_q केवल पूर्णांक अंकगणितीय मॉड्यूलो 13 है। वर्गमूल मॉड 13 वाली संख्याएँ हैं:

• ±1 (+1 के लिए वर्गमूल ±1, −1 के लिए ±5)
• ±3 (वर्गमूल +3 के लिए ±4, −3 के लिए ±6)
• ±4 (वर्गमूल +4 के लिए ±2, −4 के लिए ±3)।

इस प्रकार, पाले ग्राफ में, हम रेंज [0,12] में प्रत्येक पूर्णांक के लिए एक शीर्ष बनाते हैं, और प्रत्येक ऐसे पूर्णांक x को छह पड़ोसियों से जोड़ते हैं: x ± 1 (mod 13), x ± 3 (mod 13) , और x ± 4 (मॉड 13) है।

गुण

पाले ग्राफ़ स्व-पूरक ग्राफ़ हैं | स्व-पूरक: किसी भी पाले ग्राफ़ का पूरक इसके लिए आइसोमॉर्फिक है। एक समरूपता मानचित्रण के माध्यम से है जो एक शीर्ष x को xk (mod q) तक ले जाती है, जहाँ k कोई भी गैर-अवशेष modq है (Sachs 1962).

पाले ग्राफ दृढ़ता से नियमित ग्राफ हैं, पैरामीटर के साथ

$srg\left(q,{\tfrac {1}{2}}(q-1),{\tfrac {1}{4}}(q-5),{\tfrac {1}{4}}(q-1)\right).$

यह वास्तव में इस तथ्य से अनुसरण करता है कि ग्राफ सममित ग्राफ है और | चाप-सकर्मक और स्व-पूरक है। इसके अतिरिक्त, पाले ग्राफ़ कॉन्फ़्रेंस ग्राफ़ के एक अनंत परिवार का निर्माण करते हैं।

पाले रेखांकन के आइजन वैल्यू ​​​​हैं ${\tfrac {1}{2}}(q-1)$ (बहुलता 1 के साथ) और ${\tfrac {1}{2}}(-1\pm {\sqrt {q}})$ (दोनों बहुलता के साथ ${\tfrac {1}{2}}(q-1)$). उन्हें द्विघात गॉस राशि का उपयोग करके या दृढ़ता से नियमित रेखांकन के सिद्धांत का उपयोग करके गणना की जा सकती है।

यदि q प्रधान है, तो पाले ग्राफ का चीजर स्थिरांक (ग्राफ सिद्धांत) i(G) निम्नलिखित सीमाओं को पूरा करने के लिए जाना जाता है:

${\frac {q-{\sqrt {q}}}{4}}\leq i(G)\leq {\sqrt {\left(q+{\sqrt {q}}\right)\left({\frac {q-{\sqrt {q}}}{2}}\right)}}.$

जब q मुख्य होता है, तो संबद्ध पाले ग्राफ एक हैमिल्टनियन चक्र परिसंचारी ग्राफ होता है।

पाले ग्राफ़ अर्ध-यादृच्छिक (चुंग एट अल। 1989) हैं: प्रत्येक संभावित स्थिर-क्रम ग्राफ़ की संख्या एक पाले ग्राफ़ के सबग्राफ के रूप में होती है (बड़े q के लिए सीमा में) यादृच्छिक ग्राफ़ के समान, और बड़े वर्टिकल के सेट में लगभग उतने ही किनारे होते हैं जितने कि वे रैंडम ग्राफ़ में होते हैं।

अनुप्रयोग

• ऑर्डर 9 का पाले ग्राफ एक स्थानीय रैखिक ग्राफ, एक रूक का ग्राफ और 3-3 डुओप्रिज्म का ग्राफ है।
• आदेश 13 के पाले ग्राफ में पुस्तक की मोटाई 4 और कतार संख्या 3 है (वोल्ज़ 2018).
• ऑर्डर 17 का पाले ग्राफ अद्वितीय सबसे बड़ा ग्राफ G है जैसे कि न तो G और न ही इसके पूरक में एक पूर्ण 4-वर्टेक्स सबग्राफ (इवांस एट अल। 1981) सम्मिलित है। यह इस प्रकार है कि रैमसे सिद्धांत आर (4, 4) = 18।
• ऑर्डर 101 का पाले ग्राफ वर्तमान में सबसे बड़ा ज्ञात ग्राफ G है जैसे कि न तो G और न ही इसके पूरक में एक पूर्ण 6-वर्टेक्स सबग्राफ होता है।
• सासुकरा एट अल। (1993) हॉरोक्स-ममफोर्ड बंडल के निर्माण को सामान्य बनाने के लिए पाले ग्राफ का उपयोग करें।

पाले डिग्राफ

q को एक प्रमुख पॉवर होने दें q = 3 (मॉड 4)। इस प्रकार, कोटि q, F_q के परिमित क्षेत्र का -1 का कोई वर्गमूल नहीं है। यद्यपि, F_q के अलग-अलग तत्वों की प्रत्येक जोड़ी (a, b) के लिए, या तो a - b या b - a, लेकिन दोनों नहीं, एक वर्ग है। पाले डिग्राफ वर्टेक्स सेट V = F_q और आर्क सेट के साथ निर्देशित ग्राफ है

$A=\left\{(a,b)\in \mathbf {F} _{q}\times \mathbf {F} _{q}\ :\ b-a\in (\mathbf {F} _{q}^{\times })^{2}\right\}.$

पाले डिग्राफ एक टूर्नामेंट (ग्राफ सिद्धांत) है क्योंकि अलग-अलग कोने की प्रत्येक जोड़ी एक चाप से एक और केवल एक दिशा में जुड़ी हुई है।

पाले डिग्राफ कुछ एंटीसिमेट्रिक कॉन्फ़्रेंस मैट्रिक्स और बाइप्लेन ज्यामिति के निर्माण की ओर जाता है।

वर्ग

क्रम 13 के पाले ग्राफ में प्रत्येक शीर्ष के छह पड़ोसी एक चक्र में जुड़े हुए हैं; यानी ग्राफ नेबरहुड (ग्राफ सिद्धांत) है। इसलिए, इस ग्राफ को एक टोरस्र्स के त्रिभुज (टोपोलॉजी) के रूप में एम्बेड किया जा सकता है, जिसमें हर चेहरा एक त्रिकोण है और हर त्रिकोण एक चेहरा है। अधिक सामान्यतः, यदि आदेश q के किसी भी पीले ग्राफ को एम्बेड किया जा सकता है ताकि उसके सभी चेहरे त्रिकोण हों, तो हम यूलर विशेषता के माध्यम से परिणामी सतह के जीनस की गणना कर सकते हैं ${\tfrac {1}{24}}(q^{2}-13q+24)$. मोहर (2005) अनुमान लगाता है कि एक सतह का न्यूनतम जीनस जिसमें एक पाले ग्राफ को एम्बेड किया जा सकता है, इस स्थितियों में इस सीमा के पास है कि q एक वर्ग है, और सवाल करता है कि क्या इस तरह की बाध्यता अधिक सामान्यतः हो सकती है। विशेष रूप से, मोहर का अनुमान है कि वर्ग क्रम के पाले ग्राफ को जीनस के साथ सतहों में एम्बेड किया जा सकता है

$(q^{2}-13q+24)\left({\tfrac {1}{24}}+o(1)\right),$

जहाँ o(1) पद q का कोई भी फलन हो सकता है जो उस सीमा में शून्य हो जाता है जहाँ q अनंत तक जाता है।

वाइट (2001) ऑर्डर q ≡ 1 (mod 8) के पाले ग्राफ़ के एम्बेडिंग ढूंढता है जो अत्यधिक सममित और स्व-दोहरी हैं, एक टोरस पर 3×3 वर्ग ग्रिड के रूप में ऑर्डर 9 के पाले ग्राफ़ के प्राकृतिक एम्बेडिंग को सामान्यीकृत करते हैं। चूकी, मोहर के अनुमानित बाउंड की तुलना में व्हाइट के एंबेडिंग का जीन लगभग तीन गुना अधिक है।

संदर्भ

• Baker, R. D.; Ebert, G. L.; Hemmeter, J.; Woldar, A. J. (1996). "Maximal cliques in the Paley graph of square order". J. Statist. Plann. Inference. 56: 33–38. doi:10.1016/S0378-3758(96)00006-7.
• Broere, I.; Döman, D.; Ridley, J. N. (1988). "The clique numbers and chromatic numbers of certain Paley graphs". Quaestiones Mathematicae. 11: 91–93. doi:10.1080/16073606.1988.9631945.
• Chung, Fan R. K.; Graham, Ronald L.; Wilson, R. M. (1989). "Quasi-random graphs". Combinatorica. 9 (4): 345–362. doi:10.1007/BF02125347.
• Erdős, P.; Rényi, A. (1963). "Asymmetric graphs". Acta Mathematica Academiae Scientiarum Hungaricae. 14 (3–4): 295–315. doi:10.1007/BF01895716. MR 0156334.
• Evans, R. J.; Pulham, J. R.; Sheehan, J. (1981). "On the number of complete subgraphs contained in certain graphs". Journal of Combinatorial Theory. Series B. 30 (3): 364–371. doi:10.1016/0095-8956(81)90054-X.
• Graham, R. L.; Spencer, J. H. (1971). "A constructive solution to a tournament problem". Canadian Mathematical Bulletin. 14: 45–48. doi:10.4153/CMB-1971-007-1. MR 0292715.
• Mohar, Bojan (2005). "Triangulations and the Hajós conjecture". Electronic Journal of Combinatorics. 12: N15. MR 2176532.
• Paley, R.E.A.C. (1933). "On orthogonal matrices". J. Math. Phys. 12 (1–4): 311–320. doi:10.1002/sapm1933121311.
• Sachs, Horst (1962). "Über selbstkomplementäre Graphen". Publicationes Mathematicae Debrecen. 9: 270–288. MR 0151953.
• Sasakura, Nobuo; Enta, Yoichi; Kagesawa, Masataka (1993). "Construction of rank two reflexive sheaves with similar properties to the Horrocks–Mumford bundle". Proc. Japan Acad., Ser. A. 69 (5): 144–148. doi:10.3792/pjaa.69.144.
• White, A. T. (2001). "Graphs of groups on surfaces". Interactions and models. Amsterdam: North-Holland Mathematics Studies 188.
• Wolz, Jessica (2018). Engineering Linear Layouts with SAT. Master's Thesis. University of Tübingen.

बाहरी संबंध

• Brouwer, Andries E. "Paley graphs".
• Mohar, Bojan (2005). "Genus of Paley graphs".