Erdős–Szemerédi theorem
எண்கணித ஒருங்கிணைப்பில், எர்டாஸ்-ஸ்ஸெமெரெடி தேற்றம் ஒவ்வொரு வரையறுக்கப்பட்ட முழு எண்களின் தொகுப்புக்கும், குறைந்தபட்சம் ஒன்று, ஜோடி வாரியான தொகைகளின் தொகுப்பு அல்லது ஜோடி வாரியான தயாரிப்புகளின் தொகுப்பு கணிசமாக பெரிய தொகுப்பை உருவாக்குகிறது என்று கூறுகிறது. இன்னும் துல்லியமாக, எர்டாஸ்-ஸ்ஸெமெரெடி தேற்றம் எந்தவொரு காலியாக இல்லாத தொகுப்புக்கும் நேர்மறை மாறிலிகள் c மற்றும் உள்ளன என்று கூறுகிறது. இது 1983 இல் பால் எர்டாஸ் மற்றும் எண்ட்ரே ஸ்ஸெமெரெடி ஆகியோரால் நிரூபிக்கப்பட்டது. குறியீடு தொகுப்பின் கார்டினாலிட்டியைக் குறிக்கிறது. ஜோடி வாரியான தொகைகளின் தொகுப்பு மற்றும் அதன் கூட்டுத்தொகை என்று அழைக்கப்படுகிறது. ஜோடி வாரியான தயாரிப்புகளின் தொகுப்பு மற்றும் அதன் தயாரிப்பு தொகுப்பு என்று அழைக்கப்படுகிறது. இந்த தேற்றம் சேர்க்கை அமைப்பு மற்றும் பெருக்கல் அமைப்பு இணைந்து இருக்க முடியாது என்ற கோட்பாட்டின் ஒரு பதிப்பாகும். உண்மையான கோடு ஒரு வரையறுக்கப்பட்ட சபரிங் அல்லது வரையறுக்கப்பட்ட சப்ஃபீல்டை ஒத்த எந்த தொகுப்பையும் கொண்டிருக்கவில்லை என்பதற்கான ஒரு கூற்றாகவும் இதைக் காணலாம்; இது இப்போது கூட்டுத்தொகை நிகழ்வு என்று அழைக்கப்படுவதற்கான முதல் எடுத்துக்காட்டு, இது இப்போது வரையறுக்கப்பட்ட புலங்கள் உட்பட பல்வேறு வகையான வளையங்கள் மற்றும் புலங்களில் வைத்திருப்பதாக அறியப்படுகிறது. கூட்டுத்தொகை-தயாரிப்பு அனுமானம் எந்தவொரு தொகுப்பின் கூட்டுத்தொகை அல்லது தயாரிப்பு தொகுப்புகளில் ஒன்று முடிந்தவரை பெரியதாக இருக்க வேண்டும் என்று கூட்டுத்தொகை-தயாரிப்பு அனுமானம் முறைசாரா முறையில் கூறுகிறது. இது முதலில் எர்டாஸ் மற்றும் ஸ்ஸெமெரெடி ஆகியோரால் முழு எண்கள் மீது ஊகிக்கப்பட்டது, ஆனால் உண்மையான எண்களை வைத்திருப்பதாக கருதப்படுகிறது. அனுமானம்ஃ எந்தவொரு தொகுப்புக்கும் ஒன்று உள்ளது ஓ (1) குறியீட்டில் உள்ள அறிகுறியற்ற அளவுரு |A | ஆகும். எடுத்துக்காட்டுகள் என்றால், அறிகுறியற்ற குறியீட்டைப் பயன்படுத்தினால், அறிகுறியற்ற அளவுருவுடன். முறைசாரா முறையில், இது கூட்டுத்தொகை வளராது என்று கூறுகிறது. மறுபுறம், தயாரிப்பு தொகுப்பு அனைவருக்கும் வடிவத்தின் வரம்பை திருப்திப்படுத்துகிறது. இது எர்டாஸ் பெருக்கல் அட்டவணை சிக்கலுடன் தொடர்புடையது. இந்த செட்டுக்கு சிறந்த கீழ் எல்லை கெவின் ஃபோர்டு காரணமாகும். இந்த உதாரணம் ஜியோர்ஜி எலிக்ஸ் மற்றும் இம்ரே இசட். ருசா ஆகியோரின் மொத்த தயாரிப்பு சிக்கலின் ஃபூ சம்ஸ், மெனி ப்ராடக்ட்ஸ் பதிப்பின் ஒரு எடுத்துக்காட்டு. அவற்றின் முடிவின் விளைவாக, சிறிய சேர்க்கை இரட்டிப்பாகும் எந்த தொகுப்பும், எடுத்துக்காட்டாக ஒரு எண்கணித முன்னேற்றம் தயாரிப்பு தொகுப்பில் குறைந்த வரம்பைக் கொண்டுள்ளது. முழு எண்களில் ஒரு எண்கணித முன்னேற்றத்தின் எந்த அடர்த்தியான துணைக்குழுவிற்கும், இது அடுக்கில் உள்ள காரணி வரை கூர்மையாக உள்ளது என்பதை சூ மற்றும் ஜோ நிரூபித்தனர். மாறாக, தொகுப்பு திருப்தி அளிக்கிறது, ஆனால் பல தொகைகளைக் கொண்டுள்ளதுஃ இந்த வரம்பு ஒரு எண்ணின் பைனரி பிரதிநிதித்துவத்தை கருத்தில் கொள்வதிலிருந்து வருகிறது. இந்த தொகுப்பு ஒரு வடிவியல் முன்னேற்றத்திற்கு ஒரு எடுத்துக்காட்டு. எண்களின் சீரற்ற தொகுப்பைப் பொறுத்தவரை, தயாரிப்பு தொகுப்பு மற்றும் கூட்டுத்தொகை தொகுப்பு இரண்டும் கார்டினாலிட்டியைக் கொண்டுள்ளன; அதாவது, அதிக நிகழ்தகவுடன் கூட்டுத்தொகை தொகுப்பு மீண்டும் மீண்டும் கூறுகளை உருவாக்காது, மேலும் தயாரிப்பு தொகுப்புக்கு ஒரே மாதிரியாக இருக்கும். Erdós மற்றும் Szemerédi என்ற அனுமானத்தின் கூர்மை, பிணைப்புடன் போதுமான மென்மையான முழு எண்களின் தொகுப்புக்கு ஒரு எடுத்துக்காட்டுஃ அனுமானத்தில் உள்ள ஓ (1) சொல் அவசியம் என்பதை இது காட்டுகிறது. சில தொகைகள், பல தயாரிப்புகள் (எஃப். எஸ். எம். பி): என்றால், சில தயாரிப்புகள், பல தொகைகள் (எஃப். பி. எம். எஸ்): என்றால், பின்னர். வரலாறு மற்றும் தற்போதைய முடிவுகள் பின்வரும் அட்டவணை யதார்த்தங்களை விட மொத்த தயாரிப்பு சிக்கலின் முன்னேற்றத்தை சுருக்கமாகக் கூறுகிறது. கியோர்கி எலிக்ஸின் 1/4 மற்றும் ஜோசெஃப் சோலிமோசியின் 1/3 ஆகியவை மேற்கோள் இலக்கியத்திற்குள் மைல்கல் முடிவுகளாகக் கருதப்படுகின்றன. 2009 க்குப் பிறகு அனைத்து முன்னேற்றங்களும் வடிவத்தில் உள்ளன, மேலும் கொன்யாகின் மற்றும் ஷ்க்ரெடோவின் வாதங்களின் சுத்திகரிப்புகளைக் குறிக்கின்றன. Szemerédi-Trotter தேற்றத்தை மட்டுமே உள்ளடக்கிய சிக்கலான எண்கள் சான்று நுட்பங்கள் சிக்கலான எண்களுக்கு தானாகவே விரிவடைகின்றன, ஏனெனில் Szemerédi-Trotter தேற்றம் Tóth இன் தேற்றத்தால் உள்ளது. கொன்யாஜினும் ருட்னேவும் சிக்கலான எண்களுக்கு மேல் 3/4 என்ற அடுக்குடன் பொருந்தினர். வடிவத்தின் அடுக்குகளுடன் கூடிய முடிவுகள் சிக்கலான எண்களுக்கு மேல் பொருந்தவில்லை. வரையறுக்கப்பட்ட புலங்களில் கூட்டுப் பொருள் சிக்கல் குறிப்பாக வரையறுக்கப்பட்ட புலங்களில் நன்கு ஆய்வு செய்யப்படுகிறது. காக்கேயா அனுமானம் என்ற வரையறுக்கப்பட்ட புலத்தால் தூண்டப்பட்ட வோல்ஃப், ஒவ்வொரு துணைக்குழுவிற்கும், ஒரு (பெரிய) பகா எண் இருக்கும்போது, அது ஒரு முழுமையான மாறிலி என்று ஊகித்தார். இந்த அனுமானம் 1990 களில் விக்டெர்சனால் சீரற்ற பிரித்தெடுத்தல்களால் உந்தப்பட்டது. பின்வரும் உதாரணத்தின் காரணமாக கூட்டுப் பொருள் சிக்கல் வரையறுக்கப்பட்ட புலங்களில் நிபந்தனையின்றி இருக்க முடியாது என்பதை நினைவில் கொள்கஃ எடுத்துக்காட்டுஃ ஒரு வரையறுக்கப்பட்ட புலமாக இருங்கள் மற்றும் எடுத்துக் கொள்வோம். பின்னர் கூட்டல் மற்றும் பெருக்கத்தின் கீழ் மூடப்பட்டுள்ளது, மற்றும் எனவே. இந்த நோயியல் உதாரணம் கேள்விக்குரிய புலத்தின் எந்த துணை புலமாகவும் எடுத்துக்கொள்வதற்கு விரிவடைகிறது. தர ரீதியாக, கூட்டுப் பொருள் சிக்கல் வரையறுக்கப்பட்ட புலங்களில் தீர்க்கப்பட்டுள்ளதுஃ தேற்றம் (போர்கேன், காட்ஸ், தாவோ (2004)): முதன்மையானதாக இருக்கட்டும் மற்றும் சிலவற்றுடன் இருக்கட்டும். பின்னர் சிலருக்கு ஒன்று உள்ளது. போர்கெய்ன், காட்ஸ் மற்றும் தாவோ ஆகியோர் இந்த தேற்றத்தை தன்னிச்சையான புலங்களுக்கு விரிவுபடுத்தினர். முறைசாரா முறையில், பின்வரும் தேற்றம், ஒரு போதுமான பெரிய தொகுப்பு கூட்டல் அல்லது பெருக்கத்தின் கீழ் வளரவில்லை என்றால், அது பெரும்பாலும் ஒரு துணை புலத்தின் விரிவாக உள்ளது என்று கூறுகிறது. தேற்றம் (போர்கேன், காட்ஸ், தாவோ (2004)): ஒரு வரையறுக்கப்பட்ட புலத்தின் துணைக்குழுவாக இருக்கட்டும், இதனால் சிலருக்கு அது இருக்கும் என்று வைத்துக்கொள்வோம். பின்னர் ஒரு துணை புலம் உள்ளது, மற்றும் ஒரு தொகுப்பு உள்ளது. மாறிலி சுயாதீனமாக இருக்கலாம் என்று அவர்கள் பரிந்துரைக்கின்றனர். வரையறுக்கப்பட்ட புலம் தொகை-தயாரிப்பு சிக்கலுக்கான அளவு முடிவுகள் பொதுவாக இரண்டு பிரிவுகளாகப் பிரிக்கப்படுகின்றனஃ சிறப்பியல்புகளைப் பொறுத்தவரை சிறியது மற்றும் சிறப்பியல்புகளைப் பொறுத்தவரை பெரியது. ஏனென்றால், ஒவ்வொரு அமைப்பிலும் வெவ்வேறு வகையான நுட்பங்கள் பயன்படுத்தப்படுகின்றன. சிறிய தொகுப்புகள் இந்த ஆட்சியில், சிறப்பியல்புகளின் ஒரு களமாக இருக்கட்டும். புலம் எப்போதும் வரையறுக்கப்படவில்லை என்பதை நினைவில் கொள்க. அப்படியானால், அதன் பண்பு பூஜ்ஜியமாக இருக்கும்போது,-கட்டுப்பாடு தவிர்க்கப்படுகிறது. முதன்மை அல்லாத வரிசை கொண்ட புலங்களில்,-கட்டுப்பாடு எந்த துணை புலத்துடனும் மிகப் பெரிய குறுக்குவெட்டைக் கொண்டிருக்கவில்லை என்ற அனுமானத்துடன் மாற்றப்படலாம். இந்த திசையில் சிறந்த வேலை லி மற்றும் ரோச்-நியூட்டன் மேற்கண்ட அட்டவணையின் குறியீட்டில் ஒரு அடுக்கை அடைவதால் ஆகும். பெரிய தொகுப்புகள் பகா எண்ணைப் பொறுத்தவரை, கரேவின் பின்வரும் விளைவாக மொத்த தயாரிப்பு சிக்கல் தீர்க்கப்பட்டதாகக் கருதப்படுகிறதுஃ தேற்றம் (கரேவ் (2007)): வாருங்கள். பிறகு. இது வரம்பில் உகந்ததாகும். இந்த முடிவு 2011 ஆம் ஆண்டில் வின் என்பவரால் முதன்மை அல்லாத வரிசையின் வரையறுக்கப்பட்ட புலங்களுக்கு நீட்டிக்கப்பட்டது. மாறுபாடுகள் மற்றும் பொதுமைப்படுத்தல்கள் போர்கெய்ன் மற்றும் சாங் இயக்கிகளின் பிற சேர்க்கைகள் செட்களுக்கு நிபந்தனையற்ற வளர்ச்சியை நிரூபித்தன, ஒருவர் போதுமான தொகைகள் அல்லது தயாரிப்புகளைக் கருத்தில் கொள்ளும் வரைஃ தேற்றம் (போர்கெய்ன், சாங் (2003): லெட். பின்னர் உள்ளது, எனவே அனைவருக்கும், ஒன்று உள்ளது. பல படைப்புகளில், கூட்டல் மற்றும் பெருக்கம் ஆகியவை ஒரே வெளிப்பாடாக இணைக்கப்படுகின்றன. கூட்டல் மற்றும் பெருக்கம் என்ற குறிக்கோள் இணைந்து இருக்க முடியாது என்பதால், ஒரு தொகுப்பின் கூட்டல் மற்றும் பெருக்கத்தின் எந்தவொரு அற்பமான கலவையும் வளர்ச்சிக்கு உத்தரவாதம் அளிக்க வேண்டும் என்று ஒருவர் எதிர்பார்க்கிறார். வரையறுக்கப்பட்ட அமைப்புகளில், அல்லது அற்பமான துணை புலங்களைக் கொண்ட புலங்களில், அத்தகைய அறிக்கைக்கு மேலும் கட்டுப்பாடுகள் தேவை என்பதை நினைவில் கொள்க. ஆர்வமுள்ள தொகுப்புகளில் அடங்கும் (முடிவுகள்):-ஸ்டீவன்ஸ் மற்றும் வாரன் அதை காட்டுகிறார்கள்-மர்பி, ரோச்-நியூட்டன் மற்றும் ஷ்க்ரெடோவ் அதைக் காட்டுகிறார்கள்-ஸ்டீவன்ஸ் மற்றும் வாரன் அதைக் காட்டுகிறார்கள்-ஸ்டீவன்ஸ் மற்றும் ருட்னேவ் அதைக் காட்டுகிறார்கள் கூட்டுத்தொகை இல்லாத தொகுப்பு குறிப்புகள் வெளிப்புற இணைப்புகளைப் பார்க்கவும் எண் கோட்பாட்டில் தனித்துவமான கணித கோட்பாடுகளில் கோட்பாடுகளை ஒருங்கிணைக்கிறது