Erdős–Szemerédi theorem
અંકગણિત સંયોજનશાસ્ત્રમાં, એર્દોસ-ઝેમેરેડી પ્રમેય જણાવે છે કે પૂર્ણાંકોના દરેક મર્યાદિત સમૂહ માટે, ઓછામાં ઓછો એક, જોડી મુજબના સરવાળાનો સમૂહ અથવા જોડી મુજબના ઉત્પાદનોનો સમૂહ નોંધપાત્ર રીતે મોટો સમૂહ બનાવે છે. વધુ ચોક્કસપણે, એર્દોસ-ઝેમેરેડી પ્રમેય જણાવે છે કે કોઈ પણ બિન-ખાલી સમૂહ માટે હકારાત્મક અચળાંકો c અને આવા અસ્તિત્વ ધરાવે છે. તે 1983માં પોલ એર્દોસ અને એન્ડ્રે સ્ઝેમેરેદી દ્વારા સાબિત કરવામાં આવ્યું હતું. સંકેત સમૂહની મુખ્યતાને સૂચવે છે. જોડી મુજબની રકમનો સમૂહ છે અને તેને રકમનો સમૂહ કહેવામાં આવે છે. જોડી મુજબના ઉત્પાદનોનો સમૂહ છે અને તેને ઉત્પાદનનો સમૂહ કહેવામાં આવે છે. આ પ્રમેય એ સિદ્ધાંતનું એક સંસ્કરણ છે કે જે એડિટિવ સ્ટ્રક્ચર અને મલ્ટિપ્લિકેટિવ સ્ટ્રક્ચર સહઅસ્તિત્વમાં ન હોઈ શકે. તેને એક દાવા તરીકે પણ જોઈ શકાય છે કે વાસ્તવિક રેખામાં મર્યાદિત સબરીંગ અથવા મર્યાદિત સબફિલ્ડ જેવો કોઈ સમૂહ નથી; તે હવે સમ-પ્રોડક્ટ ઘટના તરીકે ઓળખાય છે તેનું પ્રથમ ઉદાહરણ છે, જે હવે મર્યાદિત ક્ષેત્રો સહિત વિવિધ રિંગ્સ અને ક્ષેત્રોમાં પકડવા માટે જાણીતું છે. સરવાળો-ઉત્પાદન અનુમાન સરવાળો-ઉત્પાદન અનુમાન અનૌપચારિક રીતે કહે છે કે કોઈપણ સમૂહનો સરવાળો સમૂહ અથવા ઉત્પાદન સમૂહ લગભગ શક્ય તેટલો મોટો હોવો જોઈએ. તે મૂળરૂપે પૂર્ણાંકો પર એર્દોસ અને સ્ઝેમેરેડી દ્વારા અનુમાન કરવામાં આવ્યું હતું, પરંતુ વાસ્તવિક સંખ્યાઓ પર જાળવી રાખવાનું માનવામાં આવે છે. અનુમાનઃ કોઈપણ સમૂહ માટે એક પાસે ઓ (1) નોટેશનમાં એસિમ્પ્ટોટિક પરિમાણ |A | છે. ઉદાહરણો જો પછી એસિમ્પ્ટોટિક નોટેશનનો ઉપયોગ કરીને, એસિમ્પ્ટોટિક પરિમાણ સાથે. અનૌપચારિક રીતે, આ કહે છે કે નો સરવાળો વધતો નથી. બીજી બાજુ, ઉત્પાદન સમૂહ બધા માટે ફોર્મની મર્યાદાને સંતોષે છે. આ એર્ડોસ ગુણાકાર કોષ્ટક સમસ્યા સાથે સંબંધિત છે. આ સેટ માટે શ્રેષ્ઠ લોઅર બાઉન્ડ કેવિન ફોર્ડને કારણે છે. આ ઉદાહરણ ગ્યોર્જી એલેક્સ અને ઇમરે ઝેડ. રુઝાની સમ-પ્રોડક્ટ સમસ્યાના ફ્યુ સમ, મેની પ્રોડક્ટ્સ વર્ઝનનું ઉદાહરણ છે. તેમના પરિણામનું પરિણામ એ છે કે નાના એડિટિવ ડબલિંગ સાથેનો કોઈપણ સમૂહ, ઉદાહરણ તરીકે અંકગણિત પ્રગતિ, ઉત્પાદન સમૂહ પર નીચલી સીમા ધરાવે છે. ઝુ અને ઝોઉએ સાબિત કર્યું કે પૂર્ણાંકોમાં અંકગણિત પ્રગતિના કોઈપણ ગાઢ સબસેટ માટે, જે એક્સ્પોનન્ટમાં પરિબળ સુધી તીક્ષ્ણ છે. તેનાથી વિપરીત, સમૂહ સંતોષ આપે છે, પરંતુ તેમાં ઘણા સરવાળો છેઃ આ બંધન સંખ્યાના દ્વિસંગી પ્રતિનિધિત્વને ધ્યાનમાં લેવાથી આવે છે. આ સમૂહ ભૌમિતિક પ્રગતિનું ઉદાહરણ છે. સંખ્યાઓના યાદૃચ્છિક સમૂહ માટે, ઉત્પાદન સમૂહ અને સરવાળો સમૂહ બંનેમાં મુખ્યતા હોય છે; એટલે કે, ઉચ્ચ સંભાવના સાથે સરવાળો સમૂહ કોઈ પુનરાવર્તિત ઘટકો ઉત્પન્ન કરતો નથી, અને ઉત્પાદન સમૂહ માટે સમાન હોય છે. એર્ડોસ અને સ્ઝેમેરેડી અનુમાનની તીક્ષ્ણતા બાઉન્ડ સાથે પૂર્ણાંકોના પૂરતા પ્રમાણમાં સરળ સમૂહનું ઉદાહરણ આપે છેઃ આ દર્શાવે છે કે અનુમાનમાં ઓ (1) શબ્દ જરૂરી છે. અતિશય કિસ્સાઓમાં ઘણીવાર અભ્યાસ કરવામાં આવે છે તે પૂર્વધારણાના આત્યંતિક કિસ્સાઓ છેઃ થોડા સરવાળા, ઘણા ઉત્પાદન (એફ. એસ. એમ. પી.): જો, તો પછી થોડા ઉત્પાદનો, ઘણા સરવાળા (એફ. પી. એમ. એસ.): જો, તો. ઇતિહાસ અને વર્તમાન પરિણામો નીચેનું કોષ્ટક વાસ્તવિક પર રકમ-ઉત્પાદન સમસ્યા પર પ્રગતિનો સારાંશ આપે છે. ગ્યોર્જી એલેક્સના 1/4 અને જોઝેફ સોલિમોસીના 1/3 ઘટકોને ટાંકતા સાહિત્યમાં સીમાચિહ્નરૂપ પરિણામો ગણવામાં આવે છે. 2009 પછીના તમામ સુધારાઓ સ્વરૂપના છે, અને કોન્યાગિન અને શ્ક્રેડોવની દલીલોના સુધારાઓનું પ્રતિનિધિત્વ કરે છે. જટિલ સંખ્યાઓ માત્ર સ્ઝેમેરેડી-ટ્રોટર પ્રમેયને સમાવતી પુરાવા તકનીકો આપમેળે જટિલ સંખ્યાઓ સુધી વિસ્તરે છે, કારણ કે સ્ઝેમેરેડી-ટ્રોટર પ્રમેય ટોથના પ્રમેય દ્વારા માન્ય છે. કોન્યાગિન અને રુડનેવ જટિલ સંખ્યાઓ પર 3/4 ના ઘાતાંક સાથે મેળ ખાતા હતા. સ્વરૂપના ઘાતાંકો સાથેના પરિણામો જટિલ સંખ્યાઓ સાથે મેળ ખાતા નથી. મર્યાદિત ક્ષેત્રો પર સરવાળાની સમસ્યાનો ખાસ કરીને મર્યાદિત ક્ષેત્રો પર સારી રીતે અભ્યાસ કરવામાં આવે છે. મર્યાદિત ક્ષેત્ર કાકીયાના અનુમાનથી પ્રેરિત થઈને, વોલ્ફે અનુમાન લગાવ્યું હતું કે દરેક ઉપગણ માટે, જ્યાં એક (મોટો) અવિભાજ્ય છે, તે નિરપેક્ષ અચળાંક માટે છે. આ અનુમાન 1990ના દાયકામાં રેન્ડમનેસ એક્સટ્રેક્ટર્સ દ્વારા પ્રેરિત વિગડરસન દ્વારા પણ ઘડવામાં આવ્યું હતું. નોંધ લો કે સરવાળો-ઉત્પાદન સમસ્યા નીચેના ઉદાહરણને કારણે બિનશરતી મર્યાદિત ક્ષેત્રોમાં ટકી શકતી નથીઃ ઉદાહરણ તરીકેઃ ચાલો એક મર્યાદિત ક્ષેત્ર બનીએ અને લઈએ. પછી ત્યારથી ઉમેરા અને ગુણાકાર હેઠળ બંધ છે, અને તેથી. આ પેથોલોજીકલ ઉદાહરણ પ્રશ્નમાં ક્ષેત્રના કોઈપણ પેટા-ક્ષેત્ર તરીકે લેવા સુધી વિસ્તરે છે. ગુણાત્મક રીતે, સરવાળા-ઉત્પાદનની સમસ્યાને મર્યાદિત ક્ષેત્રો પર હલ કરવામાં આવી છેઃ પ્રમેય (બોર્ગેન, કાટ્ઝ, તાઓ (2004)): ચાલો અવિભાજ્ય હોઈએ અને કેટલાક માટે સાથે રહેવા દો. પછી કેટલાક માટે હોય છે. બોર્ગેન, કાટ્ઝ અને ટાઓએ આ પ્રમેયને મનસ્વી ક્ષેત્રો સુધી વિસ્તાર્યો. અનૌપચારિક રીતે, નીચેનો પ્રમેય કહે છે કે જો પૂરતો મોટો સમૂહ સરવાળા અથવા ગુણાકાર હેઠળ વૃદ્ધિ પામતો નથી, તો તે મોટે ભાગે પેટા-ક્ષેત્રના વિસ્તરણમાં સમાયેલો હોય છે. પ્રમેય (બોર્ગેન, કાટ્ઝ, તાઓ (2004)): ચાલો એક મર્યાદિત ક્ષેત્રનો સબસેટ બનીએ જેથી કેટલાક લોકો માટે અને ધારો કે તે. પછી તેની સાથે એક પેટા ક્ષેત્ર અને તેની સાથે એક સમૂહ અસ્તિત્વમાં છે. તેઓ સૂચવે છે કે અચળાંક તેનાથી સ્વતંત્ર હોઈ શકે છે. મર્યાદિત ક્ષેત્ર સરવાળો-ઉત્પાદન સમસ્યા તરફના માત્રાત્મક પરિણામો સામાન્ય રીતે બે વર્ગોમાં આવે છેઃ જ્યારે લાક્ષણિકતાના સંદર્ભમાં નાનું હોય અને જ્યારે લાક્ષણિકતાના સંદર્ભમાં મોટું હોય. આનું કારણ એ છે કે દરેક સેટિંગમાં વિવિધ પ્રકારની તકનીકોનો ઉપયોગ કરવામાં આવે છે. નાના સમૂહો આ શાસનમાં, ચાલો લાક્ષણિકતાનું ક્ષેત્ર બનીએ. નોંધ લો કે ક્ષેત્ર હંમેશા મર્યાદિત હોતું નથી. જ્યારે આ કિસ્સો હોય, અને તેની લાક્ષણિકતા શૂન્ય હોય, ત્યારે-અવરોધ અવગણવામાં આવે છે. બિન-મુખ્ય ક્રમ ધરાવતા ક્ષેત્રોમાં,-પ્રતિબંધને એવી ધારણા સાથે બદલી શકાય છે કે જે કોઈપણ પેટાક્ષેત્ર સાથે ખૂબ મોટું આંતરછેદ ધરાવતું નથી. આ દિશામાં શ્રેષ્ઠ કાર્ય લી અને રોશ-ન્યુટન ઉપરના કોષ્ટકના સંકેતલિપીમાં એક ઘાતાંક પ્રાપ્ત કરવાને કારણે છે. મોટા સમૂહો જ્યારે મુખ્ય માટે, સરવાળા-ઉત્પાદનની સમસ્યાનું સમાધાન ગારેવના નીચેના પરિણામને કારણે માનવામાં આવે છેઃ પ્રમેય (ગારેવ (2007)): ચાલો. પછી. આ શ્રેણીમાં શ્રેષ્ઠ છે. આ પરિણામ 2011 માં વિન દ્વારા નોન-પ્રાઇમ ઓર્ડરના મર્યાદિત ક્ષેત્રોમાં વિસ્તૃત કરવામાં આવ્યું હતું. ચલો અને સામાન્યીકરણ સંચાલકો બોર્ગેન અને ચાંગના અન્ય સંયોજનો સમૂહો માટે બિનશરતી વૃદ્ધિ સાબિત કરે છે, જ્યાં સુધી કોઈ પર્યાપ્ત રકમ અથવા ઉત્પાદનોને ધ્યાનમાં લેઃ પ્રમેય (બોર્ગેન, ચાંગ (2003)): ધારો. પછી ત્યાં અસ્તિત્વમાં છે જેથી બધા માટે, એક છે. ઘણી કૃતિઓમાં, સરવાળા અને ગુણાકારને એક અભિવ્યક્તિમાં જોડવામાં આવે છે. આદર્શ વાક્યમાં ઉમેરો અને ગુણાકાર સહઅસ્તિત્વમાં ન હોઈ શકે, ત્યારે કોઈ અપેક્ષા રાખે છે કે સમૂહના ઉમેરા અને ગુણાકારના કોઈપણ બિન-તુચ્છ સંયોજનથી વૃદ્ધિની બાંયધરી મળવી જોઈએ. નોંધ લો કે મર્યાદિત સેટિંગ્સમાં, અથવા બિન-તુચ્છ પેટાક્ષેત્રો સાથેના ક્ષેત્રોમાં, આવા નિવેદનને વધુ અવરોધોની જરૂર છે. રસના સમૂહોમાં સમાવેશ થાય છે (પરિણામો માટે):-સ્ટીવન્સ અને વોરેન દર્શાવે છે કે-મર્ફી, રોશ-ન્યુટન અને સ્ક્રેડોવ દર્શાવે છે કે-સ્ટીવન્સ અને વોરેન દર્શાવે છે કે-સ્ટીવન્સ અને રુડનેવ દર્શાવે છે કે સમ-ફ્રી સેટ સંદર્ભો બાહ્ય કડીઓ કોમ્બિનેટોરિક્સ સંખ્યા સિદ્ધાંતમાં અલગ ગણિતના પ્રમેયોમાં પ્રમેયો સારાંશ આપે છે.