Blow-up lemma
1997માં જાનોસ કોમલોસ, ગેબર એન. સાર્કોઝી અને એન્ડ્રે સ્ઝેમેરેડી દ્વારા સાબિત કરાયેલ બ્લો-અપ લેમ્મા, ખાસ કરીને નિયમિતતા પદ્ધતિના સંદર્ભમાં, ચરમ આલેખ સિદ્ધાંતમાં એક મહત્વપૂર્ણ પરિણામ છે. તે જણાવે છે કે સ્ઝેમેરેડીના નિયમિત લેમ્માના નિવેદનમાં નિયમિત જોડીઓ બંધાયેલ ડિગ્રીના ફેલાયેલા આલેખને એમ્બેડ કરવાના સંદર્ભમાં સંપૂર્ણ દ્વિપક્ષી આલેખની જેમ વર્તે છે. વ્યાખ્યાઓ અને નિવેદન બ્લો-અપ લેમ્માને ઔપચારિક રીતે જણાવવા માટે, આપણે પહેલા સુપર-રેગ્યુલર જોડીની કલ્પનાને વ્યાખ્યાયિત કરવાની જરૂર છે. અતિ-નિયમિત જોડીઓ શિરોબિંદુ સમૂહના ઉપગણની જોડીને-અતિ-નિયમિત કહેવામાં આવે છે જો દરેક માટે અને સંતોષકારક હોય અને આપણી પાસે છે અને વધુમાં, બધા માટે અને બધા માટે. અહીં સાથે જોડીની સંખ્યા સૂચવે છે અને તે એક ધાર છે. બ્લો-અપ લેમ્માનું નિવેદન ક્રમ અને હકારાત્મક પરિમાણોનો આલેખ જોતાં, ત્યાં એક હકારાત્મક અસ્તિત્વ ધરાવે છે જે નીચે મુજબ છે. ચાલો મનસ્વી હકારાત્મક પૂર્ણાંકો હોઈએ અને ચાલો આપણે શિરોબિંદુઓને કદના જોડી મુજબના અસંબદ્ધ સમૂહો (ફૂલીંગ અપ) સાથે બદલીએ. આપણે એક જ શિરોબિંદુ સમૂહ પર બે આલેખ બનાવીએ છીએ. પ્રથમ આલેખ દરેક ધારને અનુરૂપ શિરોબિંદુ સમૂહો અને વચ્ચે સંપૂર્ણ દ્વિપક્ષી આલેખ સાથે બદલીને મેળવવામાં આવે છે. દરેક ધારને અને વચ્ચેની-સુપર-રેગ્યુલર જોડી સાથે બદલીને સ્પાર્સ ગ્રાફ G બનાવવામાં આવે છે. જો ગ્રાફ સાથે એમ્બેડ કરી શકાય છે, તો તે પહેલેથી જ જી. પ્રૂફ સ્કેચમાં એમ્બેડ કરી શકાય છે. બ્લો-અપ લેમ્માનો પુરાવો અનુક્રમે શિરોબિંદુઓને એમ્બેડ કરવા માટે રેન્ડમાઇઝ્ડ લોભી અલ્ગોરિધમ (આરજીએ) નો ઉપયોગ કરવા પર આધારિત છે. દલીલ પછી અલ્ગોરિધમનો નિષ્ફળતા દરને બંધાવીને આગળ વધે છે જેમ કે તે પરિમાણોની યોગ્ય પસંદગી માટે 1 (અને હકીકતમાં) કરતા ઓછો હોય છે. આનો અર્થ એ છે કે અલ્ગોરિધમ સફળ થવાની બિન-શૂન્ય તક છે, તેથી એમ્બેડિંગ અસ્તિત્વમાં હોવું જોઈએ. આ રીતે તમામ શિરોબિંદુઓને સીધા એમ્બેડ કરવાનો પ્રયાસ કામ કરતું નથી કારણ કે જ્યારે માત્ર થોડી સંખ્યામાં શિરોબિંદુઓ બાકી હોય ત્યારે અલ્ગોરિધમ અટકી શકે છે. તેના બદલે, આપણે શિરોબિંદુ સમૂહનો એક નાનો ભાગ અલગ રાખીએ છીએ, જેને બફર શિરોબિંદુઓ કહેવાય છે, અને બાકીના શિરોબિંદુઓને જોડવાનો પ્રયાસ કરીએ છીએ. બફર શિરોબિંદુઓ અને તેના બાકીના શિરોબિંદુઓ વચ્ચે સંપૂર્ણ મેળ શોધવા માટે હોલના લગ્ન પ્રમેયનો ઉપયોગ કરીને બફર શિરોબિંદુઓ પછીથી જડિત કરવામાં આવે છે. નોંધો આપણે અગાઉના વિભાગોમાં રજૂ કરાયેલા તમામ સંકેતોને ઉધાર લઈએ છીએ. જવા દો. તેમાં એમ્બેડ કરી શકાય છે, તેથી આપણે બધા માટે લખી શકીએ છીએ. શિરોબિંદુ માટે, ચાલો સૂચવીએ. માટે, અનુરૂપ શિરોબિંદુ સમૂહો વચ્ચેની ધારની ઘનતા સૂચવે છે. તે એમ્બેડિંગ છે જે આપણે બનાવવા માંગીએ છીએ. તે અંતિમ સમય છે જે પછી અલ્ગોરિધમ સમાપ્ત થાય છે. અલ્ગોરિધમનો તબક્કો 0 ની રૂપરેખાઃ પ્રારંભ લોભથી ઓછામાં ઓછા એકબીજાથી અંતરના શિરોબિંદુઓના મહત્તમ સમૂહ તરીકે શિરોબિંદુઓમાંથી બફર શિરોબિંદુઓના સમૂહને પસંદ કરો સૂચિમાં બાકીના શિરોબિંદુઓને (તેમાં) ક્રમ આપો, પ્રથમના પડોશીઓને મૂકો. હાલમાં પ્રાથમિકતા ધરાવતા શિરોબિંદુઓની કતાર જાહેર કરો, જે શરૂઆતમાં ખાલી છે. શિરોબિંદુઓ દ્વારા અનુક્રમિત સમૂહોની શ્રેણી જાહેર કરો, જે તમામ "મુક્ત સ્થળો" ના સમૂહને રજૂ કરે છે, એટલે કે, શિરોબિંદુઓમાં ખાલી શિરોબિંદુઓના સમૂહને પહેલેથી જ જડિત પડોશીઓની કોઈપણ નિકટતા શરતોનું ઉલ્લંઘન કર્યા વિના મેપ કરી શકાય છે. માટે શરૂ કરવામાં આવે છે. તબક્કો 1: રેન્ડમાઇઝ્ડ લોભી એમ્બેડિંગ બાકીના શિરોબિંદુઓના સમૂહમાંથી નીચે પ્રમાણે શિરોબિંદુ પસંદ કરો જો પ્રાથમિકતા ધરાવતા શિરોબિંદુઓની કતાર ખાલી ન હોય, તો તેમાંથી શિરોબિંદુ પસંદ કરો અન્યથા, બાકીના શિરોબિંદુઓની સૂચિમાંથી શિરોબિંદુ પસંદ કરો "સારી" પસંદગીઓના સમૂહમાંથી અનિયમિત રીતે શિરોબિંદુ માટે છબી પસંદ કરો, જ્યાં પસંદગી સારી છે જો નવા ફ્રી-સેટમાંથી કોઈ પણ અપેક્ષિત મૂલ્યથી કદમાં ખૂબ અલગ ન હોય. મફત સમૂહોને અપડેટ કરો, અને એવા શિરોબિંદુઓ મૂકો કે જેમના મુક્ત સમૂહો તેમના કદના સંદર્ભમાં છેલ્લા અપડેટમાં પ્રાથમિકતા ધરાવતા શિરોબિંદુઓના સમૂહમાં ખૂબ નાના થઈ ગયા છે જો કતારમાં કોઈપણ સમૂહનો પૂરતો મોટો અપૂર્ણાંક હોય તો તેને રદ કરો જો ત્યાં બિન-બફર શિરોબિંદુઓ ક્યાં તો એમ્બેડ કરવા માટે બાકી છે અથવા, સમયને અપડેટ કરો અને પગલું 1 પર પાછા જાઓ; અન્યથા તબક્કા 2 પર આગળ વધો. તબક્કો 2: બાકીના શિરોબિંદુઓ માટે કોનિગ-હોલ મેચિંગ એમ્બેડ કરવા માટે બાકી રહેલા શિરોબિંદુઓના સમૂહને ધ્યાનમાં લો, જે ચોક્કસપણે છે, અને મુક્ત ફોલ્લીઓનો સમૂહ. આ બે સમૂહો વચ્ચે દ્વિપક્ષી આલેખ બનાવો, દરેકને જોડો અને આ દ્વિપક્ષી આલેખમાં એક સંપૂર્ણ મેળ શોધો. આ મેળ અનુસાર એમ્બેડ કરો. ચોકસાઈનો પુરાવો ચોકસાઈનો પુરાવો તકનીકી અને ખૂબ જ સંકળાયેલો છે, તેથી અમે વિગતોને અવગણીએ છીએ. મુખ્ય દલીલ નીચે પ્રમાણે આગળ વધે છેઃ પગલું 1: મોટાભાગના શિરોબિંદુઓ સારા હોય છે, અને પૂરતા શિરોબિંદુઓ મુક્ત હોય છે, એક સાથે તેના પર ઇન્ડક્શન દ્વારા સાબિત કરો કે જો તે સમયે શિરોબિંદુ હોય, તો પછી પસંદગીઓનો માત્ર એક નાનો ભાગ ખરાબ હોય છે, બધા મુક્ત સમૂહો અનમ્બેડેડ શિરોબિંદુઓ માટે એકદમ મોટા હોય છે. તે ઘટનાનો વિચાર કરો કે જ્યાં પ્રથમ તબક્કા દરમિયાન કોઈ શિરોબિંદુઓ જડિત નથી, દરેક માટે એક એવો સમય હોય છે કે તે સમયે મુક્ત શિરોબિંદુઓનો અપૂર્ણાંક નાનો હતો. પછી, આપણે સાબિત કરીએ છીએ કે થવાની સંભાવના ઓછી છે. પગલું 3: તબક્કો 1 ઉચ્ચ સંભાવના સાથે સફળ થાય છે પ્રથમ તબક્કો નિષ્ફળ થઈ શકે તે એકમાત્ર રસ્તો એ છે કે જો તે સ્થગિત થાય, કારણ કે પ્રથમ પગલાથી આપણે જાણીએ છીએ કે હંમેશા સારા શિરોબિંદુઓની પૂરતી પસંદગી હોય છે. જ્યારે કતાર ખૂબ લાંબી હોય ત્યારે જ કાર્યક્રમ બંધ થાય છે. પછી દલીલ નિષ્ફળતાના તમામ પ્રકારો પર જોડાણ દ્વારા આગળ વધે છે, નોંધે છે કે કોઈપણ ચોક્કસ પસંદગી માટે, અને નિષ્ફળ થયેલી કતારના સબસેટનું પ્રતિનિધિત્વ કરવા સાથે, ટ્રિપલ "મુખ્ય લેમ્મા" ની શરતોને સંતોષે છે, અને આમ થવાની સંભાવના ઓછી હોય છે. પગલું 4: પ્રારંભિક તબક્કામાં કોઈ કતાર નથી યાદ રાખો કે સૂચિ સેટ કરવામાં આવી હતી જેથી બફરમાં શિરોબિંદુઓના પડોશીઓ પહેલા એમ્બેડ થઈ શકે. જ્યાં સુધી આ તમામ શિરોબિંદુઓ જડિત ન થાય ત્યાં સુધી સમયને પ્રારંભિક તબક્કો કહેવામાં આવે છે. ઇન્ડક્શન દ્વારા સાબિત કરો કે પ્રારંભિક તબક્કા દરમિયાન કતારમાં કોઈ શિરોબિંદુઓ ઉમેરાતા નથી. તે અનુસરે છે કે બફર શિરોબિંદુઓના તમામ પડોશીઓ બાકીના શિરોબિંદુઓ પહેલાં ઉમેરાય છે. પગલું 5: બફર શિરોબિંદુઓમાં પૂરતા પ્રમાણમાં મુક્ત ફોલ્લીઓ હોય છે કોઈપણ માટે અને, આપણે સંભાવના પર પૂરતા પ્રમાણમાં મોટી નીચલી સીમા શોધી શકીએ છીએ કે, કોઈપણ શિરોબિંદુઓ જડિત થયા તે પહેલાં મુક્ત હતી તેવી ધારણા પર શરતી. પગલું 6: તબક્કો 2 ઉચ્ચ સંભાવના સાથે સફળ થાય છે હોલના લગ્ન પ્રમેય અનુસાર, તબક્કો 2 ત્યારે જ નિષ્ફળ જાય છે જ્યારે હોલની સ્થિતિનું ઉલ્લંઘન કરવામાં આવે. આવું થવા માટે, કેટલાક અને આવા હોવા જોઈએ. મુક્ત સમૂહોની વિશાળતા દ્વારા ખૂબ નાનું ન હોઈ શકે (પગલું 1). જો ખૂબ મોટી હોય, તો ઉચ્ચ સંભાવના સાથે, તેથી આવા કિસ્સામાં નિષ્ફળતાની સંભાવના ઓછી હશે. જો તે ન તો ખૂબ નાનું હોય કે ન તો ખૂબ મોટું હોય, તો તે નોંધવું કે તે બિનઉપયોગી શિરોબિંદુઓનો મોટો સમૂહ છે, આપણે મુખ્ય લેમ્માનો ઉપયોગ કરી શકીએ છીએ અને નિષ્ફળતાની સંભાવનાને સંઘબદ્ધ કરી શકીએ છીએ. એપ્લિકેશન્સ ગાઢ આલેખને એમ્બેડ કરવા માટે બ્લો-અપ લેમ્માની સંખ્યાબંધ એપ્લિકેશનો છે. પોસા-સીમોર અનુમાન 1962માં, લાજોસ પોસાએ અનુમાન લગાવ્યું હતું કે ઓછામાં ઓછી ડિગ્રી ધરાવતા દરેક-વર્ટેક્સ આલેખમાં ઓછામાં ઓછો હેમિલ્ટોનિયન ચક્રનો વર્ગ હોય છે, જે ડીરાકના પ્રમેયને સામાન્ય બનાવે છે. પોલ સીમોર દ્વારા 1974માં આ અનુમાનને આગળ વધારીને નીચે મુજબ કરવામાં આવ્યું હતુંઃ લઘુત્તમ ડિગ્રી ધરાવતા શિરોબિંદુઓ પરનો દરેક આલેખ ઓછામાં ઓછો હેમિલ્ટોનિયન ચક્રની-th શક્તિ ધરાવે છે. 1998 માં (નિશ્ચિત માટે) તમામ પૂરતા પ્રમાણમાં મોટા મૂલ્યો માટેના અનુમાનને સાબિત કરવા માટે કોમ્લોસ, સાર્કોઝી અને સ્ઝેમેરેડી દ્વારા બ્લો-અપ લેમ્માનો ઉપયોગ કરવામાં આવ્યો હતો. એલોન-યુસ્ટર અનુમાન 1995માં, નોગા એલોન અને રાફેલ યુસ્ટરએ જાણીતા હેજનલ-ઝેમેરેડી પ્રમેયના સામાન્યીકરણને મનસ્વી-પરિબળો (માત્ર સંપૂર્ણ આલેખને બદલે) તરીકે ધ્યાનમાં લીધું અને નીચેનું નિવેદન સાબિત કર્યુંઃ શિરોબિંદુઓ સાથેના દરેક નિશ્ચિત આલેખ માટે, n શિરોબિંદુઓ સાથે અને લઘુત્તમ ડિગ્રી સાથે કોઈપણ આલેખ G માં H ની શિરોબિંદુ વિચ્છેદિત નકલો હોય છે. તેઓ એવું પણ અનુમાન કરે છે કે પરિણામ માત્ર એક અચળાંક (રેખીયને બદલે) ભૂલ સાથે ધરાવે છેઃ દરેક પૂર્ણાંક માટે એક અચળાંક અસ્તિત્વ ધરાવે છે કે શિરોબિંદુઓ સાથે દરેક આલેખ માટે, શિરોબિંદુઓ સાથે અને લઘુત્તમ ડિગ્રી સાથે કોઈપણ આલેખમાં ઓછામાં ઓછી શિરોબિંદુ વિચ્છેદિત નકલો હોય છે. આ અનુમાન 2001માં કોમ્લોસ, સાર્કોઝી અને સ્ઝેમેરેદી દ્વારા બ્લો-અપ લેમ્માનો ઉપયોગ કરીને સાબિત કરવામાં આવ્યું હતું. ઇતિહાસ અને પ્રકારો બ્લો-અપ લેમ્મા, સૌપ્રથમ 1997 માં કોમ્લોસ, સાર્કોઝી અને સ્ઝેમેરેડી દ્વારા પ્રકાશિત કરવામાં આવ્યું હતું, જે ફેલાયેલા આલેખને એમ્બેડ કરવા માટે નિયમિતતા પદ્ધતિનો ઉપયોગ કરીને હાલની સાબિતી તકનીકોના શુદ્ધિકરણ તરીકે ઉભરી આવ્યું હતું, જેમ કે વૃક્ષો ફેલાવવા અંગેના બોલોબાસ અનુમાનના પુરાવા તરીકે, હેમિલ્ટોનિયન ચક્રની કે-થી ગ્રાફ શક્તિને સમાવવા માટે જરૂરી લઘુત્તમ ડિગ્રી વિશે પોસા-સીમોર અનુમાન પર કામ કરે છે, અને ગ્રાફ માટે જરૂરી લઘુત્તમ ડિગ્રી પર એલોન-યુસ્ટર અનુમાનનો પુરાવો સંપૂર્ણ એચ-પરિબળ ધરાવે છે. આ તમામ પ્રમેયોના પુરાવા મોટાભાગના શિરોબિંદુઓને એમ્બેડ કરવા માટે રેન્ડમાઇઝ્ડ લોભી અલ્ગોરિધમનો ઉપયોગ કરવા પર આધાર રાખે છે, અને પછી બાકીના શિરોબિંદુઓ માટે એમ્બેડિંગ શોધવા માટે કોનિગ-હોલ જેવી દલીલનો ઉપયોગ કરે છે. બ્લો-અપ લેમ્માના પ્રથમ પુરાવાએ પણ સમાન દલીલનો ઉપયોગ કર્યો હતો. પાછળથી 1997 માં, જો કે, તે જ લેખકોએ અન્ય એક પેપર પ્રકાશિત કર્યું જેમાં તેને નિર્ધારક બનાવવા માટે રેન્ડમાઇઝ્ડ અલ્ગોરિધમમાં સુધારો જોવા મળ્યો. પીટર કીવાશે 2010માં બ્લો-અપ લેમ્માનું હાયપરગ્રાફમાં સામાન્યીકરણ શોધી કાઢ્યું હતું. સ્ટીફન ગ્લોક અને ફેલિક્સ જોસે 2018માં સપ્તરંગી આલેખ માટે બ્લો-અપ લેમ્માનો એક પ્રકાર શોધ્યો હતો. 2019માં, પીટર એલન, જુલિયા બોટ્ટર, હાયપ હેન, યોશીહારુ કોહાયાકાવા અને યુરી પર્સને ગ્રાફ થિયરીમાં બાઉન્ડેડ ડિગ્રી ગ્રાફને રેન્ડમ અને સ્યુડોરાન્ડમ ગ્રાફમાં એમ્બેડ કરવા માટે બ્લો-અપ લેમ્માના વિરલ એનાલોગ શોધી કાઢ્યા હતા.