Hypergraph regularity method
ગણિતમાં, હાયપરગ્રાફ નિયમિતતા પદ્ધતિ એ ચરમ આલેખ સિદ્ધાંતમાં એક શક્તિશાળી સાધન છે જે હાયપરગ્રાફ નિયમિતતા લેમ્મા અને સંકળાયેલ ગણતરી લેમ્માના સંયુક્ત ઉપયોગનો સંદર્ભ આપે છે. તે આલેખ નિયમિતતા પદ્ધતિનું સામાન્યીકરણ છે, જે સ્ઝેમેરેડીની નિયમિતતા અને ગણતરી લેમ્માના ઉપયોગનો સંદર્ભ આપે છે. ખૂબ જ અનૌપચારિક રીતે, હાયપરગ્રાફ નિયમિતતા લેમ્મા કોઈપણ એકસમાન હાયપરગ્રાફને બંધાયેલા ભાગો (યોગ્ય સીમા અને અવ્યવસ્થિત કલ્પનાઓ સાથે) સાથે અવ્યવસ્થિત-જેવી વસ્તુમાં વિઘટિત કરે છે, જેની સાથે કામ કરવું સામાન્ય રીતે સરળ હોય છે. બીજી બાજુ, હાયપરગ્રાફ કાઉન્ટિંગ લેમ્મા રેન્ડમ જેવા ભાગોના કેટલાક સંગ્રહોમાં આપેલ આઇસોમોર્ફિઝમ વર્ગના હાયપરગ્રાફ્સની સંખ્યાનો અંદાજ કાઢે છે. આ સ્ઝેમેરેડીના નિયમિત લેમ્માનું વિસ્તરણ છે જે આપેલ કોઈપણ આલેખને બંધાયેલા સંખ્યાના ભાગોમાં વિભાજીત કરે છે જેથી ભાગો વચ્ચેની ધાર લગભગ અવ્યવસ્થિત રીતે વર્તે. તેવી જ રીતે, હાયપરગ્રાફ કાઉન્ટિંગ લેમ્મા એ ગ્રાફ કાઉન્ટિંગ લેમ્માનું સામાન્યીકરણ છે જે મોટા ગ્રાફના સબગ્રાફ તરીકે નિશ્ચિત ગ્રાફની નકલોની સંખ્યાનો અંદાજ કાઢે છે. આ પદ્ધતિની ઘણી અલગ રચનાઓ છે, જે તમામ હાયપરગ્રાફ રિમૂવલ લેમ્મા અને અન્ય સંખ્યાબંધ શક્તિશાળી પરિણામો સૂચવે છે, જેમ કે સ્ઝેમેરેડીના પ્રમેય, તેમજ તેના કેટલાક બહુ-પરિમાણીય વિસ્તરણ. નીચેના ફોર્મ્યુલેશન વી. રોડલ, બી. નાગલે, જે. સ્કોકન, એમ. સ્કાચ્ટ અને વાય. કોહાયાકાવાને કારણે છે, વૈકલ્પિક આવૃત્તિઓ માટે જુઓ તાઓ (2006), અને ગોવર્સ (2007). વ્યાખ્યાઓ હાયપરગ્રાફ નિયમિતતા અને ગણતરીના લેમ્માને ઔપચારિક રીતે જણાવવા માટે, આપણે સ્યુડો-રેન્ડમનેસ (રેન્ડમ-લિકનેસ) અને બાઉન્ડનેસની યોગ્ય કલ્પનાઓને ઔપચારિક બનાવવા તેમજ રેન્ડમ જેવા બ્લોક અને પાર્ટીશનનું વર્ણન કરવા માટે કેટલાક તકનીકી શબ્દોને વ્યાખ્યાયિત કરવાની જરૂર છે. સંકેત શિરોબિંદુઓ પર એક સમાન જૂથ સૂચવે છે. શિરોબિંદુ પાર્ટીશન પર એક-પક્ષીય-આલેખ છે. તે બધા-ઘટક શિરોબિંદુ સમૂહોનું કુટુંબ છે જે જૂથમાં ફેલાયેલું છે. ખાસ કરીને, તે એક સંપૂર્ણ-પક્ષીય-આલેખ છે. નીચે આપેલી બાબતો સાપેક્ષ ઘનતાની એક મહત્વપૂર્ણ કલ્પનાને વ્યાખ્યાયિત કરે છે, જે હાયપરગ્રાફમાં આવેલી ધાર દ્વારા ફેલાયેલી ધારના અપૂર્ણાંકનું આશરે વર્ણન કરે છે. ઉદાહરણ તરીકે, જ્યારે, જથ્થો સબહાઇપરગ્રાફમાં 2-ધાર દ્વારા રચાયેલા ત્રિકોણના અપૂર્ણાંકની બરાબર હોય છે જે 3-ધાર હોય છે. વ્યાખ્યા [સાપેક્ષ ઘનતા]. માટે, સાથે કેટલાક વર્ગો ઠીક કરો. ધારો કે તે એક પૂર્ણાંક છે. ચાલો પ્રેરિત-પક્ષીય આલેખનો સબહાઇપરગ્રાફ બનીએ. સાપેક્ષ ઘનતાને વ્યાખ્યાયિત કરો. નીચેની બાબત એ છે કે સ્યુડોરાન્ડોમનેસની યોગ્ય ધારણા છે જેનો નિયમિતતા પદ્ધતિ ઉપયોગ કરશે. અનૌપચારિક રીતે, નિયમિતતાના આ ખ્યાલ દ્વારા,-એજ () નું-એજ () પર થોડું નિયંત્રણ હોય છે. વધુ ચોક્કસપણે, આ એક સેટિંગને વ્યાખ્યાયિત કરે છે જ્યાં મોટા સબહાઇપરગ્રાફ્સમાં ધારની ઘનતા લગભગ સમાન હોય છે જે એકલા સંબંધિત ઘનતાના આધારે અપેક્ષા રાખે છે. ઔપચારિક રીતે, વ્યાખ્યા [()-નિયમિતતા]. ધારો કે તે હકારાત્મક વાસ્તવિક સંખ્યાઓ છે અને તે એક પૂર્ણાંક છે. વર્ગોની કોઈપણ પસંદગી માટે અને સંતોષકારક સબહાઇપરગ્રાફ્સના કોઈપણ સંગ્રહ માટે આપણી પાસે હોય તો તે ()-નિયમિત છે. મોટે ભાગે કહીએ તો, નીચેના સ્યુડોરાન્ડમ બ્લોકનું વર્ણન કરે છે જેમાં હાયપરગ્રાફ નિયમિતતા લેમ્મા કોઈપણ મોટા પૂરતા હાયપરગ્રાફને વિઘટિત કરે છે. સ્ઝેમેરેડી નિયમિતતામાં, 2-ધાર વિરુદ્ધ 1-ધાર (શિરોબિંદુઓ) ને નિયમિત કરવામાં આવે છે. આ સામાન્યીકૃત ધારણામાં,-ધારને નિયમિત કરવામાં આવે છે વિરુદ્ધ-ધારને બધા માટે. વધુ ચોક્કસપણે, આ-કોમ્પ્લેક્સ તરીકે ઓળખાતા નિયમિત હાયપરગ્રાફની કલ્પનાને વ્યાખ્યાયિત કરે છે, જેમાં-એજનું અસ્તિત્વ તમામ અંતર્ગત-ધારોનું અસ્તિત્વ તેમજ તેમની સંબંધિત નિયમિતતા સૂચવે છે. ઉદાહરણ તરીકે, જો 3-ધાર હોય તો, અને સંકુલમાં 2-ધાર હોય છે. વધુમાં, 2-ધાર દ્વારા બનેલા તમામ સંભવિત ત્રિકોણ પર 3-ધારની ઘનતા subhypergraphs.Definition [-રેગ્યુલર-કોમ્પ્લેક્સ] ના દરેક સંગ્રહમાં લગભગ સમાન હોય છે. એક-જટિલ એ એક-પક્ષીય આલેખની સંતોષકારક પ્રણાલી છે. હકારાત્મક વાસ્તવિક સંખ્યાઓના વેક્ટર અને પૂર્ણાંકને જોતાં, આપણે કહીએ છીએ કે-જટિલ એ-નિયમિત છે જો દરેક માટે, ઘનતા સાથે-નિયમિત હોય. દરેક માટે, is ()-ના સંદર્ભમાં નિયમિત છે. નીચે આપેલા પ્રમાણસર પાર્ટીશનનું વર્ણન કરે છે જે હાયપરગ્રાફ નિયમિતતા લેમ્મા પ્રેરિત કરશે. વિભાજનનો એ-સમાન પરિવાર એ 1-ધાર (શિરોબિંદુઓ), 2-ધાર (જોડી), 3-ધાર (ત્રિપુટીઓ) વગેરેના વિભાજનોનો ક્રમ છે. સ્ઝેમેરેડીની નિયમિતતા લેમ્મા દ્વારા મેળવેલા પાર્ટીશનથી આ એક મહત્વપૂર્ણ તફાવત છે, જ્યાં માત્ર શિરોબિંદુઓનું પાર્ટીશન કરવામાં આવે છે. હકીકતમાં, ગોવર્સે દર્શાવ્યું હતું કે માત્ર શિરોબિંદુ વિભાજન હાયપરગ્રાફ કાઉન્ટિંગ લેમ્માને સૂચિત કરવા માટે નિયમિતતાની પૂરતી મજબૂત કલ્પના આપી શકતું નથી. વ્યાખ્યા [-સમકક્ષ પાર્ટીશન]. ધારો કે તે વાસ્તવિક સંખ્યા છે, પૂર્ણાંક છે, અને હકારાત્મક વાસ્તવિકતાના વાહક છે. ચાલો હકારાત્મક પૂર્ણાંકોનો વેક્ટર બનીએ અને એક-ઘટક શિરોબિંદુ સમૂહ બનીએ. આપણે કહીએ છીએ કે પાર્ટીશનોની ફેમિલી-ઇક્વિટેબલ છે જો તે નીચેની બાબતોને સંતોષેઃ તેનું ઇક્વિટેબલ વર્ટેક્સ પાર્ટીશન છે. તે છે. પાર્ટીશનો જેથી જો અને પછી મોટાભાગના ભાગોમાં વિભાજિત કરવામાં આવે, જે તમામ સભ્યો છે. બધા માટે પરંતુ મોટા ભાગના-ટુપલ્સ પર અનન્ય-નિયમિત-સંકુલ છે જેમ કે સભ્યો તરીકે વિવિધ પાર્ટીશન વર્ગો ધરાવે છે અને. અંતે, નીચે આપેલું વ્યાખ્યાયિત કરે છે કે-સમાન હાયપરગ્રાફ પાર્ટીશનના સંદર્ભમાં નિયમિત હોવાનો અર્થ શું છે. ખાસ કરીને, આ મુખ્ય વ્યાખ્યા છે જે હાયપરગ્રાફ નિયમિતતા લેમ્મા bellow.Definition [પાર્ટીશનના સંદર્ભમાં નિયમિતતા] ના આઉટપુટનું વર્ણન કરે છે. આપણે કહીએ છીએ કે-ગ્રાફ એ પાર્ટીશનોના પરિવારના સંદર્ભમાં-નિયમિત છે, જો બધામાં પરંતુ મોટાભાગની ધાર પર એવી મિલકત હોય કે જે અને જો અનન્ય-જટિલ હોય, તો તે સંદર્ભમાં નિયમિત છે. નિવેદનો હાયપરગ્રાફ નિયમિતતા લેમ્મા તમામ હકારાત્મક વાસ્તવિક, અને કાર્યો માટે, અસ્તિત્વમાં છે અને તેથી નીચે મુજબ છે. શિરોબિંદુઓ પર કોઈપણ એકસમાન હાયપરગ્રાફ માટે, પાર્ટીશનો અને વેક્ટરનો એક પરિવાર અસ્તિત્વમાં છે જેથી, બધા માટે અને ક્યાં માટે, નીચે મુજબ હોય. પાર્ટીશનો અને દરેક માટે એક-સમાન પરિવાર છે. તે સંદર્ભમાં નિયમિત છે. હાયપરગ્રાફ કાઉન્ટિંગ લેમ્મા બધા પૂર્ણાંકો માટે નીચે મુજબ છેઃ અને ત્યાં પૂર્ણાંકો છે અને જેથી, સાથે, અને, જો શિરોબિંદુ પાર્ટીશન સાથે-નિયમિત સંકુલ હોય અને, પછી. એપ્લિકેશન્સ મુખ્ય એપ્લિકેશન કે જેના દ્વારા મોટાભાગના અન્ય લોકો અનુસરે છે તે હાયપરગ્રાફ રિમૂવલ લેમ્મા છે, જે આશરે જણાવે છે કે નિશ્ચિત અને મોટા-એકસમાન હાયપરગ્રાફ આપવામાં આવે છે, જો તેની થોડી નકલો હોય, તો તેની બધી નકલોને દૂર કરવા માટે કેટલીક હાયપરએજ કાઢી શકાય છે. તેને વધુ ઔપચારિક રીતે જણાવવા માટે, હાયપરગ્રાફ રિમૂવલ લેમ્મા બધા અને દરેક માટે, અસ્તિત્વમાં છે અને તેથી નીચે મુજબ છે. ધારો કે તે શિરોબિંદુઓ પર એકસમાન હાયપરગ્રાફ છે અને તે શિરોબિંદુઓ પર છે. જો તેમાં મોટાભાગની નકલો હોય, તો તેને મુક્ત બનાવવા માટે હાઇપરએજ કાઢી શકાય છે. આલેખ નિયમિતતા પદ્ધતિ માટેની મૂળ પ્રેરણાઓમાંની એક સ્ઝેમેરેડીના પ્રમેયને સાબિત કરવાની હતી, જે જણાવે છે કે દરેક ગાઢ સબસેટમાં મનસ્વી લંબાઈની અંકગણિત પ્રગતિ હોય છે. હકીકતમાં, ત્રિકોણ દૂર કરવાના લેમ્માના પ્રમાણમાં સરળ ઉપયોગ દ્વારા, કોઈ સાબિત કરી શકે છે કે ત્રિકોણના દરેક ગાઢ સબસેટમાં લંબાઈ 3 ની અંકગણિત પ્રગતિ હોય છે. હાયપરગ્રાફ નિયમિતતા પદ્ધતિ અને હાયપરગ્રાફ દૂર કરવાની લેમ્મા સ્ઝેમેરેડીના પ્રમેયોના ઘનતા સંસ્કરણના ઉચ્ચ-પરિમાણીય અને રિંગ એનાલોગને સાબિત કરી શકે છે, જે મૂળરૂપે ફર્સ્ટનબર્ગ અને કાટ્ઝનેલ્સન દ્વારા સાબિત કરવામાં આવ્યા હતા. હકીકતમાં, આ અભિગમ પ્રમેયો માટે પ્રથમ માત્રાત્મક સીમાઓ આપે છે. આ પ્રમેય આશરે સૂચવે છે કે કોઈપણ ગાઢ ઉપગણ કોઈપણ મર્યાદિત પેટર્ન ધરાવે છે. જ્યારે અને પેટર્ન અમુક લંબાઈની અંકગણિત પ્રગતિ હોય ત્યારે તે સ્ઝેમેરેડીના પ્રમેયની સમકક્ષ હોય છે. ફર્સ્ટેનબર્ગ અને કાટ્ઝનેલ્સન પ્રમેય ચાલો એક મર્યાદિત સબસેટ હોઈએ અને આપવામાં આવે. પછી ત્યાં એક મર્યાદિત સબસેટ અસ્તિત્વમાં છે જેમ કે દરેક સાથે તેની હોમોથેટિક નકલ હોય છે. (એટલે કે. સ્વરૂપનો સમૂહ, કેટલાક માટે અને) વધુમાં, જો કેટલાક માટે, તો એવું અસ્તિત્વ ધરાવે છે કે જે બધા માટે આ ગુણધર્મ ધરાવે છે. અન્ય સંભવિત સામાન્યીકરણ જે દૂર કરવાના લેમ્મા દ્વારા સાબિત કરી શકાય છે તે છે જ્યારે પરિમાણને વધવા દેવામાં આવે છે. ટેનગન, ટોકુશિગે, રોડલ અને સ્કાચ્ટ પ્રમેય એક મર્યાદિત વર્તુળ છે. દરેક માટે, એવું અસ્તિત્વ ધરાવે છે કે, કારણ કે, સાથેનો કોઈપણ સબસેટ (ડાબી-મોડ્યુલ તરીકે) ની આઇસોમોર્ફિક નકલનો કોસેટ ધરાવે છે. બીજા શબ્દોમાં કહીએ તો, કેટલાક એવા છે કે, જ્યાં, એક ઈન્જેક્શન છે. સંદર્ભો આલેખ સિદ્ધાંત