Burr–Erdős conjecture
ગણિતમાં, બર-એર્ડોસ અનુમાન એ વિરલ આલેખની રામસે સંખ્યાને લગતી સમસ્યા હતી. આ અનુમાનનું નામ સ્ટીફન બર અને પોલ એર્દોસના નામ પરથી રાખવામાં આવ્યું છે, અને તે એર્દોસના નામ પરથી રાખવામાં આવેલા ઘણા અનુમાનોમાંથી એક છે; તે જણાવે છે કે આલેખના કોઈપણ વિરલ પરિવારમાં આલેખની રામસે સંખ્યા ગ્રાફના શિરોબિંદુઓની સંખ્યામાં રેખીય રીતે વધવી જોઈએ. આ અનુમાન ચૂંગબુમ લી દ્વારા સાબિત થયું હતું. આમ તે હવે એક પ્રમેય છે. વ્યાખ્યાઓ જો G એ દિશાહીન આલેખ હોય, તો G ની અધોગતિ એ લઘુતમ સંખ્યા p છે કે જેમાં G ની દરેક પેટા આલેખમાં p અથવા તેનાથી નાની ડિગ્રીનું શિરોબિંદુ હોય છે. ડીજનરેસી પી સાથેના આલેખને પી-ડીજનરેટ કહેવામાં આવે છે. તેવી જ રીતે, પી-ડિજનરેટ આલેખ એ એક આલેખ છે જેને પી અથવા તેનાથી નાના ડિગ્રીના શિરોબિંદુને વારંવાર દૂર કરીને ખાલી આલેખમાં ઘટાડી શકાય છે. તે રેમ્સેના પ્રમેયને અનુસરે છે કે કોઈપણ આલેખ G માટે ઓછામાં ઓછો પૂર્ણાંક, G નો રેમ્સે નંબર અસ્તિત્વમાં છે, જેમ કે ઓછામાં ઓછા શિરોબિંદુઓ પરનો કોઈપણ સંપૂર્ણ આલેખ જેની કિનારીઓ લાલ અથવા વાદળી રંગની હોય તેમાં G ની મોનોક્રોમેટિક નકલ હોય છે. દાખલા તરીકે, ત્રિકોણનો રેમ્સે નંબર 6 છેઃ છ શિરોબિંદુઓ પર સંપૂર્ણ આલેખની કિનારીઓ લાલ અથવા વાદળી રંગની હોય તે ભલે ગમે તે હોય, ત્યાં હંમેશા લાલ ત્રિકોણ અથવા વાદળી ત્રિકોણ હોય છે. 1973માં, સ્ટીફન બર અને પૌલ એર્દોસે નીચેનો અંદાજ મૂક્યો હતોઃ દરેક પૂર્ણાંક p માટે એક અચળ cp અસ્તિત્વ ધરાવે છે જેથી n શિરોબિંદુઓ પર કોઈપણ p-ડીજનરેટ ગ્રાફ G પાસે મહત્તમ cp n હોય. એટલે કે, જો n-વર્ટેક્સ ગ્રાફ G એ p-ડીજનરેટ હોય, તો પછી દરેક બે ધારવાળા સંપૂર્ણ ગ્રાફમાં cp n શિરોબિંદુઓ પર G ની મોનોક્રોમેટિક નકલ અસ્તિત્વમાં હોવી જોઈએ. જાણીતા પરિણામો સંપૂર્ણ અનુમાન સાબિત થાય તે પહેલાં, તે પહેલા કેટલાક વિશેષ કિસ્સાઓમાં પતાવટ કરવામાં આવી હતી. તે બાઉન્ડેડ-ડિગ્રી ગ્રાફ માટે સાબિત થયું હતું; તેમના પુરાવાથી સી. પી. નું મૂલ્ય ખૂબ ઊંચું થયું હતું, અને આ અચળાંકમાં સુધારાઓ અને દ્વારા કરવામાં આવ્યા હતા. વધુ સામાન્ય રીતે, આ અનુમાન પી-ગોઠવી શકાય તેવા આલેખ માટે સાચું હોવાનું જાણીતું છે, જેમાં બંધાયેલા મહત્તમ ડિગ્રીવાળા આલેખ, સમતલીય આલેખ અને આલેખ કે જેમાં કેપીનો પેટા વિભાગ ન હોય. તે પેટા વિભાજિત આલેખ માટે પણ જાણીતું છે, જેમાં કોઈ પણ બે અડીને આવેલા શિરોબિંદુઓની ડિગ્રી બે કરતા વધારે હોતી નથી. મનસ્વી આલેખ માટે, રેમ્સે સંખ્યા એક કાર્ય દ્વારા બંધાયેલ હોવાનું જાણીતું છે જે માત્ર સહેજ અતિરેખીય રીતે વધે છે. ખાસ કરીને, દર્શાવ્યું કે ત્યાં એક સ્થિર સી. પી. અસ્તિત્વમાં છે, જેમ કે, કોઈપણ પી-ડીજનરેટ એન-વર્ટેક્સ ગ્રાફ જી માટે, નોંધો સંદર્ભો. . . . . . . . . ગ્રાફ થિયરી રામસે થિયરી એવા અનુમાનો કે જે સાબિત થયા છે બર-એર્ડોસ અનુમાન ગ્રાફ થિયરીમાં પ્રમેયો