पाले ग्राफ

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

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

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

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

परिभाषा

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

अब वी = 'एफ'_q और जाने

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

यदि एक जोड़ी {ए, बी} को ई में शामिल किया गया है, तो इसे इसके दो तत्वों के क्रम में शामिल किया गया है। के लिए, 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) , और एक्स ± 4 (मॉड 13)।

गुण

Paley ग्राफ़ स्व-पूरक ग्राफ़ हैं | स्व-पूरक: किसी भी Paley ग्राफ़ का पूरक इसके लिए आइसोमॉर्फिक है। एक समरूपता मानचित्रण के माध्यम से है जो एक शीर्ष 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).$

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

Paley रेखांकन के eigenvalues ​​​​हैं ${\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 प्रधान होता है, तो संबद्ध Paley ग्राफ एक हैमिल्टनियन चक्र परिसंचारी ग्राफ होता है।

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

अनुप्रयोग

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

पाले डिग्राफ

क्यू को एक प्रमुख शक्ति होने दें क्यू = 3 (मॉड 4)। इस प्रकार, कोटि q, 'F' का परिमित क्षेत्र_q, -1 का कोई वर्गमूल नहीं है। नतीजतन, 'एफ' के विशिष्ट तत्वों की प्रत्येक जोड़ी (ए, बी) के लिए_q, या तो 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 के पाले ग्राफ में प्रत्येक शीर्ष के छह पड़ोसी एक चक्र में जुड़े हुए हैं; यानी ग्राफ नेबरहुड (ग्राफ थ्योरी) है। इसलिए, इस ग्राफ को एक टोरस्र्स के त्रिभुज (टोपोलॉजी) के रूप में एम्बेड किया जा सकता है, जिसमें हर चेहरा एक त्रिकोण है और हर त्रिकोण एक चेहरा है। अधिक आम तौर पर, यदि आदेश क्यू के किसी भी पीले ग्राफ को एम्बेड किया जा सकता है ताकि उसके सभी चेहरे त्रिकोण हों, तो हम यूलर विशेषता के माध्यम से परिणामी सतह के जीनस की गणना कर सकते हैं ${\tfrac {1}{24}}(q^{2}-13q+24)$. Mohar (2005) अनुमान लगाता है कि एक सतह का न्यूनतम जीनस जिसमें एक पाले ग्राफ को एम्बेड किया जा सकता है, इस मामले में इस सीमा के पास है कि क्यू एक वर्ग है, और सवाल करता है कि क्या इस तरह की बाध्यता अधिक आम तौर पर हो सकती है। विशेष रूप से, मोहर का अनुमान है कि वर्ग क्रम के पाले ग्राफ को जीनस के साथ सतहों में एम्बेड किया जा सकता है

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

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

White (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".