Erdős–Szekeres theorem
ગણિતમાં, એર્ડોસ-ઝેકેરેસ પ્રમેય ભારપૂર્વક જણાવે છે કે, r, s આપવામાં આવે તો, ઓછામાં ઓછી (r−1) (s−1) + 1 લંબાઈ ધરાવતી અલગ વાસ્તવિક સંખ્યાઓનો કોઈપણ ક્રમ લંબાઈ r નો એકવિધ રીતે વધતો ક્રમ અથવા લંબાઈ s નો એકવિધ રીતે ઘટતો ક્રમ ધરાવે છે. આ પુરાવો એ જ 1935ના પેપરમાં દેખાયો હતો જેમાં હેપ્પી એન્ડિંગ સમસ્યાનો ઉલ્લેખ કરવામાં આવ્યો હતો. તે એક અંતિમ પરિણામ છે જે રેમ્સેના પ્રમેયના ઉપસંહારમાંથી એક ચોક્કસ બનાવે છે. જ્યારે રામસેનો પ્રમેય એ સાબિત કરવાનું સરળ બનાવે છે કે અલગ વાસ્તવિક સંખ્યાઓના દરેક અનંત અનુક્રમમાં એકવિધ રીતે વધતા અનંત અનુગામી અથવા એકવિધ રીતે ઘટતા અનંત અનુગામીનો સમાવેશ થાય છે, ત્યારે પોલ એર્દોસ અને જ્યોર્જ ઝેકેરેસ દ્વારા સાબિત થયેલું પરિણામ આગળ વધે છે. ઉદાહરણ r = 3 અને s = 2 માટે, સૂત્ર આપણને જણાવે છે કે ત્રણ સંખ્યાઓના કોઈપણ ક્રમચયમાં લંબાઈ ત્રણનો વધતો ક્રમ અથવા લંબાઈ બેની ઘટતી ક્રમ હોય છે. સંખ્યાઓના છ ક્રમચયોમાંથી 1,2,3:1,2,3 ની વધતી જતી અનુગામી સંખ્યા છે જેમાં ત્રણેય સંખ્યાઓનો સમાવેશ થાય છે 1,3,2 ની ઘટતી અનુગામી સંખ્યા છે 3,2 2,1,3 ની ઘટતી અનુગામી સંખ્યા છે 2 2,3,1 ની બે ઘટતી અનુગામી સંખ્યાઓ છે, 2,1 અને 3,1 3,1,2 ની બે ઘટતી અનુગામી સંખ્યાઓ છે, 3,1 અને 3,2 3,2,1 ની ત્રણ ઘટતી લંબાઈ-2 અનુગામી સંખ્યાઓ છે, 3,2,3,1 અને 2,1. વૈકલ્પિક અર્થઘટનો ભૌમિતિક અર્થઘટન યુક્લિડિયન સમતલમાં બિંદુઓના x-કોઓર્ડિનેટ્સ તરીકે અનુક્રમમાં સંખ્યાઓની સ્થિતિઓનું અર્થઘટન કરી શકાય છે, અને સંખ્યાઓ પોતાને y-કોઓર્ડિનેટ્સ તરીકે અર્થઘટન કરી શકે છે; તેનાથી વિપરીત, સમતલમાં નિર્ધારિત કોઈપણ બિંદુ માટે, બિંદુઓના y-કોઓર્ડિનેટ્સ, તેમના x-કોઓર્ડિનેટ્સ દ્વારા ક્રમબદ્ધ, સંખ્યાઓનો ક્રમ બનાવે છે (જ્યાં સુધી બે બિંદુઓ સમાન x-કોઓર્ડિનેટ્સ ન હોય). ક્રમ અને બિંદુ સમૂહો વચ્ચેના આ અનુવાદ સાથે, એર્ડોસ-ઝેકેરેસ પ્રમેયને એમ કહીને અર્થઘટન કરી શકાય છે કે ઓછામાં ઓછા rs − r − s + 2 બિંદુઓના કોઈપણ સમૂહમાં આપણે r − 1 હકારાત્મક-ઢોળાવની ધાર અથવા s − 1 નકારાત્મક-ઢોળાવની ધારનો બહુકોણીય માર્ગ શોધી શકીએ છીએ. ખાસ કરીને (r = s લઈને), ઓછામાં ઓછા n બિંદુઓના કોઈપણ સમૂહમાં આપણે સમાન-ચિહ્ન ઢોળાવ સાથે ઓછામાં ઓછી θ θ ધારનો બહુકોણીય માર્ગ શોધી શકીએ છીએ. દાખલા તરીકે, r = s = 5 લેતા, ઓછામાં ઓછા 17 બિંદુઓના કોઈપણ સમૂહમાં ચાર ધારનો માર્ગ હોય છે જેમાં તમામ ઢોળાવોમાં સમાન નિશાની હોય છે. આવા પાથ વિના rs − r − s + 1 બિંદુઓનું ઉદાહરણ, જે દર્શાવે છે કે આ બાઉન્ડ ચુસ્ત છે, તે (r − 1) બાય (s − 1) ગ્રીડ પર નાના પરિભ્રમણ લાગુ કરીને બનાવી શકાય છે. ક્રમચય પેટર્નનું અર્થઘટન એર્ડોસ-ઝેકેરેસ પ્રમેયને ક્રમચય પેટર્નની ભાષામાં પણ અર્થઘટન કરી શકાય છે જે જણાવે છે કે ઓછામાં ઓછા rs + 1 લંબાઈના દરેક ક્રમચયમાં 1,2,3,., r + 1 અથવા s + 1, s,., 2,1 પેટર્ન હોવી જોઈએ. પુરાવા એર્ડોસ-ઝેકેરેસ પ્રમેયને ઘણી જુદી જુદી રીતે સાબિત કરી શકાય છે; એર્ડોસ-ઝેકેરેસ પ્રમેયના છ જુદા જુદા પુરાવાઓનું સર્વેક્ષણ કરે છે, જેમાં નીચેના બે સમાવેશ થાય છે. સ્ટીલ દ્વારા સર્વેક્ષણ કરાયેલા અન્ય પુરાવાઓમાં એર્ડોસ અને ઝેકેરેસ દ્વારા મૂળ પુરાવા તેમજ, અને નો સમાવેશ થાય છે. કબૂતર છિદ્ર સિદ્ધાંત લંબાઈ (r−1) (s−1) + 1 નો ક્રમ આપવામાં આવે તો, દરેક સંખ્યા Ni ને જોડી (એઆઇ, બી) સાથે અનુક્રમમાં લેબલ કરો, જ્યાં એઆઇ એ સૌથી લાંબી એકવિધ રીતે વધતી અનુગામીની લંબાઈ છે જે ની સાથે સમાપ્ત થાય છે અને બી એ ની સાથે સમાપ્ત થતી સૌથી લાંબી એકવિધ રીતે ઘટતી અનુગામીની લંબાઈ છે. અનુક્રમમાં દરેક બે સંખ્યાઓને અલગ જોડી સાથે લેબલ કરવામાં આવે છેઃ જો અને પછી, અને બીજી બાજુ જો તો. પરંતુ ત્યાં માત્ર (r−1) (s−1) સંભવિત લેબલ હોય છે જો એઆઇ મહત્તમ r−1 હોય અને બીઆઇ મહત્તમ s−1 હોય, તો કબૂતર છિદ્ર સિદ્ધાંત દ્વારા i નું મૂલ્ય અસ્તિત્વમાં હોવું જોઈએ જેના માટે એઆઇ અથવા બીઆઇ આ શ્રેણીની બહાર છે. જો એઆઇ શ્રેણીની બહાર હોય તો ની એ ઓછામાં ઓછી r લંબાઈના વધતા ક્રમનો ભાગ છે, અને જો બાય શ્રેણીની બહાર હોય તો ની એ ઓછામાં ઓછી લંબાઈના ઘટતા ક્રમનો ભાગ છે. આ સાબિતીને એક પાનાના કાગળને શ્રેય આપે છે અને તેને તે સર્વેક્ષણ કરેલા પુરાવાઓમાં "સૌથી ચપળ અને સૌથી વ્યવસ્થિત" કહે છે. અન્ય પુરાવાઓમાં આંશિક ક્રમમાં સાંકળ વિઘટન પર દિલવર્થના પ્રમેય અથવા તેના સરળ દ્વિ (મિર્સ્કીના પ્રમેય) નો ઉપયોગ થાય છે. પ્રમેયને સાબિત કરવા માટે, ક્રમના સભ્યો પર આંશિક ક્રમ વ્યાખ્યાયિત કરો, જેમાં x એ આંશિક ક્રમમાં y કરતા ઓછો અથવા બરાબર હોય જો x ≤ y સંખ્યાઓ તરીકે હોય અને x અનુક્રમમાં y કરતા પાછળનો ન હોય. આ આંશિક ક્રમમાં સાંકળ એકવિધ રીતે વધતી જતી અનુગામી છે, અને એન્ટીચેઇન એકવિધ રીતે ઘટતી જતી અનુગામી છે. મિર્સ્કીના પ્રમેય મુજબ, ક્યાં તો લંબાઈની સાંકળ r હોય છે, અથવા ક્રમને મહત્તમ r-1 વિરોધી સાંકળોમાં વિભાજિત કરી શકાય છે; પરંતુ તે કિસ્સામાં સૌથી મોટા વિરોધી સાંકળોએ ઓછામાં ઓછી લંબાઈ સાથે ઘટતા અનુગામીની રચના કરવી જોઈએ વૈકલ્પિક રીતે, દિલવર્થના પ્રમેય દ્વારા જ, ક્યાં તો લંબાઈ s ની વિરોધી સાંકળ હોય છે, અથવા ક્રમને મહત્તમ s-1 સાંકળોમાં વિભાજિત કરી શકાય છે, જેમાંથી સૌથી લાંબી સાંકળની લંબાઈ ઓછામાં ઓછી r હોવી જોઈએ. રોબિન્સન-શેન્સ્ટેડ પત્રવ્યવહારનો ઉપયોગ પરિણામ રોબિન્સન-શેન્સ્ટેડ પત્રવ્યવહારના ઉપસંહાર તરીકે પણ મેળવી શકાય છે. યાદ કરો કે રોબિન્સન-શેન્સ્ટેડ પત્રવ્યવહાર દરેક ક્રમને યંગ ટેબ્લો પી સાથે સાંકળે છે, જેની એન્ટ્રીઓ ક્રમના મૂલ્યો છે. ટેબ્લો પીમાં નીચેના ગુણધર્મો છેઃ સૌથી લાંબા વધતા અનુગામીની લંબાઈ પી ની પ્રથમ હરોળની લંબાઈ જેટલી હોય છે. સૌથી લાંબા ઘટતા અનુગામીની લંબાઈ પી ના પ્રથમ સ્તંભની લંબાઈ જેટલી હોય છે. હવે, કદના ચોરસ બૉક્સ (આર-1) (એસ-1) માં (આર-1) (એસ-1) + 1 એન્ટ્રીઓ ફિટ કરવી શક્ય નથી, જેથી પ્રથમ હરોળની લંબાઈ ઓછામાં ઓછી આર હોય અથવા છેલ્લી હરોળની લંબાઈ ઓછામાં ઓછી એસ હોય.