Blow-up lemma
1997 ஆம் ஆண்டில் ஜானோஸ் கொம்லோஸ், கபோர் என். சார்கோசி மற்றும் எண்ட்ரே ஸ்ஸெமெரெடி ஆகியோரால் நிரூபிக்கப்பட்ட ப்ளோ-அப் லெம்மா, தீவிர வரைபடக் கோட்பாட்டில் ஒரு முக்கியமான விளைவாகும், குறிப்பாக வழக்கமான முறையின் சூழலில். Szemerédi இன் வழக்கமான லெம்மாவின் அறிக்கையில் உள்ள வழக்கமான ஜோடிகள் வரம்புக்குட்பட்ட அளவிலான விரிவான வரைபடங்களை உட்பொதிக்கும் சூழலில் முழுமையான இருதரப்பு வரைபடங்களைப் போல செயல்படுகின்றன என்று அது கூறுகிறது. வரையறைகள் மற்றும் அறிக்கை ப்ளோ-அப் லெம்மாவை முறையாகக் குறிப்பிட, நாம் முதலில் ஒரு சூப்பர்-ரெகுலர் ஜோடி என்ற கருத்தை வரையறுக்க வேண்டும். சூப்பர்-ரெகுலர் ஜோடிகள் உச்சியின் தொகுப்பின் ஒரு ஜோடி துணைக்குழுக்கள்-சூப்பர்-ரெகுலர் என்று அழைக்கப்படுகின்றன, ஒவ்வொன்றிற்கும் திருப்திகரமாக இருந்தால், மேலும் நம்மிடம் உள்ளது, மேலும், அனைவருக்கும் மற்றும் அனைவருக்கும். இங்கே ஒரு விளிம்புடன் மற்றும் அத்தகைய ஜோடிகளின் எண்ணிக்கையைக் குறிக்கிறது. ப்ளோ-அப் லெம்மாவின் அறிக்கை வரிசை மற்றும் நேர்மறை அளவுருக்களின் வரைபடத்தைப் பொறுத்தவரை, பின்வருவனவற்றைக் கொண்ட ஒரு நேர்மறை உள்ளது. தன்னிச்சையான நேர்மறை முழு எண்களாக இருக்கட்டும், அதன் செங்குத்துகளை ஜோடி வாரியாக வேறுபட்ட அளவுகளின் தொகுப்புகளுடன் மாற்றுவோம் (ஊதுதல்). ஒரே உச்சியில் இரண்டு வரைபடங்களை உருவாக்குகிறோம். முதல் வரைபடம் ஒவ்வொரு விளிம்பையும் அதனுடன் தொடர்புடைய உச்சி செட்களுக்கு இடையில் முழுமையான இருதரப்பு வரைபடத்துடன் மாற்றுவதன் மூலம் பெறப்படுகிறது. ஒவ்வொரு விளிம்பையும் மற்றும் இடையே ஒரு-சூப்பர்-வழக்கமான ஜோடியுடன் மாற்றுவதன் மூலம் ஒரு ஸ்பார்ஸர் கிராஃப் ஜி கட்டமைக்கப்படுகிறது. ஒரு வரைபடம் உட்பொதிக்கப்பட்டிருந்தால், அது ஏற்கனவே ஜி. ப்ரூஃப் ஸ்கெட்சில் உட்பொதிக்கப்படலாம் ப்ளோ-அப் லெம்மாவின் ஆதாரம் ஒரு சீரற்ற பேராசை வழிமுறையைப் (ஆர்ஜிஏ) பயன்படுத்தி அதன் செங்குத்துகளை தொடர்ச்சியாக உட்பொதிப்பதை அடிப்படையாகக் கொண்டது. வாதம் பின்னர் வழிமுறை தோல்வியின் விகிதத்தை கட்டுப்படுத்துவதன் மூலம் தொடர்கிறது, இது பொருத்தமான அளவுருக்களைத் தேர்ந்தெடுப்பதற்கு 1 க்கும் குறைவாக (உண்மையில்) உள்ளது. இதன் பொருள் வழிமுறை வெற்றிபெற பூஜ்ஜியமற்ற வாய்ப்பு உள்ளது, எனவே ஒரு உட்பொதிப்பு இருக்க வேண்டும். இந்த முறையில் அனைத்து செங்குத்துகளையும் நேரடியாக உட்பொதிக்க முயற்சிப்பது வேலை செய்யாது, ஏனெனில் ஒரு சிறிய எண்ணிக்கையிலான செங்குத்துகள் மட்டுமே இருக்கும்போது வழிமுறை சிக்கிக்கொள்ளக்கூடும். அதற்கு பதிலாக, இடையக செங்குத்துகள் என்று அழைக்கப்படும் உச்சியின் தொகுப்பின் ஒரு சிறிய பகுதியை ஒதுக்கி வைத்து, மீதமுள்ள செங்குத்துகளை உட்பொதிக்க முயற்சிக்கிறோம். இடையக செங்குத்துகள் பின்னர் ஹாலின் திருமண தேற்றத்தைப் பயன்படுத்தி இடையக செங்குத்துகளுக்கும் மீதமுள்ள செங்குத்துகளுக்கும் இடையில் ஒரு சரியான பொருத்தத்தைக் கண்டறிய உட்பொதிக்கப்பட்டுள்ளன. முந்தைய பிரிவுகளில் அறிமுகப்படுத்தப்பட்ட அனைத்து குறியீடுகளையும் நாம் கடன் வாங்குகிறோம். விடுங்கள். இதில் உட்பொதிக்க முடியும் என்பதால், நாம் அனைவருக்காகவும் எழுதலாம். ஒரு உச்சிக்கு, குறிக்கலாம். ஏனெனில், தொடர்புடைய உச்சி செட்களுக்கு இடையிலான விளிம்புகளின் அடர்த்தியைக் குறிக்கிறது. நாம் கட்டமைக்க விரும்பும் உட்பொதிப்பாகும். இது அல்காரிதம் முடிவடையும் இறுதி நேரமாகும். அல்காரிதம் கட்டம் 0 இன் அவுட்லைன்ஃ துவக்கம் பேராசையுடன் உச்சிகளிலிருந்து இடையக செங்குத்துகளின் தொகுப்பை குறைந்தபட்சம் ஒருவருக்கொருவர் அதிகபட்ச செங்குத்துகள் தூரமாக தேர்வு செய்யுங்கள், ஒரு பட்டியலில் மீதமுள்ள செங்குத்துகளை (உள்ளவை) வரிசைப்படுத்தி, முதல் அண்டை நாடுகளை வைக்கவும். தற்போது முன்னுரிமை அளிக்கப்பட்ட செங்குத்துகளின் வரிசையை அறிவிக்கவும், இது ஆரம்பத்தில் காலியாக உள்ளது. அனைத்து "இலவச புள்ளிகளின்" தொகுப்பைக் குறிக்கும் செங்குத்துகளால் குறியிடப்பட்ட தொகுப்புகளின் வரிசையை அறிவிக்கவும், அதாவது, முனையில் ஆக்கிரமிக்கப்படாத செங்குத்துகளின் தொகுப்பை ஏற்கனவே உட்பொதிக்கப்பட்ட அண்டை நாடுகளிலிருந்து எந்தவொரு அருகாமை நிபந்தனைகளையும் மீறாமல் வரைபடமாக்க முடியும். துவக்கப்பட்டுள்ளது. கட்டம் 1: சீரற்ற பேராசை உட்பொதிப்பு மீதமுள்ள செங்குத்துகளின் தொகுப்பிலிருந்து பின்வருமாறு ஒரு உச்சியைத் தேர்ந்தெடுக்கவும்ஃ முன்னுரிமை அளிக்கப்பட்ட செங்குத்துகளின் வரிசை காலியாக இல்லாவிட்டால், அதில் இருந்து உச்சியைத் தேர்ந்தெடுக்கவும் இல்லையெனில், மீதமுள்ள செங்குத்துகளின் பட்டியலிலிருந்து ஒரு உச்சியைத் தேர்ந்தெடுக்கவும். இலவச செட்டுகளைப் புதுப்பித்து, முன்னுரிமை செங்குத்துகளின் தொகுப்பில் கடைசி புதுப்பிப்பில் அவற்றின் அளவைப் பொறுத்தவரை இலவச செட்டுகள் மிகவும் சிறியதாகிவிட்டன, வரிசையில் ஏதேனும் செட்களில் போதுமான அளவு பெரிய பகுதியைக் கொண்டிருந்தால் நிறுத்தவும் பஃபர் அல்லாத செங்குத்துகள் ஏதேனும் ஒன்றில் உட்பொதிக்கப்பட வேண்டும் அல்லது, நேரத்தைப் புதுப்பித்து படி 1 க்குச் செல்ல வேண்டும் என்றால்; இல்லையெனில் கட்டம் 2 க்குச் செல்லுங்கள். கட்டம் 2: மீதமுள்ள செங்குத்துகளுக்கான கோனிக்-ஹால் பொருத்தம் உட்பொதிக்கப்பட வேண்டிய செங்குத்துகளின் தொகுப்பைக் கவனியுங்கள், இது துல்லியமானது மற்றும் இலவச புள்ளிகளின் தொகுப்பு. இந்த இரண்டு தொகுப்புகளுக்கும் இடையில் ஒரு இருதரப்பு வரைபடத்தை உருவாக்கி, ஒவ்வொன்றையும் இணைத்து, இந்த இருதரப்பு வரைபடத்தில் ஒரு சரியான பொருத்தத்தைக் கண்டறியவும். இந்த பொருத்தத்திற்கு ஏற்ப உட்பொதிக்கப்பட்டது. துல்லியத்தின் சான்று துல்லியத்தின் சான்று தொழில்நுட்பமானது மற்றும் மிகவும் ஈடுபாடு கொண்டது, எனவே விவரங்களைத் தவிர்க்கிறோம். முக்கிய வாதம் பின்வருமாறு தொடர்கிறதுஃ படி 1: பெரும்பாலான செங்குத்துகள் நல்லவை, போதுமான செங்குத்துகள் இலவசமாக உள்ளன, ஒரே நேரத்தில் தூண்டுவதன் மூலம் நிரூபிக்கவும், அந்த நேரத்தில் உட்பொதிக்கப்பட்ட உச்சியில் இருந்தால், தேர்வுகளில் ஒரு சிறிய பகுதி மட்டுமே மோசமாக இருக்கும், அனைத்து இலவச செட்களும் உட்பொதிக்கப்படாத செங்குத்துகளுக்கு மிகவும் பெரியவை படி 2: "முக்கிய லெம்மா" கருத்தில் கொள்ளுங்கள், அது மிகவும் சிறியதல்ல. முதல் கட்டத்தில் எந்த செங்குத்துகளும் உட்பொதிக்கப்படாத நிகழ்வைக் கவனியுங்கள், அந்த நேரத்தில் உள்ள இலவச செங்குத்துகளின் பின்னம் சிறியதாக இருக்கும் ஒரு நேரம் உள்ளது. பின்னர், நடப்பதற்கான நிகழ்தகவு குறைவாக உள்ளது என்பதை நாங்கள் நிரூபிக்கிறோம். படி 3: கட்டம் 1 அதிக நிகழ்தகவுடன் வெற்றி பெறுகிறது முதல் கட்டம் தோல்வியடையும் ஒரே வழி அது நிறுத்தப்பட்டால் மட்டுமே, ஏனெனில் முதல் படியின் மூலம் எப்போதும் நல்ல செங்குத்துகளின் போதுமான தேர்வு இருப்பதை நாம் அறிவோம். வரிசை மிக நீளமாக இருக்கும்போது மட்டுமே நிரல் நிறுத்தப்படுகிறது. வாதம் பின்னர் தோல்வியின் அனைத்து முறைகளிலும் ஒன்றிணைப்பதன் மூலம் தொடர்கிறது, எந்தவொரு குறிப்பிட்ட தேர்வுக்கும், தோல்வியுற்ற வரிசையின் துணைக்குழுவைக் குறிக்கும் வகையில், மூன்று "முக்கிய லெம்மாவின்" நிபந்தனைகளை பூர்த்தி செய்கிறது, இதனால் ஏற்படுவதற்கான குறைந்த நிகழ்தகவு உள்ளது. படி 4: ஆரம்ப கட்டத்தில் வரிசை இல்லை இடையகத்தில் உள்ள செங்குத்துகளின் அண்டை நாடுகள் முதலில் உட்பொதிக்கப்படும் வகையில் பட்டியல் அமைக்கப்பட்டது என்பதை நினைவில் கொள்க. இந்த செங்குத்துகள் அனைத்தும் உட்பொதிக்கப்படும் வரை இருக்கும் நேரம் ஆரம்ப கட்டம் என்று அழைக்கப்படுகிறது. ஆரம்ப கட்டத்தில் வரிசையில் எந்த செங்குத்துகளும் சேர்க்கப்படுவதில்லை என்பதை தூண்டல் மூலம் நிரூபிக்கவும். இதைத் தொடர்ந்து இடையக செங்குத்துகளின் அண்டை நாடுகள் அனைத்தும் மீதமுள்ள செங்குத்துகளுக்கு முன் சேர்க்கப்படுகின்றன. படி 5: இடையக செங்குத்துகள் போதுமான இலவச புள்ளிகளைக் கொண்டுள்ளன மற்றும், எந்தவொரு செங்குத்துகளும் உட்பொதிக்கப்படுவதற்கு முன்பு சுதந்திரமாக இருந்த அனுமானத்தின் நிபந்தனையின் அடிப்படையில், நிகழ்தகவின் மீது போதுமான பெரிய கீழ் வரம்பைக் காணலாம். படி 6: கட்டம் 2 அதிக நிகழ்தகவுடன் வெற்றி பெறுகிறது ஹாலின் திருமணக் கோட்பாட்டின் படி, ஹாலின் நிலை மீறப்பட்டால் மட்டுமே கட்டம் 2 தோல்வியடைகிறது. இது நடக்க, அது போன்ற சில இருக்க வேண்டும். இலவச செட்டுகளின் பெரிய தன்மையால் மிகவும் சிறியதாக இருக்க முடியாது (படி 1). மிகவும் பெரியதாக இருந்தால், அதிக நிகழ்தகவுடன், அத்தகைய வழக்கில் தோல்விக்கான நிகழ்தகவு குறைவாக இருக்கும். மிகவும் சிறியதாகவோ அல்லது மிகப் பெரியதாகவோ இல்லாவிட்டால், அது பயன்படுத்தப்படாத செங்குத்துகளின் பெரிய தொகுப்பு என்பதைக் குறிப்பிட்டு, முக்கிய லெம்மாவைப் பயன்படுத்தலாம் மற்றும் தோல்வியின் நிகழ்தகவை ஒன்றிணைக்கலாம். பயன்பாடுகள் அடர்த்தியான வரைபடங்களை உட்பொதிப்பதில் ப்ளோ-அப் லெம்மா பல பயன்பாடுகளைக் கொண்டுள்ளது. போசா-சீமோர் அனுமானம் 1962 ஆம் ஆண்டில், லாஜோஸ் போசா குறைந்தபட்ச டிகிரியைக் கொண்ட ஒவ்வொரு வெர்டெக்ஸ் வரைபடமும் குறைந்தபட்சம் ஹாமில்டோனியன் சுழற்சியின் சதுரத்தைக் கொண்டுள்ளது என்று ஊகித்தார், இது டிராக்கின் தேற்றத்தை பொதுமைப்படுத்துகிறது. 1974 ஆம் ஆண்டில் பால் சீமோர் இந்த அனுமானத்தை மேலும் விரிவுபடுத்தினார்ஃ குறைந்தபட்ச டிகிரி கொண்ட செங்குத்துகளில் உள்ள ஒவ்வொரு வரைபடமும் ஹாமில்டோனியன் சுழற்சியின்-வது சக்தியைக் கொண்டுள்ளது. 1998 ஆம் ஆண்டில் (ஒரு நிலையான) அனைத்து போதுமான பெரிய மதிப்புகளுக்கும் அனுமானத்தை நிரூபிக்க கொம்லோஸ், சர்கோஸி மற்றும் ஸ்ஸெமெரெடி ஆகியோரால் ப்ளோ-அப் லெம்மா பயன்படுத்தப்பட்டது. 1995 ஆம் ஆண்டில், நோகா அலோன் மற்றும் ரபேல் யூஸ்டர் ஆகியோர் நன்கு அறியப்பட்ட ஹஜ்னல்-ஸ்ஸெமெரெடி தேற்றத்தின் பொதுமைப்படுத்தலை தன்னிச்சையான-காரணிகளாக (முழுமையான வரைபடங்களுக்கு பதிலாக) கருதி, பின்வரும் அறிக்கையை நிரூபித்தனர்ஃ செங்குத்துகளுடன் கூடிய ஒவ்வொரு நிலையான வரைபடத்திற்கும், n செங்குத்துகளுடன் கூடிய மற்றும் குறைந்தபட்ச டிகிரியுடன் கூடிய எந்த வரைபடமும் G இல் H இன் செங்குத்துப் பிரதிகள் உள்ளன. இந்த அனுமானம் 2001 ஆம் ஆண்டில் கொம்லோஸ், சர்கோஸி மற்றும் ஸ்ஸெமெரெடி ஆகியோரால் ப்ளோ-அப் லெம்மாவைப் பயன்படுத்தி நிரூபிக்கப்பட்டது. வரலாறு மற்றும் மாறுபாடுகள் 1997 ஆம் ஆண்டில் கொம்லோஸ், சர்கோஸி மற்றும் ஸ்ஸெமெரெடி ஆகியோரால் முதன்முதலில் வெளியிடப்பட்ட ப்ளோ-அப் லெம்மா, பரவலான வரைபடங்களை உட்பொதிக்க வழக்கமான முறையைப் பயன்படுத்தி தற்போதுள்ள ஆதார நுட்பங்களின் சுத்திகரிப்பாக வெளிப்பட்டது, மரங்களை பரப்புவது குறித்த பொல்லோபாஸ் அனுமானத்தின் சான்றில், ஹாமில்டோனியன் சுழற்சியின் கே-வது வரைபட சக்தியைக் கொண்டிருக்கத் தேவையான குறைந்தபட்ச டிகிரி பற்றிய போசா-சீமோர் அனுமானத்தில் வேலை செய்யுங்கள், மற்றும் ஒரு வரைபடத்திற்குத் தேவையான குறைந்தபட்ச டிகிரியில் அலோன்-யூஸ்டர் அனுமானத்தின் ஆதாரம் ஒரு சரியான எச்-காரணி. இந்த கோட்பாடுகள் அனைத்தின் சான்றுகளும் பெரும்பாலான செங்குத்துகளை உட்பொதிக்க ஒரு சீரற்ற பேராசை வழிமுறையைப் பயன்படுத்துவதை நம்பியிருந்தன, பின்னர் மீதமுள்ள செங்குத்துகளுக்கு உட்பொதிப்பைக் கண்டறிய ஒரு கோனிக்-ஹால் போன்ற வாதத்தைப் பயன்படுத்துகின்றன. ப்ளோ-அப் லெம்மாவின் முதல் ஆதாரமும் இதேபோன்ற வாதத்தைப் பயன்படுத்தியது. இருப்பினும், பின்னர் 1997 ஆம் ஆண்டில், அதே ஆசிரியர்கள் மற்றொரு கட்டுரையை வெளியிட்டனர், இது சீரற்ற வழிமுறையை தீர்மானிக்க ஒரு முன்னேற்றத்தைக் கண்டறிந்தது. பீட்டர் கீவாஷ் 2010 ஆம் ஆண்டில் ஹைபர் கிராப்களுக்கு ப்ளோ-அப் லெம்மாவின் பொதுமைப்படுத்தலைக் கண்டறிந்தார். ஸ்டீபன் க்ளோக் மற்றும் ஃபெலிக்ஸ் ஜூஸ் ஆகியோர் 2018 ஆம் ஆண்டில் வானவில் வரைபடங்களுக்கான ப்ளோ-அப் லெம்மாவின் மாறுபாட்டைக் கண்டுபிடித்தனர். 2019 ஆம் ஆண்டில், பீட்டர் ஆலன், ஜூலியா பாட்சர், ஹைப் ஹான், யோஷிஹாரு கோஹயாகாவா மற்றும் யூரி பெர்சன் ஆகியோர், வரைகலை கோட்பாட்டில் வரம்புக்குட்பட்ட டிகிரி வரைபடங்களை சீரற்ற மற்றும் போலி வரைபடங்களில் உட்பொதிப்பதற்காக ப்ளோ-அப் லெம்மாவின் அரிதான ஒப்புமைகளைக் கண்டறிந்தனர்.