Container method
(હાયપરગ્રાફ) કન્ટેનરની પદ્ધતિ એ એક શક્તિશાળી સાધન છે જે લાક્ષણિક માળખાને વર્ગીકૃત કરવામાં અને/અથવા સ્થાનિક અવરોધોના નિર્ધારિત સમૂહ સાથે અલગ વસ્તુઓના પરિવારો વિશેના આત્યંતિક પ્રશ્નોના જવાબ આપવામાં મદદ કરી શકે છે. આવા પ્રશ્નો એક્સ્ટ્રીમ ગ્રાફ થિયરી, એડિટિવ કોમ્બિનેટોરિક્સ, ડિસ્ક્રીટ જ્યોમેટ્રી, કોડિંગ થિયરી અને રામસે થિયરીમાં કુદરતી રીતે ઉદ્ભવે છે; તેમાં સંકળાયેલ ક્ષેત્રોની કેટલીક સૌથી શાસ્ત્રીય સમસ્યાઓનો સમાવેશ થાય છે. આ સમસ્યાઓને નીચેના સ્વરૂપના પ્રશ્નો તરીકે વ્યક્ત કરી શકાય છેઃ ધાર સમૂહ સાથે મર્યાદિત શિરોબિંદુ સમૂહ પર હાયપરગ્રાફ આપવામાં આવે છે (એટલે કે. કેટલાક કદની મર્યાદાઓ સાથેના ઉપગણોનો સંગ્રહ), આપણે તેના સ્વતંત્ર સમૂહો વિશે શું કહી શકીએ (એટલે કે. તેના તે ઉપગણમાં કોઈ તત્વ નથી)? હાયપરગ્રાફ કન્ટેનર લેમ્મા આવા પ્રશ્નોના ઉકેલ માટે એક પદ્ધતિ પ્રદાન કરે છે. ઇતિહાસ એ એક્સ્ટ્રીમ ગ્રાફ થિયરીની પાયાની સમસ્યાઓમાંની એક, જે 1907માં મેન્ટલ અને 1940ના દાયકાના તુરાનના કાર્ય સાથે સંબંધિત છે, તે એવા આલેખની લાક્ષણિકતા દર્શાવવા માટે કહે છે જેમાં સબગ્રાફ તરીકે પ્રતિબંધિત અમુક નિશ્ચિતની નકલ ન હોય. એક અલગ ક્ષેત્રમાં, એડિટિવ કોમ્બિનેટોરિક્સમાં એક પ્રેરક પ્રશ્ન એ સમજવાનો છે કે-ટર્મ અંકગણિત પ્રગતિ વિના પૂર્ણાંકોનો સમૂહ કેટલો મોટો હોઈ શકે છે, આ કદ પર ઉપરની સીમાઓ રોથ () અને સ્ઝેમેરેડી (સામાન્ય) દ્વારા આપવામાં આવે છે. કન્ટેનરની પદ્ધતિ (આલેખમાં) શરૂઆતમાં 1980 માં ક્લેઇટમેન અને વિન્સ્ટન દ્વારા શરૂ કરવામાં આવી હતી, જેમણે 4-ચક્ર વિના જાળી અને આલેખની સંખ્યાને મર્યાદિત કરી હતી. કન્ટેનર-શૈલીના લેમ્માને વિવિધ સંદર્ભોમાં બહુવિધ ગણિતશાસ્ત્રીઓ દ્વારા સ્વતંત્ર રીતે વિકસાવવામાં આવ્યા હતા, ખાસ કરીને સપોઝેન્કો સહિત, જેમણે શરૂઆતમાં 2002-2003 માં આ અભિગમનો ઉપયોગ નિયમિત આલેખમાં સ્વતંત્ર સમૂહોની ગણતરી કરવા, અબેલિયન જૂથોમાં સરવાળો-મુક્ત સમૂહો, અને અન્ય વિવિધ ગણતરી સમસ્યાઓનો અભ્યાસ કરવા માટે કર્યો હતો. મુખ્ય વિચાર અને અનૌપચારિક નિવેદન સંયોજનમાં ઘણી સમસ્યાઓને આલેખ અને હાયપરગ્રાફમાં સ્વતંત્ર સમૂહો વિશેના પ્રશ્નો તરીકે પુનઃરચના કરી શકાય છે. ઉદાહરણ તરીકે, ધારો કે આપણે પૂર્ણાંકોના સબસેટ્સને સમજવા માંગીએ છીએ, જેને આપણે-ટર્મ અંકગણિત પ્રગતિના અભાવ દ્વારા સૂચવીએ છીએ. આ સમૂહો બરાબર-યુનિફોર્મ હાયપરગ્રાફમાં સ્વતંત્ર સમૂહો છે, જ્યાં તમામ-ટર્મ અંકગણિત પ્રગતિઓનો સંગ્રહ છે. ઉપરોક્ત (અને અન્ય ઘણા) ઉદાહરણોમાં, હાયપરગ્રાફ વિશે સામાન્ય રીતે બે કુદરતી વર્ગની સમસ્યાઓ ઊભી થાય છેઃ મહત્તમ સ્વતંત્ર સેટનું કદ કેટલું હોય છે? મહત્તમ કદના સ્વતંત્ર સમૂહોનો સંગ્રહ કેવો દેખાય છે? સ્વતંત્ર સમૂહો કેવી રીતે હોઈ શકે? "લાક્ષણિક" સ્વતંત્ર સમૂહ કેવો દેખાય છે? આ સમસ્યાઓ એક સરળ નિરીક્ષણ દ્વારા જોડાયેલી છે. ધારો કે તે સૌથી મોટા સ્વતંત્ર સમૂહનું કદ છે અને ધારો કે તેમાં સ્વતંત્ર સમૂહ છે. પછી, જ્યાં નીચલી સીમા મહત્તમ સ્વતંત્ર સમૂહના તમામ ઉપગણને લઈને અનુસરે છે. આ સીમાઓ એકબીજાથી પ્રમાણમાં દૂર હોય છે સિવાય કે તે ખૂબ મોટી હોય, હાયપરગ્રાફના શિરોબિંદુઓની સંખ્યાની નજીક હોય. જો કે, ઘણા હાયપરગ્રાફ્સ કે જે કુદરતી રીતે સંયુક્ત સમસ્યાઓમાં ઉદ્ભવે છે, તેમાં આપણી પાસે એવું માનવાનું કારણ છે કે નીચલી સીમા સાચા મૂલ્યની નજીક છે; આમ પ્રાથમિક ધ્યેય ઉપરની સીમાઓને સુધારવાનું છે. હાયપરગ્રાફ કન્ટેનર લેમ્મા હાયપરગ્રાફમાં સ્વતંત્ર સમૂહોના પરિવારની રચના અને કદને સમજવા માટે એક શક્તિશાળી અભિગમ પ્રદાન કરે છે. તેના મૂળમાં, હાયપરગ્રાફ કન્ટેનર પદ્ધતિ આપણને હાયપરગ્રાફ, કન્ટેનરનો સંગ્રહ, શિરોબિંદુઓના સબસેટમાંથી બહાર કાઢવા માટે સક્ષમ બનાવે છે જે નીચેના ગુણધર્મોને સંતોષે છેઃ ત્યાં ઘણા બધા કન્ટેનર નથી. દરેક કન્ટેનર સૌથી મોટા સ્વતંત્ર સમૂહ કરતાં ઘણું મોટું નથી. દરેક કન્ટેનરમાં થોડી ધાર હોય છે. હાયપરગ્રાફમાં દરેક સ્વતંત્ર સમૂહ સંપૂર્ણપણે અમુક કન્ટેનરમાં સમાવિષ્ટ હોય છે. નામ પાત્ર આ છેલ્લી શરતનો ઉલ્લેખ કરે છે. આવા કન્ટેનર ઘણીવાર સ્વતંત્ર સમૂહો (કન્ટેનરના સબસેટ) ના કુટુંબની લાક્ષણિકતા દર્શાવવા અને હાયપરગ્રાફના સ્વતંત્ર સમૂહોની ગણતરી કરવા માટે (કન્ટેનરના તમામ સંભવિત સબસેટ્સને ધ્યાનમાં લઈને) અસરકારક અભિગમ પ્રદાન કરે છે. હાયપરગ્રાફ કન્ટેનર લેમ્મા ઉપરોક્ત કન્ટેનરનું વિઘટન બે ટુકડાઓમાં પ્રાપ્ત કરે છે. તે એક નિર્ધારિત કાર્યનું નિર્માણ કરે છે. પછી, તે એક અલ્ગોરિધમ પ્રદાન કરે છે જે હાયપરગ્રાફમાં દરેક સ્વતંત્ર સમૂહમાંથી બહાર કાઢે છે, શિરોબિંદુઓનો પ્રમાણમાં નાનો સંગ્રહ, જેને ફિંગરપ્રિન્ટ કહેવાય છે, તે ગુણધર્મ સાથે. પછી, કન્ટેનર એ ઉપરોક્ત પ્રક્રિયામાં ઉદ્ભવતા સેટનો સંગ્રહ છે, અને ફિંગરપ્રિન્ટ્સનું નાનું કદ આવા કન્ટેનર સેટની સંખ્યા પર સારું નિયંત્રણ પ્રદાન કરે છે. ગ્રાફ કન્ટેનર અલ્ગોરિધમ અમે પ્રથમ ગ્રાફમાં સ્વતંત્ર સમૂહોની સંખ્યા પર મજબૂત ઉપલી સીમાઓ બતાવવા માટેની પદ્ધતિનું વર્ણન કરીએ છીએ; આ પ્રદર્શન સમોતિજના ગ્રાફ કન્ટેનર પદ્ધતિ વિશેના સર્વેક્ષણમાંથી સ્વીકારવામાં આવ્યું છે, જેનો મૂળ ઉપયોગ ક્લેઇટમેન-વિન્સ્ટન અને સપોઝેન્કો દ્વારા કરવામાં આવ્યો હતો. નોંધ અમે નીચેના વિભાગમાં નીચેના સંકેતનો ઉપયોગ કરીએ છીએ. શિરોબિંદુઓ પરનો આલેખ છે, જ્યાં શિરોબિંદુ સમૂહ (મનસ્વી) ક્રમથી સજ્જ છે. ચાલો કદ સાથે સ્વતંત્ર સમૂહોનો સંગ્રહ બનીએ. ચાલો કદના સ્વતંત્ર સમૂહોની સંખ્યા હોઈએ. શિરોબિંદુ ઉપગણનો મહત્તમ-ડિગ્રી ક્રમ એ પ્રેરિત ઉપગણમાં તેમની ડિગ્રી દ્વારા શિરોબિંદુઓનો ક્રમ છે. ક્લેઇટમેન-વિન્સ્ટન અલ્ગોરિધમ નીચેનું અલ્ગોરિધમ ગ્રાફમાં દરેક સ્વતંત્ર સમૂહ માટે એક નાનું "ફિંગરપ્રિન્ટ" આપે છે અને ફિંગરપ્રિન્ટનું નિર્ણાયક કાર્ય ખૂબ મોટા ન હોય તેવા સબસેટનું નિર્માણ કરે છે જેમાં સંપૂર્ણ સ્વતંત્ર સમૂહ ફિક્સ ગ્રાફ, સ્વતંત્ર સમૂહ અને હકારાત્મક પૂર્ણાંક હોય છે. પ્રારંભઃ ચાલો. માટે પુનરાવર્તનઃ ન્યૂનતમ અનુક્રમણિકા શોધવાનો મહત્તમ-ડિગ્રી ક્રમ એવી રીતે બનાવો કે (એટલે કે. પ્રેરિત સબગ્રાફમાં સૌથી મોટા ડિગ્રીનું શિરોબિંદુ) ચાલો, શિરોબિંદુ ક્યાં છે. વેક્ટર અને શિરોબિંદુ સમૂહને આઉટપુટ કરો. વિશ્લેષણ બાંધકામ દ્વારા, ઉપરોક્ત અલ્ગોરિધમનો આઉટપુટ ગુણધર્મ ધરાવે છે, જે નોંધે છે કે તે એક શિરોબિંદુ સબસેટ છે જે સંપૂર્ણપણે દ્વારા નિર્ધારિત થાય છે અને અન્યથા તેના કાર્ય દ્વારા નહીં. આના પર ભાર મૂકવા માટે આપણે લખીશું. આપણે એ પણ અવલોકન કર્યું છે કે આપણે ઉપરના અલ્ગોરિધમમાં સમૂહને માત્ર વેક્ટરથી પુનઃરચના કરી શકીએ છીએ. આ સૂચવે છે કે ફિંગરપ્રિન્ટની સારી પસંદગી અને કન્ટેનર માટે સારી પસંદગી હોઈ શકે છે. વધુ સ્પષ્ટ રીતે કહીએ તો, આપણે કેટલાક કદના સ્વતંત્ર સમૂહોની સંખ્યાને આઉટપુટ સિક્વન્સના સરવાળા તરીકે બાંધી શકીએ છીએ, જ્યાં આપણે ગ્રાફના સ્વતંત્ર સમૂહોની કુલ સંખ્યા પર બંધ મેળવવા માટે સરવાળો કરી શકીએ છીએઃ આ ઉપલી મર્યાદાને ઘટાડવાનો પ્રયાસ કરતી વખતે, આપણે તે સંતુલન પસંદ કરવા માંગીએ છીએ/આ બે શરતોને ઘટાડે છે. આ પરિણામ શિરોબિંદુઓને મહત્તમ ડિગ્રી (ઘટાડવા માટે) દ્વારા ક્રમ આપવાના મૂલ્યને સમજાવે છે. લેમ્માસ ઉપરોક્ત અસમાનતાઓ અને અવલોકનો વધુ સામાન્ય સેટિંગમાં કહી શકાય, જે વેક્ટર પર સ્પષ્ટ રકમથી અલગ પડે છે. લેમ્મા 1: સાથે આલેખ આપવામાં આવે છે અને ધારો કે પૂર્ણાંક અને વાસ્તવિક સંખ્યાઓ સંતુષ્ટ કરે છે. ધારો કે ઓછામાં ઓછા શિરોબિંદુઓ પર દરેક પ્રેરિત સબગ્રાફ ઓછામાં ઓછી ધાર ઘનતા ધરાવે છે. પછી દરેક પૂર્ણાંક માટે, લેમ્મા 2: ચાલો શિરોબિંદુઓ પર આલેખ બનાવીએ અને ધારીએ કે પૂર્ણાંક અને વાસ્તવિક એવી રીતે પસંદ કરવામાં આવે છે. જો ઓછામાં ઓછા શિરોબિંદુઓના તમામ ઉપગણમાં ઓછામાં ઓછી ધાર હોય, તો ત્યાં શિરોબિંદુઓના ઉપગણોનો સંગ્રહ ("ફિંગરપ્રિન્ટ્સ") અને એક નિર્ધારક કાર્ય હોય છે, જેથી દરેક સ્વતંત્ર સમૂહ માટે, એવું હોય. હાયપરગ્રાફ કન્ટેનર લેમ્મા અનૌપચારિક રીતે, હાયપરગ્રાફ કન્ટેનર લેમ્મા આપણને કહે છે કે આપણે દરેક સ્વતંત્ર સમૂહને એક નાની ફિંગરપ્રિન્ટ સોંપી શકીએ છીએ, જેથી સમાન ફિંગરપ્રિન્ટવાળા તમામ સ્વતંત્ર સમૂહ સમાન મોટા સમૂહ, સંકળાયેલ કન્ટેનરના હોય, જેનું કદ હાયપરગ્રાફના શિરોબિંદુઓની સંખ્યાથી દૂર હોય. વધુમાં, આ ફિંગરપ્રિન્ટ્સ નાના હોય છે (અને આમ ત્યાં થોડા કન્ટેનર હોય છે), અને આપણે હાયપરગ્રાફના કેટલાક સરળ ગુણધર્મોનો ઉપયોગ કરીને આવશ્યકપણે શ્રેષ્ઠ રીતે તેમના કદને ઉપર બાંધી શકીએ છીએ. આપણે યુનિફોર્મ હાયપરગ્રાફ સાથે સંકળાયેલા નીચેના સંકેતોને યાદ કરીએ છીએ. હકારાત્મક પૂર્ણાંકો માટે વ્યાખ્યાયિત કરો, જ્યાં. ચાલો સ્વતંત્ર સમૂહોનો સંગ્રહ બનીએ. આવા કેટલાક સ્વતંત્ર સમૂહને સૂચવશે. નિવેદન આપણે બાલોગ, મોરિસ, સમોતિજ અને સેક્સટનના કાર્યમાં મળેલા આ લેમ્માનું સંસ્કરણ જણાવીએ છીએ ચાલો એક સમાન હાયપરગ્રાફ બનીએ અને ધારો કે દરેક અને કેટલાક માટે, આપણી પાસે તે છે. પછી, ત્યાં એક સંગ્રહ અને એક કાર્ય છે જે દરેક માટે અને સાથે અસ્તિત્વમાં છે. દરેક માટે અને. ઉદાહરણ એપ્લિકેશન્સ રેગ્યુલર ગ્રાફ્સ ઇન્ડિપેન્ડન્ટ સેટની સંખ્યા પર અપર બાઉન્ડ આપણે બતાવીશું કે ત્યાં એક એબ્સોલ્યુટ કોન્સ્ટન્ટ છે જે દરેક-વર્ટેક્સ-રેગ્યુલર ગ્રાફને સંતોષે છે. આપણે માટે તુચ્છ બાઉન્ડનો ઉપયોગ કરીને દરેક કદના સ્વતંત્ર સમૂહોની સંખ્યાને બાંધી શકીએ છીએ. મોટા માટે, આ પરિમાણો સાથે લો,-નિયમિત આલેખ લેમ્મા 1 ની શરતોને સંતોષે છે અને આમ, બધા પર સારાંશ આપે છે, જે ઇચ્છિત પરિણામ આપે છે જ્યારે આપણે સમ-ફ્રી સેટમાં પ્લગ કરીએ છીએ જો કોઈ સંતોષકારક ન હોય તો અબેલિયન જૂથના તત્વોનો સમૂહ સરવાળો-મુક્ત કહેવાય છે. આપણે બતાવીશું કે તેમાં મહત્તમ રકમ-મુક્ત ઉપગણ છે. આ નિયમિત આલેખમાં સ્વતંત્ર સમૂહોની સંખ્યા પર આપણી ઉપરની સીમાઓથી અનુસરશે. આ જોવા માટે, આપણે સહાયક આલેખ બનાવવાની જરૂર પડશે. આપણે સૌપ્રથમ અવલોકન કરીએ છીએ કે નીચલા ક્રમની શરતો સુધી, આપણે આપણું ધ્યાન ઓછામાં ઓછા નાના ઘટકો સાથે રકમ-મુક્ત સમૂહો સુધી મર્યાદિત કરી શકીએ છીએ (કારણ કે આના પૂરકમાં ઉપગણની સંખ્યા સૌથી વધુ છે). કેટલાક ઉપગણને જોતાં, આપણે શિરોબિંદુ સમૂહ અને ધાર સમૂહ સાથે સહાયક આલેખ વ્યાખ્યાયિત કરીએ છીએ, અને અવલોકન કરીએ છીએ કે આપણો સહાયક આલેખ નિયમિત છે કારણ કે દરેક ઘટક તેના કરતા નાનો છે. પછી જો સબસેટના સૌથી નાના ઘટકો હોય, તો સેટ ગ્રાફમાં એક સ્વતંત્ર સમૂહ છે. પછી, આપણી અગાઉની બાઉન્ડ દ્વારા, આપણે જોઈએ છીએ કે સમ-ફ્રી સબસેટ્સની સંખ્યા મહત્તમ ત્રિકોણ-મુક્ત આલેખ પર હોય છે. આપણે શિરોબિંદુઓ સાથે ત્રિકોણ-મુક્ત આલેખની સંખ્યા પર એસિમ્પ્ટોટિકલી ટાઈટ અપર બાઉન્ડ આપીને આંકડાકીય પ્રશ્નનો જવાબ આપવા માટે હાયપરગ્રાફ કન્ટેનર લેમ્માનો ઉપયોગ કરવાનું ઉદાહરણ આપીએ છીએ. અનૌપચારિક નિવેદન દ્વિપક્ષી આલેખ ત્રિકોણ મુક્ત હોવાથી, શિરોબિંદુઓ સાથે ત્રિકોણ મુક્ત આલેખની સંખ્યા ઓછામાં ઓછી સંતુલિત સંપૂર્ણ દ્વિપક્ષી આલેખના તમામ સંભવિત પેટા આલેખની ગણતરી કરીને મેળવવામાં આવે છે. આપણે શિરોબિંદુ સમૂહ અને ધાર સમૂહ સાથે સહાયક-સમાન હાયપરગ્રાફ બનાવી શકીએ છીએ. આ હાયપરગ્રાફ ત્રિકોણને એ અર્થમાં "એન્કોડ" કરે છે કે શિરોબિંદુઓ પર ત્રિકોણ-મુક્ત આલેખનો પરિવાર બરાબર આ હાયપરગ્રાફના સ્વતંત્ર સમૂહોનો સંગ્રહ છે. ઉપરોક્ત હાયપરગ્રાફ એક સરસ ડિગ્રી વિતરણ ધરાવે છેઃ ની દરેક ધાર, અને આમ શિરોબિંદુ બરાબર ત્રિકોણમાં સમાયેલ છે અને તેમાં તત્વોની દરેક જોડી વધુમાં વધુ 1 ત્રિકોણમાં સમાયેલ છે. તેથી, હાયપરગ્રાફ કન્ટેનર લેમ્માને (પુનરાવર્તિત રીતે) લાગુ કરીને, આપણે બતાવી શકીએ છીએ કે કન્ટેનરનો એક પરિવાર છે જેમાં દરેકમાં થોડા ત્રિકોણ હોય છે જેમાં દરેક ત્રિકોણ-મુક્ત આલેખ/હાયપરગ્રાફનો સ્વતંત્ર સમૂહ હોય છે. ત્રિકોણ-મુક્ત આલેખની સંખ્યા પર ઉચ્ચ મર્યાદા આપણે પહેલા સામાન્ય હાયપરગ્રાફ કન્ટેનર લેમ્માને નીચે પ્રમાણે 3-સમાન હાયપરગ્રાફમાં વિશેષતા આપીએ છીએઃ લેમ્માઃ દરેક માટે, એવું અસ્તિત્વ ધરાવે છે કે જે નીચે મુજબ ધરાવે છે. ચાલો સરેરાશ ડિગ્રી સાથે 3-સમાન હાયપરગ્રાફ હોઈએ અને ધારો કે તે. પછી મોટાભાગના કન્ટેનરનો સંગ્રહ અસ્તિત્વમાં છે જેમ કે દરેક માટે, બધા માટે અસ્તિત્વમાં છે આ લેમ્માને પુનરાવર્તિત રીતે લાગુ કરવાથી નીચેનો પ્રમેય મળશે (નીચે સાબિત કર્યા મુજબ): પ્રમેયઃ બધા માટે, એવું અસ્તિત્વમાં છે કે જે નીચે મુજબ છે. દરેક હકારાત્મક પૂર્ણાંક માટે, શિરોબિંદુઓ પર આલેખનો સંગ્રહ અસ્તિત્વમાં છે જેમ કે દરેક ત્રિકોણ કરતા ઓછા હોય છે, શિરોબિંદુઓ પરનો દરેક ત્રિકોણ-મુક્ત આલેખ કેટલાકમાં સમાયેલો હોય છે. પુરાવોઃ ઉપર વર્ણવેલ હાયપરગ્રાફને ધ્યાનમાં લો. અગાઉ અનૌપચારિક રીતે જોવામાં આવ્યું તેમ, હાયપરગ્રાફ દરેક માટે સંતોષ આપે છે. તેથી, આપણે ઉપગણોનો અમુક સંગ્રહ શોધવા માટે ઉપરના લેમ્માને સાથે લાગુ કરી શકીએ છીએ (એટલે કે. શિરોબિંદુઓ પરના આલેખ) જેમ કે દરેક ત્રિકોણ મુક્ત આલેખ કેટલાકનો પેટા આલેખ હોય છે, દરેકમાં મોટાભાગની ધાર હોય છે. આ આપણે જે પરિણામ બતાવવા માંગીએ છીએ તેટલું મજબૂત નથી, તેથી આપણે પુનરાવર્તિત રીતે કન્ટેનર લેમ્માને લાગુ કરીશું. ધારો કે આપણી પાસે ઓછામાં ઓછા ત્રિકોણવાળું કોઈ પાત્ર છે. આપણે કન્ટેનર લેમ્માને પ્રેરિત સબ-હાયપરગ્રાફ પર લાગુ કરી શકીએ છીએ. ની સરેરાશ ડિગ્રી ઓછામાં ઓછી છે, કારણ કે દરેક ત્રિકોણમાં એક ધાર હોય છે, અને આ પ્રેરિત સબગ્રાફ મોટાભાગના શિરોબિંદુઓ ધરાવે છે. આમ, આપણે પરિમાણ સાથે લેમ્માને લાગુ કરી શકીએ છીએ, આપણા કન્ટેનરના સમૂહમાંથી દૂર કરી શકીએ છીએ, તેને કન્ટેનરના આ સમૂહ દ્વારા બદલી શકીએ છીએ, કન્ટેનર આવરી લે છે. જ્યાં સુધી આપણી પાસે કન્ટેનરનો અંતિમ સંગ્રહ ન હોય ત્યાં સુધી આપણે પુનરાવર્તન કરી શકીએ છીએ જેમાં દરેક ત્રિકોણ કરતા ઓછા હોય છે. અમે અવલોકન કર્યું છે કે આ સંગ્રહ ખૂબ મોટો ન હોઈ શકે; અમારા તમામ પ્રેરિત સબગ્રાફ્સમાં ઓછામાં ઓછા મોટા ભાગના શિરોબિંદુઓ અને સરેરાશ ડિગ્રી હોય છે, જેનો અર્થ છે કે દરેક પુનરાવર્તન મોટાભાગના નવા કન્ટેનરમાં પરિણમે છે. વધુમાં, કન્ટેનરનું કદ દરેક સમયના પરિબળ દ્વારા સંકોચાય છે, તેથી પુનરાવર્તનોની મર્યાદિત (તેના આધારે) સંખ્યા પછી, પુનરાવર્તિત પ્રક્રિયા સમાપ્ત થઈ જશે. સ્વતંત્ર સમૂહ (આલેખ સિદ્ધાંત) સ્ઝેમેરેડીનો પ્રમેય સ્ઝેમેરેડી નિયમિતતા લેમ્મા સંદર્ભો એક્સ્ટ્રીમ ગ્રાફ સિદ્ધાંત હાયપરગ્રાફ્સ એડિટિવ કોમ્બિનેટોરિક્સ પણ જુઓ.