Erdős–Gallai theorem
எர்டாஸ்-கல்லாய் தேற்றம் என்பது ஒருங்கிணைந்த கணிதத்தின் ஒரு கிளையான வரைபடக் கோட்பாட்டின் விளைவாகும். இது வரைபட உணர்தல் சிக்கலைத் தீர்ப்பதற்கான இரண்டு அறியப்பட்ட அணுகுமுறைகளில் ஒன்றை வழங்குகிறது, அதாவது. இது ஒரு எளிய வரைபடத்தின் டிகிரி வரிசையாக இயற்கையான எண்களின் வரையறுக்கப்பட்ட வரிசைக்கு தேவையான மற்றும் போதுமான நிபந்தனையை வழங்குகிறது. இந்த நிபந்தனைகளுக்குக் கீழ்ப்படும் ஒரு வரிசை "கிராஃபிக்" என்று அழைக்கப்படுகிறது. இந்த தேற்றம் 1960 ஆம் ஆண்டில் பால் எர்டாஸ் மற்றும் திபோர் கல்லாய் ஆகியோரால் வெளியிடப்பட்டது, அவர்களின் பெயரால் இது பெயரிடப்பட்டது. கூற்று எதிர்மறை அல்லாத முழு எண்களின் வரிசையை n செங்குத்துகளில் ஒரு வரையறுக்கப்பட்ட எளிய வரைபடத்தின் டிகிரி வரிசையாக குறிப்பிட முடியும், மேலும் ஒவ்வொரு உள்ளத்திற்கும் சமமாக இருந்தால் மட்டுமே. சான்றுகள் எண்களின் வரிசை கிராஃபிக் ஆக இருக்க எர்டாஸ்-கல்லாய் தேற்றத்தின் நிபந்தனைகள் அவசியம் என்பதைக் காண்பிப்பது கடினம் அல்ல. டிகிரிகளின் கூட்டுத்தொகை சமமாக இருக்க வேண்டும் என்ற தேவை கைகுலுக்கும் லெம்மாவாகும், இது ஏற்கனவே யூலர் தனது 1736 காகிதத்தில் கோனிக்ஸ்பெர்க்கின் பாலங்களில் பயன்படுத்தப்பட்டது. மிகப்பெரிய டிகிரிகளின் கூட்டுத்தொகைக்கும் மீதமுள்ள டிகிரிகளின் கூட்டுத்தொகைக்கும் இடையிலான சமத்துவமின்மையை இரட்டை எண்ணிக்கையால் நிறுவ முடியும்ஃ இடது புறம் மிக உயர்ந்த டிகிரி செங்குத்துகளுக்கு இடையில் விளிம்பு-வெர்டெக்ஸ் அருகாமைகளின் எண்ணிக்கையை அளிக்கிறது, அத்தகைய ஒவ்வொரு அருகாமையும் ஒன்று அல்லது இரண்டு உயர் டிகிரி இறுதிப் புள்ளிகளுடன் ஒரு விளிம்பில் இருக்க வேண்டும், வலதுபுறத்தில் உள்ள சொல் அதிகபட்ச எண்ணிக்கையிலான விளிம்பு-வெர்டெக்ஸ் அருகாமைகளை வழங்குகிறது, இதில் இரண்டு இறுதிப் புள்ளிகளும் அதிக டிகிரியைக் கொண்டுள்ளன, மேலும் வலது மேல் வரம்பில் மீதமுள்ள சொல் சரியாக ஒரு உயர் டிகிரி இறுதிப் புள்ளியைக் கொண்ட விளிம்புகளின் எண்ணிக்கையை வழங்குகிறது. எனவே, ஆதாரத்தின் மிகவும் கடினமான பகுதி என்னவென்றால், இந்த நிபந்தனைகளுக்குக் கீழ்ப்படும் எண்களின் எந்தவொரு வரிசைக்கும், ஒரு வரைபடம் உள்ளது, அதற்காக அது டிகிரி வரிசை. இதன் அசல் சான்று நீண்டதாகவும், சம்பந்தப்பட்டதாகவும் இருந்தது. நெட்வொர்க் ஓட்டத்தின் கருத்துக்களை அடிப்படையாகக் கொண்டு கிளாட் பெர்ஜ் ஒரு குறுகிய ஆதாரத்தை மேற்கோள் காட்டுகிறார். சௌதம் அதற்கு பதிலாக டிகிரிகளின் கூட்டுத்தொகையில் கணித தூண்டல் மூலம் ஒரு ஆதாரத்தை வழங்குகிறார்ஃ அவர் வரிசையில் ஒரு எண்ணின் முதல் குறியீடாக இருக்கட்டும் (அல்லது அனைத்தும் சமமாக இருந்தால் கடைசி எண்), ஒரு வழக்கு பகுப்பாய்வைப் பயன்படுத்தி, வரிசையில் கடைசி எண்ணிலிருந்து ஒன்றைக் கழிப்பதன் மூலம் உருவாக்கப்பட்ட வரிசை (இந்த கழித்தல் அதை பூஜ்ஜியமாக மாற்றும் என்றால் கடைசி எண்ணை அகற்றுவது) மீண்டும் கிராஃபிக் ஆகும், மேலும் ஒன்று கழிக்கப்பட்ட இரண்டு நிலைகளுக்கு இடையில் ஒரு விளிம்பைச் சேர்ப்பதன் மூலம் அசல் வரிசையைக் குறிக்கும் வரைபடத்தை உருவாக்குகிறது. கொடுக்கப்பட்ட டிகிரி வரிசையால் வரம்புக்குட்பட்ட டிகிரிகளைக் கொண்ட "சப்ரியலிஸேஷன்களின்" வரிசையைக் கவனியுங்கள். G என்பது ஒரு சப்-ரியலைசேஷன் மற்றும் i என்பது G இல் உள்ள ஒரு உச்சியின் மிகச்சிறிய குறியீடாக இருந்தால், அதன் டிகிரி டைக்கு சமமாக இல்லை என்றால், G மற்றொரு சப்-ரியலைசேஷனை உருவாக்கும் வகையில் மாற்றியமைக்கப்படலாம், இது வரிசையில் முந்தைய உச்சிகளின் டிகிரிகளை மாற்றாமல் உச்சியின் டிகிரியை அதிகரிக்கிறது. இந்த வகையான தொடர்ச்சியான படிகள் இறுதியில் கொடுக்கப்பட்ட வரிசையின் உணர்வை அடைய வேண்டும், இது தேற்றத்தை நிரூபிக்கிறது. முழு எண் பகிர்வுகளுடனான உறவு எர்டாஸ்-கல்லாய் தேற்றத்திற்கும் முழு எண் பகிர்வுகளின் கோட்பாட்டிற்கும் இடையிலான நெருங்கிய தொடர்புகளை விவரிக்கிறது. பின்னர் தொகுக்கப்படும் வரிசைப்படுத்தப்பட்ட முழு எண் வரிசைகள் பகிர்வுகளாக விளக்கப்படலாம். அவற்றின் முன்னொட்டு தொகைகளின் பெரியமயமாக்கலின் கீழ், பகிர்வுகள் ஒரு ஜாலகத்தை உருவாக்குகின்றன, இதில் ஒரு தனிப்பட்ட பகிர்வுக்கும் பகிர்வு வரிசையில் கீழே உள்ள மற்றொரு பகிர்வுக்கும் இடையிலான குறைந்தபட்ச மாற்றம் எண்களில் ஒன்றிலிருந்து ஒன்றைக் கழித்து, குறைந்தபட்சம் இரண்டு (பூஜ்ஜியமாக இருக்கலாம்) சிறிய எண்ணுடன் சேர்ப்பதாகும். ஐக்னர் மற்றும் ட்ரைஷ் காட்டியபடி, இந்த செயல்பாடு கிராஃபிக் என்ற பண்பைப் பாதுகாக்கிறது, எனவே எர்டாஸ்-கல்லாய் தேற்றத்தை நிரூபிக்க இந்த பிரதான வரிசையில் அதிகபட்சமாக இருக்கும் கிராஃபிக் காட்சிகளை வகைப்படுத்த போதுமானது. தொடர்புடைய பகிர்வுகளின் ஃபெரர்ஸ் வரைபடங்களின் அடிப்படையில் அவை அத்தகைய குணாதிசயத்தை வழங்குகின்றன, மேலும் இது எர்டாஸ்-கல்லாய் தேற்றத்திற்கு சமமானது என்பதைக் காட்டுகிறது. இதே போன்ற கோட்பாடுகள் எளிய இயக்கப்படும் வரைபடங்களின் டிகிரி வரிசைகள், சுழல்களுடன் கூடிய எளிய இயக்கப்படும் வரைபடங்கள் மற்றும் எளிய இருதரப்பு வரைபடங்களை விவரிக்கின்றன. முதல் சிக்கல் ஃபுல்கர்சன்-சென்-அன்ஸ்டீ தேற்றத்தால் வகைப்படுத்தப்படுகிறது. சமமான பிந்தைய இரண்டு நிகழ்வுகளும் கேல்-ரைசர் தேற்றத்தால் வகைப்படுத்தப்படுகின்றன. வலுவான பதிப்பு, சமத்துவமின்மையைக் கருத்தில் கொள்வது போதுமானது என்பதை நிரூபித்தது. எதிர் உந்துதலில் உள்ள வரைபடங்களுக்கான ஏற்றத்தாழ்வுகளின் தொகுப்பை கட்டுப்படுத்தவும். சமமாக தொகுக்கப்பட்ட நேர்மறை வரிசை d அதிகபட்சம் மற்றும் குறைந்தபட்சத்தைத் தவிர வேறு எந்த தொடர்ச்சியான உள்ளீடுகளையும் கொண்டிருக்கவில்லை என்றால் (மற்றும் நீளம் மிகப்பெரிய உள்ளீட்டைத் தாண்டுகிறது), பின்னர் அது th சமத்துவமின்மையை மட்டுமே சரிபார்க்க போதுமானது, எங்கே. பொதுமைப்படுத்தல் எதிர்மறை அல்லாத முழு எண்களின் வரையறுக்கப்பட்ட வரிசைகள் சமமாக இருந்தால் கிராஃபிக் மற்றும் கிராஃபிக் மற்றும் பெரியதாக இருக்கும் ஒரு வரிசை உள்ளது. இதன் மூலம் இந்த முடிவு கிடைத்துள்ளது. அதை மீண்டும் கண்டுபிடித்து இன்னும் நேரடி ஆதாரத்தை அளித்தார். ஹேவல்-ஹாக்கிமி வழிமுறை குறிப்புகள் பற்றியும் பார்க்கவும். . கல்லாய் தேற்றம் வரைபடக் கோட்பாட்டில் உள்ள தேற்றங்கள்