स्थानीय रैखिक आरेख

नौ-शीर्ष पालेय आरेख स्थानीय रैखिक है। इसके छह त्रिकोणों में से एक को हरे रंग में प्रकाशित किया गया है।

आरेख सिद्धांत में स्थानीय रैखिक आरेख एक ऐसा अप्रत्यक्ष आरेख होता है जिसमें प्रत्येक शीर्ष ठीक त्रिकोण से संबंधित होते है। समतुल्य रूप से, आरेख के प्रत्येक शीर्ष के लिए इसके निकटतम शीर्ष प्रत्येक एक-दूसरे शीर्ष के निकट होते हैं इसलिए निकटतम शीर्षों को एक प्रेरित समान रेखा में जोड़ा जा सकता है। सामान्यतः स्थानीय रैखिक आरेख को रैखिक रेखांकन के रूप मे भी जाना जाता है।

स्थानीय रैखिक आरेख के लिए कई निर्माण ज्ञात हैं। स्थानीय रैखिक आरेख के उदाहरणों में त्रिकोणीय कैक्टस आरेख, 3-नियमित त्रिभुज-मुक्त आरेख के रेखा आरेख और छोटे स्थानीय रैखिक आरेख के कार्तीय गुणनफल सम्मिलित हैं। केनेसर आरेख और कुछ दृढ़ता से नियमित आरेख भी स्थानीय रैखिक आरेख होते हैं।

स्थानीय रैखिक आरेख के कितने शीर्ष हो सकते हैं यह सवाल रूज़सा-ज़ेमेरीडी समस्या के योगों में से एक है। हालांकि सघन आरेख में शीर्षो की संख्या के वर्ग के अनुपात में कई शीर्ष हो सकते हैं स्थानीय रैखिक आरेख में शीर्षों की संख्या कम होती है जो कम से कम एक छोटे से गैर-निरंतर फलन द्वारा वर्ग से कम होती है। स्थानीय रैखिक हो सकने वाले सघन समतल आरेख भी ज्ञात हैं। सबसे कम घने स्थानीय रैखिक आरेख त्रिकोणीय कैक्टस आरेख हैं।

निर्माण

ग्लूइंग और गुणनफल

मैत्री आरेख

मैत्री आरेख एक ही साझा शीर्ष पर त्रिभुजों के संग्रह को एक साथ जोड़कर बनाए गए आरेख स्थानीय रैखिक आरेख होते हैं। वे एकमात्र परिमित आरेख हैं जिनके पास विभिन्न विशेषताए है जो कि प्रत्येक युग्म के शीर्ष (आसन्न या नहीं) एक सामान्य निकटतम आरेख को साझा करते हैं। अधिक सामान्यतः प्रत्येक त्रिकोणीय कैक्टस आरेख अतिरिक्त किसी अतिरिक्त वृत्त के साझा किए गए शीर्षों पर त्रिकोणों का एक ग्लूइंग आरेख स्थानीय रैखिक होता है।

निम्न संक्रिया द्वारा स्थानीय रैखिक आरेख छोटे स्थानीय रैखिक आरेख से बन सकते हैं माना कि $G$ और $H$ कोई भी दो स्थानीय रैखिक आरेख हैं उनमें से प्रत्येक से एक त्रिकोण का चयन करें और दो चयनित त्रिकोणों में संबंधित युग्म को एक साथ मिलाकर दो आरेखों को ग्लूइंग मे रूपांतरित करें। जिससे परिणामी आरेख स्थानीय रैखिक रहता है।

किसी भी दो स्थानीय रैखिक आरेख का कार्तीय गुणनफल स्थानीय रूप से रैखिक रहता है क्योंकि गुणनफल में कोई भी त्रिकोण एक या दूसरे फलनों में त्रिकोण होते है। उदाहरण के लिए, 9 शीर्ष-पालेय आरेख (3-3 डुओप्रिज्म का आरेख) दो त्रिकोणों का कार्तीय गुणनफल है। हैमिंग आरेख $H(d,3)$ त्रिभुजों का कार्तीय गुणनफल और पुनः स्थानीय रैखिक है।

छोटे आरेख से

कुछ आरेख जो स्वयं स्थानीय रूप से रैखिक नहीं हैं उन्हें बड़े स्थानीय रैखिक आरेख बनाने के लिए एक संरचना के रूप में उपयोग किया जा सकता है। ऐसे ही एक निर्माण में रैखिक आरेख सम्मिलित हैं। किसी भी आरेख $G$ के लिए, रैखिक आरेख $L(G)$ एक ऐसा आरेख है जिसमें $G$ के प्रत्येक शीर्ष के लिए $L(G)$ एक शीर्ष है। $L(G)$ में दो शीर्ष आसन्न होते हैं जब $G$ में प्रतिनिधित्व करने वाले दो शीर्षों का एक सामान्य समापन बिंदु होता है। यदि $G$ 3-नियमित त्रिभुज-मुक्त आरेख है तो इसका रैखिक आरेख $L(G)$ 4-नियमित और स्थानीय रैखिक होता है। इसमें $G$ के प्रत्येक शीर्ष $v$ के लिए एक त्रिभुज है जिसमें त्रिभुज के शीर्ष $v$ से संबंधित तीन शीर्षों के अनुरूप हैं। प्रत्येक 4-नियमित स्थानीय रैखिक आरेख इस प्रकार से बनाया जा सकता है। उदाहरण के लिए घन अष्टफलक का आरेख घन का रेखा आरेख है इसलिए यह स्थानीय रैखिक है। कार्तीय गुणनफल के रूप में ऊपर निर्मित स्थानीय रैखिक 9 शीर्ष-पालेय आरेख, उपयोगिता आरेख $K_{3,3}$ के रैखिक आरेख के रूप में एक अलग तरीके से भी बनाया जा सकता है। इस निर्माण द्वारा पीटरसन आरेख का रैखिक आरेख भी स्थानीय रैखिक होता है। इसमें केज (आरेख सिद्धांत) के अनुरूप गुण होते है यह सबसे छोटा संभव आरेख है जिसमें सबसे बड़े क्लिक (आरेख सिद्धांत) में तीन शीर्ष होते हैं प्रत्येक शीर्ष दो शीर्ष-विच्छेद वाले क्लिक्स में है और अलग-अलग क्लिक्स के शीर्षों के साथ सबसे छोटा फ़लक पांच लंबाई का है।

घन अष्टफलक, एक समतली स्थानीय रैखिक आरेख जिसे घन के रेखा आरेख के रूप में बनाया जा सकता है या 4-चक्र के अंदर और बाहर के फ़लक पर प्रतिप्रिज्म को प्रयुक्त करके बनाया जा सकता है।

समतली आलेख पर एक अधिक जटिल विस्तार प्रक्रिया प्रयुक्त होती है। मान लीजिए कि $G$ समतल में एक समतलीय आरेख इस प्रकार सन्निहित है कि प्रत्येक फलक एक चतुर्भुज है जैसे घन के आरेख $G$ के प्रत्येक फ़लक पर एक वर्ग एंटीप्रिज्म को प्रयुक्त करना और फिर $G$ के मूल शीर्षों को हटाना और एक नया स्थानीय रैखिक समतली आरेख तैयार करना है। परिणाम के शीर्षों और शीर्षों की संख्या की गणना यूलर के बहुफलकीय सूत्र से की जा सकती है यदि $G$ में $n$ शीर्ष हैं और इसके बिलकुल $n-2$ फलक हैं जो प्रतिप्रिज्म द्वारा $G$ के फलकों को प्रतिस्थापित करने का परिणाम है उदाहरण के लिए शीर्ष $5(n-2)+2$ और $12(n-2)$ एक 4-चक्र के दो फ़लक (आंतरिक और बाहरी) से घन अष्टफलक को फिर से इस प्रकार से बनाया जा सकता है। इस निर्माण के हटाए गए 4-चक्र को घन अष्टफलक पर इसके चतुर्भुज फलकों के चार विकर्णों को एक चक्र के रूप में देखा जा सकता है जो बहुफलक को द्विभाजित करता है।

बीजगणितीय रचनाएं

कुछ केनेसर आरेख समान आकार के समुच्चय के प्रतिच्छेदन पैटर्न से निर्मित आरेख मे स्थानीय रूप से रैखिक होते हैं। नेसर आरेख को दो मापदंडों द्वारा वर्णित किया गया है समुच्चय का आकार जो वे प्रतिनिधित्व करते हैं और ब्रह्मांड का आकार जिससे ये समुच्चय तैयार किए गए हैं। केनेसर आरेख $KG_{a,b}$ में ${\tbinom {a}{b}}$ शीर्ष होते हैं द्विपद गुणांक के लिए मानक संकेतन में a-तत्व के समुच्चय $b$ तत्व के उपसमुच्चय का प्रतिनिधित्व करते हैं इस आरेख में, दो शीर्ष आसन्न होते हैं जब संगत उपसमुच्चय असंयुक्त समुच्चय होते हैं जिनमें कोई तत्व उभयनिष्ठ नहीं होता है। विशेष स्थिति में जब $a=3b$ परिणामी आरेख स्थानीय रूप से रैखिक होता है क्योंकि प्रत्येक दो शीर्ष असंयुक्त होते हैं जिसमे $b$ तत्व उपसमुच्चय $X$ और $Y$ उन दोनों से ठीक एक अन्य $b$ तत्व उपसमुच्चय असंयुक्त है जिसमें वे सभी गुणक सम्मिलित हैं जो न तो $X$ में हैं और न ही $Y$ में है परिणामी स्थानीय रैखिक आरेख में ${\tbinom {3b}{b}}$ शीर्ष और ${\tfrac {1}{2}}{\tbinom {3b}{b}}{\tbinom {2b}{b}}$ केज होते है। उदाहरण के लिए, $b=2$ के लिए केनेसर आरेख $KG_{6,2}$ मे 15 शीर्षों और 45 केज आरेख के साथ स्थानीय रैखिक है।

स्थानीय रैखिक आरेख भी संख्याओं के प्रगति-मुक्त समुच्चय से बनाए जा सकते हैं। माना कि $p$ एक अभाज्य संख्या है माना कि $A$ संख्या गुणक $p$ का एक उपसमुच्चय है जैसे कि $A$ के कोई भी तीन सदस्य एक अंकगणितीय प्रगति गुणक $p$ नहीं बनाते हैं। अर्थात् $A$ सलेम-स्पेंसर समुच्चय गुणक $p$ है। इस समुच्चय का उपयोग $3p$ शीर्ष और $3p$ $A$ केज आरेख के साथ एक त्रिपक्षीय आरेख बनाने के लिए किया जा सकता है जो स्थानीय रैखिक है। इस आरेख को बनाने के लिए शीर्ष के तीन समुच्चय बनाएं, प्रत्येक को $0$ से $p-1$ तक क्रमांकित करें। $0$ से $p-1$ तक की श्रेणी में प्रत्येक संख्या x के लिए और $A$ के प्रत्येक तत्व के लिए, शीर्ष के पहले समुच्चय में शीर्ष को संख्या x से जोड़ने वाला एक त्रिभुज बनाएँ संख्या के साथ केज $x+a$ शीर्षों के दूसरे समुच्चय में और शीर्षों के तीसरे समुच्चय में संख्या $x+2a$ के साथ शीर्ष मे इन सभी त्रिभुजों के संयोग के रूप में एक आरेख बनाएँ। क्योंकि यह त्रिभुजों का एक संघ है और परिणामी आरेख का प्रत्येक किनारा एक त्रिभुज से संबंधित है। हालाँकि, इस प्रकार से बने त्रिभुजों के अतिरिक्त कोई अन्य त्रिभुज नहीं हो सकता है। किसी भी अन्य त्रिभुज के शीर्ष $(x,x+a,x+a+b)$ क्रमांकित होते है। जहां $a$, $b$ और $c=(a+b)/2$ सभी $A$ से संबंधित हैं, जो इस धारणा का उल्लंघन करते है कि $A$ में कोई अंकगणितीय श्रेणी $(a,c,b)$ नहीं होनी चाहिए। उदाहरण के लिए $p=3$ और $A=\{\pm 1\}$ के साथ, इस निर्माण का परिणाम शीर्ष पालेय आरेख है।

नियमितता

कुछ शीर्षों के साथ नियमित आरेख

एक आरेख नियमित आरेख होता है जब इसके सभी शीर्षों में घटना शीर्षों की संख्या समान होती है। प्रत्येक स्थानीय रैखिक आरेख में प्रत्येक शीर्ष पर सम डिग्री होनी चाहिए, क्योंकि प्रत्येक शीर्ष पर शीर्षों को त्रिभुजों में जोड़ा जा सकता है। दो स्थानीय रैखिक नियमित आरेख का कार्तीय गुणनफल फिर से स्थानीय रैखिक और नियमित होता है। जिसमें कारकों की डिग्री उनके योग के बराबर डिग्री होती है। इसलिए कोई भी डिग्री दो (त्रिकोण) के स्थानीय रैखिक आरेख के कार्तीय गुणनफलों को प्रत्येक डिग्री के $2r$ नियमित स्थानीय रैखिक आरेख का उत्पादन करने के लिए ले सकता है। क्योंकि किसी भी त्रिभुज और उसके निकटतम केज आरेख के बीच $6r-3$ ही शीर्ष होते हैं। त्रिभुज के कोई भी दो शीर्ष स्थानीय रैखिकता का उल्लंघन किए बिना एक निकटतम शीर्ष को साझा नहीं कर सकते हैं। क्योकि शीर्षों के साथ नियमित आरेख केवल तभी संभव होते हैं जब $r$ 1, 2, 3, या 5 हो और इन चार स्थितियों में से प्रत्येक के लिए विशिष्ट रूप से परिभाषित किया गया है शीर्षों की संख्या पर इस सीमा को पूरा करने वाले चार नियमित आरेख 3-शीर्ष 2-नियमित त्रिभुज $K_{3}$, 9-शीर्ष 4-नियमित पालेय आरेख, 15-शीर्ष 6-नियमित केनेसर आरेख $KG_{6,2}$और श्लाफली आरेख के 27-शीर्ष 10-नियमित पूरक आरेख अंतिम 27-शीर्ष 10-नियमित आरेख भी घन सतह पर 27 रेखाओं के प्रतिच्छेदन आरेख का प्रतिनिधित्व करते है।

दृढ नियमित आरेख

एक दृढ़ नियमित आरेख को चार $(n,k,\lambda ,\mu )$ मापदंडों द्वारा चित्रित किया जा सकता है जहाँ $n$ शीर्षों की संख्या है, $k$ प्रति शीर्ष घटना शीर्षों की संख्या है, $\lambda$ शीर्षों के प्रत्येक सन्निकट युग्म के लिए साझा की गयी निकटतम की संख्या है और $\mu$ शीर्षों के प्रत्येक गैर-निकटवर्ती युग्म के लिए साझा की गयी निकटतम की संख्या है। जब $\lambda =1$ आरेख स्थानीय रैखिक है। ऊपर उल्लिखित स्थानीय रैखिक आरेख दृढ़ नियमित आरेख हैं और उनके पैरामीटर निम्नलिखित हैं:

• त्रिकोण (3,2,1,0)
• नौ-शीर्ष पालेय आरेख (9,4,1,2),
• केसर आरेख $KG_{6,2}$ (15,6,1,3)
• श्लाफली आरेख का पूरक (27,10,1,5)

अन्य स्थानीय रैखिक दृढ़ नियमित आरेख में सम्मिलित हैं:

• ब्राउवर-हेमर्स आरेख (81,20,1,6)
• बेर्लेकैंप-वैन लिंट-सीडेल आरेख (243,22,1,2)
• कोसिडेंटे-पेंटिला आरेख (378,52,1,8),
• खेल आरेख (729,112,1,20)

$\lambda =1$ के साथ अन्य संभावित-वैध संयोजन में (99,14,1,2) और (115,18,1,3) सम्मिलित हैं लेकिन यह अज्ञात है कि क्या उन मापदंडों के साथ दृढ़ नियमित आरेख सम्मिलित हैं। मापदंडों (99,14,1,2) के साथ एक दृढ़ नियमित आरेख के अस्तित्व का प्रश्न जॉन हॉर्टन कॉनवे की 99-आरेख समस्या के रूप में जाना जाता है और जॉन हॉर्टन कॉनवे ने इसके समाधान के लिए $1000 पुरस्कार की प्रस्तुति की है।

दूरी-नियमित आरेख

डिग्री 4 या 6 के निश्चित रूप से कई दूरी-नियमित आरेख हैं जो स्थानीय रैखिक हैं। समान डिग्री के दृढ़ नियमित आरेख से अज्ञात वे पीटरसन आरेख के रैखिक आरेख, हैमिंग आरेख $H(3,3)$ और अर्ध फोस्टर आरेख को भी सम्मिलित करते हैं।

घनत्व

एक समतली आरेख के प्रत्येक चतुर्भुज फ़लक (नीले शीर्ष और समतलीय शीर्षों) में प्रतिप्रिज्म (लाल शीर्ष और काले शीर्षों) मे प्रयुक्त से स्थानीय रूप से संभव स्थानीय रैखिक समतली आरेख बनाते हैं।

Main article: रुज़सा-ज़ेमेरीडी समस्या

रुज़्सा-ज़ेमेरीडी समस्या का एक सूत्रीकरण n शीर्ष स्थानीय रैखिक आरेख में शीर्षों की अधिकतम संख्या के लिए पूछता है। जैसा कि इमरे जेड रूज़सा और एंड्रे ज़ेमेरीडी ने सिद्ध किया कि यह अधिकतम संख्या $o(n^{2})$ है लेकिन $\Omega (n^{2-\varepsilon })$ प्रत्येक $\varepsilon >0$ के लिए है। प्रगति-मुक्त समुच्चयों से स्थानीय रैखिक आरेख का निर्माण स्थानीय स्तर पर ज्ञात रैखिक आरेख $n^{2}/\exp O({\sqrt {\log n}})$ के साथ होता है इन सूत्रों में $o$, $\Omega$ और $O$ क्रमशः संकेत पद्धति के उदाहरण हैं।

सतलीय आरेखों में स्थानीय रैखिक आरेख $n$ शीर्षों के साथ शीर्षों की अधिकतम संख्या ${\tfrac {12}{5}}(n-2)$ है। जहाँ घन अष्टफलक का आरेख $n=5k+2$ शीर्ष और ${\tfrac {12}{5}}(n-2)=12k$ केज आरेख के साथ बहुफलकीय आरेख के अनंत अनुक्रम में पहला है, $k=2,3,\dots$ के लिए चतुर्भुज फलकों को बढ़ाकर $K_{2,k}$ प्रतिप्रिज़्म में बनाया गया है। इन उदाहरणों से पता चलता है कि ${\tfrac {12}{5}}(n-2)$ ऊपरी सीमा प्राप्त की जा सकती है।

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