Erdős–Gyárfás conjecture
આલેખ સિદ્ધાંતમાં, 1995 માં ફલપ્રદ ગણિતશાસ્ત્રી પોલ એર્દોસ અને તેમના સહયોગી એન્ડ્રેસ ગ્યાર્ફાસ દ્વારા કરવામાં આવેલ અપ્રમાણિત એર્દોસ-ગ્યાર્ફાસ અનુમાન જણાવે છે કે ઓછામાં ઓછી ડિગ્રી 3 ધરાવતા દરેક આલેખમાં એક સરળ ચક્ર હોય છે જેની લંબાઈ બેની શક્તિ હોય છે. એર્ડોસે અનુમાન સાબિત કરવા માટે $100નું ઇનામ અથવા પ્રતિકૂળ ઉદાહરણ માટે $50ની ઓફર કરી હતી; તે એર્ડોસના ઘણા અનુમાનોમાંથી એક છે. જો અનુમાન ખોટું હોય, તો પ્રતિકૂળ ઉદાહરણ ઓછામાં ઓછા ડિગ્રી ત્રણ સાથે ગ્રાફનું સ્વરૂપ લેશે, જેમાં કોઈ પાવર-ઓફ-બે ચક્ર નથી. ગોર્ડન રોયલે અને ક્લાસ માર્કસ્ટ્રોમની કોમ્પ્યુટર શોધો દ્વારા તે જાણીતું છે કે કોઈપણ પ્રતિ-ઉદાહરણમાં ઓછામાં ઓછા 17 શિરોબિંદુ હોવા જોઈએ, અને કોઈપણ ઘન પ્રતિ-ઉદાહરણમાં ઓછામાં ઓછા 30 શિરોબિંદુ હોવા જોઈએ. માર્કસ્ટ્રોમની શોધમાં 24 શિરોબિંદુઓ પર ચાર આલેખ મળ્યા જેમાં માત્ર પાવર-ઓફ-બે ચક્રમાં 16 શિરોબિંદુઓ હોય છે. આ ચાર આલેખમાંથી એક સમતલ છે; જો કે, Erdós-Gyárfás અનુમાન હવે 3-જોડાયેલા ઘન સમતલીય આલેખના વિશેષ કેસ માટે સાચું હોવાનું જાણીતું છે ચક્ર લંબાઈના અનિવાર્ય સમૂહો સાથે આલેખની માત્રાને લગતા નબળા પરિણામો જાણીતા છેઃ લંબાઈનો એક સમૂહ S છે, જેમાં |S | = O (n0.99) હોય છે, જેમ કે સરેરાશ ડિગ્રી દસ કે તેથી વધુ ધરાવતા દરેક આલેખમાં S માં તેની લંબાઈ સાથે એક ચક્ર હોય છે, અને દરેક આલેખ કે જેની સરેરાશ ડિગ્રી n ના પુનરાવર્તિત લઘુગણકમાં ઘાતાંકીય હોય છે તેમાં એક ચક્ર હોય છે જેની લંબાઈ બેની ઘાત હોય છે. આ અનુમાન સમતલીય પંજા-મુક્ત આલેખ માટે અને એવા આલેખ માટે પણ સાચું હોવાનું જાણીતું છે જે મોટા પ્રેરિત તારાઓને ટાળે છે અને તેમની ડિગ્રી પરના વધારાના અવરોધોને સંતોષે છે. સંદર્ભો. . . . . બાહ્ય કડીઓ એક્ઝૂ, જ્યોફ્રી, ચોક્કસ લંબાઈના ચક્ર વિનાના આલેખ પશ્ચિમ, ડગ્લાસ બી., 2-શક્તિ ચક્ર લંબાઈ પર એર્ડોસ ગ્યાર્ફસ અનુમાન, ખુલ્લી સમસ્યાઓ-આલેખ સિદ્ધાંત અને સંયોજનશાસ્ત્ર અનુમાન આલેખ સિદ્ધાંતમાં વણઉકેલાયેલી સમસ્યાઓ ગ્યાર્ફસ અનુમાન