थ्रैकल
एक थ्रैकल तल में एक ग्राफ का एक अंतःस्थापन (एम्बेडिंग) है, जैसे कि प्रत्येक किनारा एक जॉर्डन चाप है और और किनारों का हर युग्म बिल्कुल एक बार मिलता है। किनारे या तो एक सामान्य अंत बिंदु पर मिल सकते हैं, या, यदि उनके पास कोई अंत बिंदु नहीं है, तो उनके आंतरिक भाग में एक बिंदु पर मिल सकते हैं। बाद की स्थिति में, क्रॉसिंग अनुप्रस्थ होना चाहिए।[1]
रैखिक थ्रैकल्स
एक रैखिक थ्रैकल इस तरह से खींचा गया थ्रैकल है कि इसके किनारे सीधी रेखा खंड हैं। जैसा कि पॉल एर्डोस ने देखा, प्रत्येक रैखिक थ्रैकल में अधिक से अधिक किनारों के रूप में शीर्ष होते हैं। यदि एक शीर्ष v तीन या अधिक किनारों vw, vx, और vy से जुड़ा है, तो उन किनारों में से कम से कम एक किनारा (जैसे vw ) एक रेखा पर स्थित है जो दो अन्य किनारों को अलग करता है। फिर, w की कोटि एक होनी चाहिए, क्योंकि vw के अलावा w पर समाप्त होने वाला कोई भी रेखा खंड, vx और vy दोनों को नहीं स्पर्श सकता है। किनारों और शीर्षों की संख्या के बीच के अंतर को परिवर्तन किए बिना w और vw को हटाने से एक छोटे थ्रैकल की उत्पत्ति होती है। इस तरह से हटाने के बाद एक थ्रैकल होता है जिसमें प्रत्येक शीर्ष पर अधिकतम दो सहवासी होते हैं, हैंडशेकिंग लेम्मा द्वारा किनारों की संख्या अधिक से अधिक शीर्षों की संख्या होती है।[2] एर्डोस के प्रमाण के आधार पर, कोई भी अनुमान लगा सकता है कि प्रत्येक रैखिक थ्रैकल एक स्यूडोफ़ॉरेस्ट है। विषम लंबाई के प्रत्येक चक्र को एक रेखीय थ्रैकल बनाने के लिए व्यवस्थित किया जा सकता है, लेकिन यह सम-लंबाई वाले चक्र के लिए संभव नहीं है, क्योंकि यदि चक्र के एक किनारे को स्वेच्छतः से चुना जाता है, तो चक्र के अन्य शीर्षों को बारी-बारी से इस किनारे के माध्यम से रेखा के विपरीत दिशा में स्थित होना चाहिए।
मीका पर्ल्स ने एक और सरल प्रमाण प्रदान किया कि रैखिक थ्रैकल्स में अधिकांश n किनारे होते हैं, इस तथ्य के आधार पर कि एक रेखीय थ्रैकल में प्रत्येक किनारे का एक अंत बिंदु होता है, जिस पर किनारे अधिकतम 180 ° के कोण पर विस्तृति होते हैं, और जिसके लिए यह इस सीमा (स्पैन) के अंदर सबसे अधिक दक्षिणावर्त किनारा होता है। इसके लिए, यदि नहीं, तो दो किनारे होंगे, किनारे के विपरीत अंत बिदुओं के लिए घटना और किनारे के माध्यम से रेखा की विपरीत दिशाओं पर लाइंग होना, जो एक दूसरे को क्रॉस नहीं कर सके है। लेकिन प्रत्येक शीर्ष में केवल एक किनारे के संबंध में यह गुण हो सकता है, इसलिए किनारों की संख्या अधिक से अधिक शीर्षों की संख्या के तुल्य होती है।[3]
जैसा कि एर्डोस ने भी देखा, बिंदु सेट के व्यास को प्राप्त करने वाले बिंदुओं के युग्मों के सेट को एक रैखिक थ्रैकल बनाना चाहिए: कोई भी दो व्यासों को एक दूसरे से अलग नहीं किया जा सकता है, क्योंकि यदि वे होते तो उनके चार अंतबिंदुओं में दो असंयुक्त किनारों के अलावा दूर की दूरी पर एक युग्म होता है। इस कारण से, तल में n बिंदुओं के प्रत्येक समुच्चय में अधिक से अधिक n व्यास युग्म हो सकते हैं, जो हेंज हॉफ और एरिका पन्नविट्ज़ द्वारा 1934 में पूछे गए एक प्रश्न का उत्तर देते हैं।[4] एंड्रयू वाज़सोनी ने इस समस्या को सामान्य करते हुए, उच्च आयामों में व्यास युग्मों की संख्या पर अनुमान लगाया था।[2]
अभिकलनी ज्यामिति में, घूर्णन कैलीपर्स की विधि का उपयोग अवमुख स्थिति में बिंदुओं के किसी भी समुच्चय से एक रैखिक थ्रैकल बनाने के लिए किया जा सकता है, बिंदुओं के युग्मों को जोड़कर जो बिंदुओं के अवमुख हल को समानांतर रेखाओं का समर्थन करते हैं।[5] इस ग्राफ में व्यास युग्मों के थ्रैकल को उपग्राफके रूप में सम्मिलित किया गया है।[6]
रेनहार्ड्ट बहुभुजों के व्यास रैखिक थ्रैकल बनाते हैं। सबसे बड़ी छोटी बहुभुज समस्या को हल करने के लिए रैखिक थ्रैकल्स की गणना का उपयोग किया जा सकता है, इसके व्यास के सापेक्ष अधिकतम क्षेत्र के साथ n-गॉन खोजने के लिए किया जा सकता है।[7]
थ्रैकल अनुमान
Can a thrackle have more edges than vertices?
जॉन हॉर्टन कॉनवे|जॉन एच. कॉनवे ने अनुमान लगाया कि, किसी भी थ्रैकल में, किनारों की संख्या अधिक से अधिक शीर्षों की संख्या के बराबर होती है। कॉनवे ने खुद शब्दावली पथ और स्पॉट (क्रमशः किनारों और शीर्षके लिए) का इस्तेमाल किया, इसलिए 'कॉनवे का थ्रैकल अनुमान' मूल रूप से कहा गया था
रूप में हर थ्रैकल में कम से कम उतने ही धब्बे होते हैं जितने पथ होते हैं। कॉनवे ने इस अनुमान को साबित करने या अस्वीकार करने के लिए $ 1000 पुरस्कार की पेशकश की, जिसमें कॉनवे की 99-ग्राफ की समस्या, डांसर सेट की न्यूनतम रिक्ति, और चाल 16 के बाद चाँदी का सिक्का के विजेता सहित पुरस्कार समस्याओं का एक हिस्सा भी शामिल है।[8] समतुल्य रूप से, थ्रैकल अनुमान को कहा जा सकता है क्योंकि प्रत्येक थ्रैकल एक स्यूडोफॉरेस्ट है। अधिक विशेष रूप से, यदि थ्रैकल अनुमान सत्य है, तो थ्रैकल्स को वुडाल के परिणाम से सटीक रूप से चित्रित किया जा सकता है: वे छद्म वन हैं जिनमें लंबाई चार का कोई चक्र नहीं है और अधिक से अधिक एक विषम चक्र है।[1][9] यह सिद्ध हो चुका है कि C के अलावा हर चक्र का ग्राफ4 एक थ्रैकल एम्बेडिंग है, जो दर्शाता है कि अनुमान गणितीय शब्दजाल की सूची#sharp है। यानी, पथ के समान स्पॉट वाले थ्रैकल हैं। दूसरे चरम पर, सबसे खराब स्थिति यह है कि स्पॉट की संख्या पथों की संख्या से दोगुनी है; यह भी प्राप्य है।
थ्रैकल अनुमान इस तरह से खींचे गए थ्रैकल्स के लिए सही माना जाता है कि प्रत्येक किनारा एक एक्स-मोनोटोन वक्र है, जो प्रत्येक ऊर्ध्वाधर रेखा द्वारा अधिकतम एक बार पार किया जाता है।[3]
ज्ञात सीमा
Lovász, Pach & Szegedy (1997) ने साबित किया कि प्रत्येक द्विपक्षीय ग्राफ थ्रैकल एक प्लेनर ग्राफ है, हालांकि प्लानर तरीके से नहीं खींचा गया है।[1]परिणामस्वरूप, वे दिखाते हैं कि n शीर्षों वाले प्रत्येक थ्रैकलीबल ग्राफ़ में अधिक से अधिक 2n − 3 किनारे होते हैं। तब से, इस सीमा में कई बार सुधार किया गया है। सबसे पहले, इसे 3(n − 1)/2 में सुधारा गया था,[10] और एक अन्य सुधार के कारण मोटे तौर पर 1.428n का बाउंड हुआ।[11] इसके अलावा, बाद के परिणाम को साबित करने के लिए इस्तेमाल की जाने वाली विधि किसी भी ε > 0 के लिए एक परिमित एल्गोरिथ्म है जो या तो (1 + ε)n की सीमा में सुधार करता है या अनुमान को गलत साबित करता है। वर्तमान रिकॉर्ड के कारण है Fulek & Pach (2017), जिन्होंने 1.3984n की सीमा सिद्ध की।[12] यदि अनुमान गलत है, तो एक न्यूनतम प्रति उदाहरण में एक शीर्ष साझा करने वाले दो समान चक्रों का रूप होगा।[9]इसलिए, अनुमान को सिद्ध करने के लिए, यह साबित करना पर्याप्त होगा कि इस प्रकार के ग्राफ़ को थ्रैकल्स के रूप में नहीं खींचा जा सकता है।
संदर्भ
- ↑ 1.0 1.1 1.2 Lovász, L.; Pach, J.; Szegedy, M. (1997), "On Conway's thrackle conjecture", Discrete and Computational Geometry, 18 (4): 369–376, doi:10.1007/PL00009322, MR 1476318. A preliminary version of these results was reviewed in O'Rourke, J. (1995), "Computational geometry column 26", ACM SIGACT News, 26 (2): 15–17, arXiv:cs/9908007, doi:10.1145/202840.202842.
- ↑ 2.0 2.1 Erdős, P. (1946), "On sets of distances of n points" (PDF), American Mathematical Monthly, 53 (5): 248–250, doi:10.2307/2305092, JSTOR 2305092.
- ↑ 3.0 3.1 Pach, János; Sterling, Ethan (2011), "Conway's conjecture for monotone thrackles", American Mathematical Monthly, 118 (6): 544–548, doi:10.4169/amer.math.monthly.118.06.544, MR 2812285.
- ↑ Hopf, H.; Pannwitz, E. (1934), "Aufgabe Nr. 167", Jahresbericht der Deutschen Mathematiker-Vereinigung, 43: 114.
- ↑ Eppstein, David (May 1995), "The Rotating Caliper Graph", The Geometry Junkyard
- ↑ For the fact that the rotating caliper graph contains all diameter pairs, see Shamos, Michael (1978), Computational Geometry (PDF), Doctoral dissertation, Yale University. For the fact that the diameter pairs form a thrackle, see, e.g., Pach & Sterling (2011).
- ↑ Graham, R. L. (1975), "The largest small hexagon" (PDF), Journal of Combinatorial Theory, Series A, 18 (2): 165–170, doi:10.1016/0097-3165(75)90004-7.
- ↑ Conway, John H., Five $1,000 Problems (Update 2017) (PDF), Online Encyclopedia of Integer Sequences, retrieved 2019-02-12
- ↑ 9.0 9.1 Woodall, D. R. (1969), "Thrackles and deadlock", in Welsh, D. J. A. (ed.), Combinatorial Mathematics and Its Applications, Academic Press, pp. 335–348, MR 0277421.
- ↑ Cairns, G.; Nikolayevsky, Y. (2000), "Bounds for generalized thrackles", Discrete and Computational Geometry, 23 (2): 191–206, doi:10.1007/PL00009495, MR 1739605.
- ↑ Fulek, R.; Pach, J. (2011), "A computational approach to Conway's thrackle conjecture", Computational Geometry, 44 (6–7): 345–355, arXiv:1002.3904, doi:10.1007/978-3-642-18469-7_21, MR 2785903.
- ↑ Fulek, R.; Pach, J. (2017), "Thrackles: An improved upper bound", Graph Drawing and Network Visualization: 25th International Symposium, GD 2017, Boston, MA, USA, September 25-27, 2017, Revised Selected Papers, Lecture Notes in Computer Science, vol. 10692, pp. 160–166, arXiv:1708.08037, doi:10.1007/978-3-319-73915-1_14, ISBN 978-3-319-73914-4.
बाहरी संबंध
- thrackle.org—website about the problem
