Erdős–Gyárfás conjecture
ग्राफ सिद्धांत में, 1995 में विपुल गणितशास्त्री पॉल एर्दोस और उनके सहयोगी आंद्रेस ग्यार्फास द्वारा किए गए अप्रमाणित एर्दोस-ग्यार्फास अनुमान में कहा गया है कि न्यूनतम डिग्री 3 वाले प्रत्येक ग्राफ में एक सरल चक्र होता है जिसकी लंबाई दो की शक्ति होती है। एर्डोस ने अनुमान को साबित करने के लिए $100 का पुरस्कार, या एक प्रति-उदाहरण के लिए $50 की पेशकश की; यह एर्डोस के कई अनुमानों में से एक है। यदि अनुमान गलत है, तो एक प्रति-उदाहरण न्यूनतम डिग्री तीन के साथ एक ग्राफ का रूप लेगा जिसमें दो चक्रों की कोई शक्ति नहीं होगी। गॉर्डन रॉयले और क्लास मार्कस्ट्रोम की कंप्यूटर खोजों के माध्यम से यह ज्ञात है कि किसी भी प्रति-उदाहरण में कम से कम 17 शीर्ष होने चाहिए, और किसी भी घन प्रति-उदाहरण में कम से कम 30 शीर्ष होने चाहिए। मार्कस्ट्रोम की खोजों में 24 शीर्षों पर चार ग्राफ पाए गए जिनमें केवल दो चक्रों की शक्ति में 16 शीर्ष होते हैं। इन चार आलेखों में से एक समतलीय है; हालाँकि, एर्डोस-ग्यार्फस अनुमान अब 3-जुड़े घन समतलीय आलेखों के विशेष मामले के लिए सही माना जाता है-चक्र लंबाई के अपरिहार्य सेटों के लिए एक ग्राफ की डिग्री से संबंधित कमजोर परिणाम ज्ञात हैंः लंबाई का एक सेट S है, जिसमें |S। = O (n0.99) है, जैसे कि औसत डिग्री दस या उससे अधिक वाले प्रत्येक ग्राफ में S में अपनी लंबाई के साथ एक चक्र होता है, और प्रत्येक ग्राफ जिसमें औसत डिग्री n के पुनरावृत्त लघुगणक में घातीय होती है, आवश्यक रूप से एक चक्र होता है जिसकी लंबाई दो की शक्ति होती है। यह अनुमान समतल पंजे-मुक्त आलेखों और उन आलेखों के लिए भी सही माना जाता है जो बड़े प्रेरित सितारों से बचते हैं और उनकी डिग्री पर अतिरिक्त बाधाओं को पूरा करते हैं। संदर्भ। .. .. .. .. बाहरी लिंक एक्सू, जेफ्री, निर्दिष्ट लंबाई पश्चिम के चक्रों के बिना ग्राफ, डगलस बी., 2-शक्ति चक्र लंबाई पर एर्डस ग्यार्फस अनुमान, खुली समस्याएं-ग्राफ सिद्धांत और संयोजन अनुमान ग्राफ सिद्धांत में अनसुलझी समस्याएं ग्यार्फस अनुमान