Ramsey-Turán theory
રામસે-તુરાન સિદ્ધાંત એ ચરમ આલેખ સિદ્ધાંતનું પેટાક્ષેત્ર છે. તે રામસેના પ્રમેય અને તુરાનના પ્રમેયના સામાન્ય સામાન્યીકરણોનો અભ્યાસ કરે છે. ટૂંકમાં, રેમ્સે-તુરાન સિદ્ધાંત આલેખની ધારની મહત્તમ સંખ્યા માટે પૂછે છે જે તેના પેટા આલેખ અને માળખા પરની મર્યાદાઓને સંતોષે છે. આ સિદ્ધાંત ઘણા કુદરતી પ્રશ્નોનું આયોજન કરે છે જે ચરમ આલેખ સિદ્ધાંતમાં ઉદ્ભવે છે. આ સિદ્ધાંતના કેન્દ્રીય વિચારોને ઔપચારિક બનાવનારા પ્રથમ લેખકો 1969માં એર્દોસ અને સોસ હતા, જોકે ગણિતશાસ્ત્રીઓએ અગાઉ ઘણી રામસે-તુરાન-પ્રકારની સમસ્યાઓની તપાસ કરી હતી. બે રંગો અને સંપૂર્ણ આલેખ માટે રામસેનો પ્રમેય અને તુરાનનો પ્રમેય, જે 1930માં તેના મૂળ સ્વરૂપમાં સાબિત થયો હતો, જણાવે છે કે કોઈપણ હકારાત્મક પૂર્ણાંક માટે એટલો મોટો પૂર્ણાંક અસ્તિત્વમાં છે કે બે રંગોનો ઉપયોગ કરીને સંપૂર્ણ આલેખની કિનારીઓના કોઈપણ રંગ માટે તેની મોનોકોરોમેટિક નકલ હોય છે. વધુ સામાન્ય રીતે, કોઈપણ આલેખ માટે, એક મર્યાદા એવી હોય છે કે જો અને તેની ધાર મનસ્વી રીતે રંગો સાથે રંગીન હોય, તો કેટલાક માટે ત્યાં th રંગમાં a હોય છે. તુરાનનો પ્રમેય, જે 1941માં સાબિત થયો હતો, તે આલેખને શિરોબિંદુઓ પરની ધારની મહત્તમ સંખ્યા સાથે લાક્ષણિકતા આપે છે જેમાં a નથી. ખાસ કરીને, આ પ્રમેય જણાવે છે કે તમામ હકારાત્મક પૂર્ણાંકો માટે, સબગ્રાફ તરીકે ન હોય તેવા-વર્ટેક્સ આલેખની ધારની સંખ્યા સૌથી વધુ હોય છે અને મહત્તમ તુરાન આલેખ દ્વારા અનન્ય રીતે પ્રાપ્ત થાય છે. આ બંને ઉત્કૃષ્ટ પરિણામો ચોક્કસ ગુણધર્મ ધરાવે તે પહેલાં આલેખ કેટલો મોટો હોઈ શકે તે અંગે પ્રશ્નો પૂછે છે. જોકે, એક નોંધપાત્ર શૈલીગત તફાવત છે. તુરાનના પ્રમેયમાં આત્યંતિક આલેખ ખૂબ જ કડક માળખું ધરાવે છે, જેમાં નાની રંગીન સંખ્યા હોય છે અને તેમાં નાની સંખ્યામાં મોટા સ્વતંત્ર સમૂહો હોય છે. બીજી બાજુ, રામસે સમસ્યાઓમાં ગણવામાં આવતો આલેખ એ સંપૂર્ણ આલેખ છે, જેમાં મોટી રંગીન સંખ્યા હોય છે અને કોઈ બિન-તુચ્છ સ્વતંત્ર સમૂહ નથી. આ બે પ્રકારની સમસ્યાઓને જોડવાની એક કુદરતી રીત એ છે કે એન્ડ્રાસ્ફાઇ દ્વારા પૂછવામાં આવેલ નીચેનો પ્રશ્ન પૂછવોઃ સમસ્યા 1: આપેલ હકારાત્મક પૂર્ણાંક માટે, એક-વર્ટેક્સ આલેખ હોવો જોઈએ જેમાં સ્વતંત્ર સંખ્યા ન હોય અને ન હોય. આવા આલેખમાં ધારની મહત્તમ સંખ્યા કેટલી હોઈ શકે? અનિવાર્યપણે, આ પ્રશ્ન રામસે સેટિંગમાં તુરાન સમસ્યાનો જવાબ પૂછે છે; તે તુરાનની સમસ્યાને ઓછી સુવ્યવસ્થિત, વધુ અવ્યવસ્થિત માળખા સાથે ગ્રાફના સબસેટ સુધી મર્યાદિત કરે છે. નીચેનો પ્રશ્ન સમસ્યાઓને વિરુદ્ધ દિશામાં જોડે છેઃ સમસ્યા 2: ચાલો આલેખ નિશ્ચિત કરીએ. શિરોબિંદુઓ પર ધારની ધારની મહત્તમ સંખ્યા કેટલી હોઈ શકે છે, તે શરત હેઠળ કે તેમાં th રંગમાં એક ન હોય? સામાન્ય સમસ્યા રેમ્સે-તુરાન સિદ્ધાંતની કરોડરજ્જુ એ ઉપરોક્ત સમસ્યાઓનું સામાન્ય સામાન્યીકરણ છે. સમસ્યા 3: ચાલો આલેખ નિશ્ચિત કરીએ. ધારો કે એક-ધાર-રંગીન-વર્ટેક્સ આલેખ સંતોષકારક છે (1) (2) th રંગ દ્વારા વ્યાખ્યાયિત સબગ્રાફમાં નં. ધારની મહત્તમ સંખ્યા કેટલી હોઈ શકે? અમે મહત્તમ દ્વારા સૂચવીએ છીએ. રામસે-તુરાન-પ્રકારની સમસ્યાઓ એ સમસ્યા 3 ના વિશેષ કિસ્સાઓ છે. આ સમસ્યાના ઘણા કિસ્સાઓ ખુલ્લા રહે છે, પરંતુ કેટલાક રસપ્રદ કિસ્સાઓ ચોક્કસ એસિમ્પ્ટોટિક ઉકેલો સાથે ઉકેલવામાં આવ્યા છે. નોંધપાત્ર પરિણામો સમસ્યા 3 ને સ્વતંત્રતા સંખ્યા પરના પ્રતિબંધના આધારે ત્રણ અલગ અલગ કિસ્સાઓમાં વિભાજિત કરી શકાય છે. ત્યાં પ્રતિબંધ-મુક્ત કેસ છે, જ્યાં, જે ક્લાસિક રામસે સમસ્યામાં ઘટાડો કરે છે. ત્યાં "મધ્યવર્તી" કેસ છે, જ્યાં નિશ્ચિત માટે. છેલ્લે, એક કેસ છે, જેમાં સૌથી વધુ સમૃદ્ધ સમસ્યાઓ છે. શ્રેણીમાં સૌથી મૂળભૂત બિન-તુચ્છ સમસ્યા એ છે કે જ્યારે અને એર્દોસ અને સોસે 1969 માં આ પરિસ્થિતિમાં રામસે-તુરાન નંબરનું એસિમ્પ્ટોટિક મૂલ્ય નક્કી કર્યુંઃ શિરોબિંદુઓની સમ સંખ્યા પર સંપૂર્ણ ગ્રાફનો કેસ વધુ પડકારજનક છે, અને 1983 માં એર્દોસ, હાજનલ, સોસ અને સ્ઝેમેરેડી દ્વારા ઉકેલવામાં આવ્યો હતોઃ નોંધ કરો કે બંને કિસ્સાઓમાં, સમસ્યાને તુરાનના પ્રમેયમાં વધારાની શરત ઉમેરવા તરીકે જોઈ શકાય છે. બંને કિસ્સાઓમાં, તે જોઈ શકાય છે કે એસિમ્પ્ટોટિક રીતે, અસર એ જ છે જાણે કે આપણે અથવા ને બદલે બાકાત રાખ્યું હોય. સંદર્ભો આલેખ સિદ્ધાંત