Erdős–Szekeres theorem
கணிதத்தில், எர்டாஸ்-செக்கரெஸ் தேற்றம், r, s கொடுக்கப்பட்டால், குறைந்தபட்சம் (r−1) (s−1) + 1 நீளமுள்ள தனித்துவமான உண்மையான எண்களின் எந்தவொரு வரிசையும் r நீளத்தின் சலிப்பான முறையில் அதிகரிக்கும் தொடர்ச்சியைக் கொண்டுள்ளது அல்லது நீளத்தின் சலிப்பான முறையில் குறைந்து வரும் தொடர்ச்சியைக் கொண்டுள்ளது என்று வலியுறுத்துகிறது. இது ஒரு இறுதியான முடிவாகும், இது ராம்சேயின் தேற்றத்தின் துல்லியமான இணைப்புகளில் ஒன்றாகும். தனித்துவமான உண்மையான எண்களின் ஒவ்வொரு எல்லையற்ற வரிசையும் ஒரு சலிப்பான முறையில் அதிகரிக்கும் எல்லையற்ற தொடர்ச்சியைக் கொண்டுள்ளது அல்லது சலிப்பான முறையில் குறைந்து வரும் எல்லையற்ற தொடர்ச்சியைக் கொண்டுள்ளது என்பதை நிரூபிக்க ராம்சேயின் தேற்றம் எளிதாக்குகிறது என்றாலும், பால் எர்டாஸ் மற்றும் ஜார்ஜ் ஸ்சேக்கரெஸ் ஆகியோரால் நிரூபிக்கப்பட்ட முடிவு மேலும் செல்கிறது. எடுத்துக்காட்டு r = 3 மற்றும் s = 2 க்கு, மூன்று எண்களின் எந்தவொரு வரிசைமாற்றமும் நீளம் மூன்றின் தொடர்ச்சியை அதிகரிக்கிறது அல்லது நீளம் இரண்டின் தொடர்ச்சியை குறைக்கிறது என்று சூத்திரம் நமக்குச் சொல்கிறது. எண்களின் ஆறு வரிசைமாற்றங்களில் 1,2,3:1,2,3 மூன்று எண்களையும் உள்ளடக்கிய அதிகரித்து வரும் தொடர்ச்சியைக் கொண்டுள்ளது 1,3,2 குறைந்து வரும் தொடர்ச்சியைக் கொண்டுள்ளது 3,2 2,1,3 குறைந்து வரும் தொடர்ச்சியைக் கொண்டுள்ளது 2 2,3,1 இரண்டு குறைந்து வரும் தொடர்ச்சிகளைக் கொண்டுள்ளது, 2,1 மற்றும் 3,1 3,1,2 இரண்டு குறைந்து வரும் தொடர்ச்சிகளைக் கொண்டுள்ளது, 3,1 மற்றும் 3,2 3,2,1 மூன்று குறைந்து வரும் நீளம்-2 தொடர்ச்சிகளைக் கொண்டுள்ளது, 3,2,3,1 மற்றும் 2,1. மாற்று விளக்கங்கள் வடிவியல் விளக்கம் ஒரு வரிசையில் உள்ள எண்களின் நிலைகளை யூக்ளிடியன் தளத்தில் உள்ள புள்ளிகளின் x-ஆயத்தங்கள் என்றும், எண்களை y-ஆயத்தங்கள் என்றும் ஒருவர் விளக்கலாம்; மாறாக, தளத்தில் அமைக்கப்பட்ட எந்த புள்ளிக்கும், புள்ளிகளின் y-ஆயத்தங்கள், அவற்றின் x-ஆயத்தங்களால் வரிசைப்படுத்தப்பட்டு, எண்களின் வரிசையை உருவாக்குகின்றன (இரண்டு புள்ளிகள் சமமான x-ஆயத்தங்களைக் கொண்டிருக்காவிட்டால்). வரிசைகள் மற்றும் புள்ளி தொகுப்புகளுக்கு இடையிலான இந்த மொழிபெயர்ப்பின் மூலம், குறைந்தபட்சம் rs − r − s + 2 புள்ளிகளின் எந்த தொகுப்பிலும் r − 1 நேர்மறை-சாய்வு விளிம்புகள் அல்லது s − 1 எதிர்மறை-சாய்வு விளிம்புகளின் பலகோண பாதையை நாம் காணலாம் என்று எர்டாஸ்-செகெரெஸ் தேற்றத்தை விளக்கலாம். குறிப்பாக (r = s ஐ எடுத்துக்கொள்வது), குறைந்தபட்சம் n புள்ளிகளின் எந்த தொகுப்பிலும், ஒரே-அடையாள சரிவுகளுடன் குறைந்தபட்சம் θ′ விளிம்புகளின் பலகோண பாதையை நாம் காணலாம். உதாரணமாக, r = s = 5 ஐ எடுத்துக் கொண்டால், குறைந்தது 17 புள்ளிகளைக் கொண்ட எந்தவொரு தொகுப்பும் நான்கு முனை பாதையைக் கொண்டுள்ளது, இதில் அனைத்து சரிவுகளும் ஒரே அடையாளத்தைக் கொண்டுள்ளன. அத்தகைய பாதை இல்லாத rs − r − s + 1 புள்ளிகளுக்கு ஒரு எடுத்துக்காட்டு, இந்த எல்லை இறுக்கமாக இருப்பதைக் காட்டுகிறது, ஒரு (r − 1) க்கு (s − 1) கட்டத்தால் ஒரு சிறிய சுழற்சியைப் பயன்படுத்துவதன் மூலம் உருவாக்க முடியும். வரிசைமாற்ற முறை விளக்கம் குறைந்தபட்சம் rs + 1 நீளத்தின் ஒவ்வொரு வரிசைமாற்றமும் 1,2,3,., r + 1 அல்லது s + 1, s,., 2,1 வடிவத்தைக் கொண்டிருக்க வேண்டும் என்று எர்டாஸ்-செகெரெஸ் தேற்றம் வரிசைமாற்ற வடிவங்களின் மொழியில் விளக்கப்படலாம். Erdós-Szekeres தேற்றத்தை பல்வேறு வழிகளில் நிரூபிக்க முடியும்; பின்வரும் இரண்டு உட்பட Erdós-Szekeres தேற்றத்தின் ஆறு வெவ்வேறு ஆதாரங்களை ஆய்வு செய்கிறது. ஸ்டீல் கணக்கெடுக்கப்பட்ட பிற சான்றுகளில் எர்டாஸ் மற்றும் செகெரஸ் ஆகியோரின் அசல் ஆதாரமும், மற்றும், மற்றும் சான்றுகளும் அடங்கும். புறா துளை கோட்பாடு நீளம் (r−1) (s−1) + 1 இன் வரிசையைக் கொடுத்தால், ஒவ்வொரு எண்ணையும் ஜோடியுடன் (ஏஆஇ, பை) வரிசையில் பெயரிடுங்கள், இதில் ஏஐ என்பது நீ மற்றும் பை உடன் முடிவடையும் மிக நீண்ட சலிப்பாக அதிகரிக்கும் தொடர்ச்சியின் நீளம் ஆகும், இது நீண்ட சலிப்பாக குறைந்து வரும் தொடர்ச்சியின் நீளம் ஆகும். வரிசையில் உள்ள ஒவ்வொரு இரண்டு எண்களும் வெவ்வேறு ஜோடியுடன் பெயரிடப்பட்டுள்ளனஃ என்றால் பின்னர், மறுபுறம் என்றால். ஆனால் (r−1) (s−1) சாத்தியமான லேபிள்கள் மட்டுமே உள்ளன, ஆயி அதிகபட்சமாக r−1 ஆகவும், பை அதிகபட்சமாக s−1 ஆகவும் இருந்தால், எனவே புறா துளை கொள்கையின்படி i இன் மதிப்பு இருக்க வேண்டும், இதற்கு ஆயி அல்லது பை இந்த வரம்பிற்கு வெளியே உள்ளது. ஐ வரம்பிற்கு வெளியே இருந்தால், நி என்பது குறைந்தபட்சம் r நீளத்தின் அதிகரிக்கும் வரிசையின் ஒரு பகுதியாகும், மேலும் பை வரம்பிற்கு வெளியே இருந்தால், நி என்பது குறைந்தபட்சம் s நீளத்தின் குறைந்து வரும் வரிசையின் ஒரு பகுதியாகும். இந்த ஆதாரத்தை ஒரு பக்க காகிதத்திற்கு வரவு வைக்கிறது மற்றும் அவர் ஆய்வு செய்யும் சான்றுகளில் "மென்மையான மற்றும் மிகவும் முறையான" என்று அழைக்கிறது. டில்வொர்த்தின் தேற்றம் மற்றொரு ஆதாரம் டில்வொர்த்தின் தேற்றத்தை பகுதி வரிசையில் சங்கிலி சிதைவுகள் அல்லது அதன் எளிய இரட்டை (மிர்ஸ்கியின் தேற்றம்) பயன்படுத்துகிறது. தேற்றத்தை நிரூபிக்க, வரிசையின் உறுப்பினர்களின் மீது ஒரு பகுதி வரிசையை வரையறுக்கவும், இதில் x என்பது x ≤ y எண்களாகவும், x வரிசையில் y ஐ விட பிந்தையதாகவும் இல்லாவிட்டால் பகுதி வரிசையில் y ஐ விட குறைவாகவோ அல்லது சமமாகவோ இருக்கும். இந்த பகுதி வரிசையில் ஒரு சங்கிலி என்பது சலிப்பாக அதிகரித்து வரும் தொடர்ச்சியாகும், மேலும் ஒரு ஆன்டிசைன் என்பது சலிப்பாக குறைந்து வரும் தொடர்ச்சியாகும். மிர்ஸ்கியின் தேற்றத்தின் படி, நீள சங்கிலி r உள்ளது, அல்லது வரிசையை அதிகபட்சம் r − 1 ஆன்டிசெயின்ஸாகப் பிரிக்கலாம்; ஆனால் அந்த விஷயத்தில் மிகப் பெரிய ஆன்டிசெயின்ஸ் குறைந்தபட்சம் நீளத்துடன் குறைந்து வரும் தொடர்ச்சியை உருவாக்க வேண்டும், மாற்றாக, டில்வொர்த்தின் தேற்றத்தின் படி, நீள s இன் ஆன்டிசெயின் உள்ளது, அல்லது வரிசையை அதிகபட்சமாக s − 1 சங்கிலிகளாகப் பிரிக்கலாம், அவற்றில் மிக நீளமானது குறைந்தபட்சம் r நீளத்தைக் கொண்டிருக்க வேண்டும். ராபின்சன்-ஷென்ஸ்டெட் கடிதத்தின் பயன்பாடு ராபின்சன்-ஷென்ஸ்டெட் கடிதத்தின் ஒரு இணைப்பாக முடிவையும் பெறலாம். ராபின்சன்-ஷென்ஸ்டெட் கடிதங்கள் ஒவ்வொரு வரிசையையும் ஒரு இளம் அட்டவணை பி உடன் தொடர்புபடுத்துகின்றன என்பதை நினைவில் கொள்ளுங்கள், அதன் உள்ளீடுகள் வரிசையின் மதிப்புகளாகும். அட்டவணை P பின்வரும் பண்புகளைக் கொண்டுள்ளதுஃ மிக நீண்ட தொடர்ச்சியின் நீளம் P இன் முதல் வரிசையின் நீளத்திற்கு சமம். மிக நீண்ட குறைந்து வரும் தொடர்ச்சியின் நீளம் P இன் முதல் நெடுவரிசையின் நீளத்திற்கு சமம். இப்போது, (r−1) (s−1) + 1 உள்ளீடுகளை (r−1) (s−1) அளவு கொண்ட ஒரு சதுர பெட்டியில் பொருத்த முடியாது, இதனால் முதல் வரிசை குறைந்தபட்சம் r நீளமாகவோ அல்லது கடைசி வரிசை குறைந்தபட்சம் s நீளமாகவோ இருக்கும்.