Кіріспе
Экстремалды граф теориясындағы тұжырымдама. Экстремалды граф теориясында Сземередидің тұрақтылық леммасы графты шектелген сандағы бөліктерге бөлуге болады, сонда бөліктер арасындағы жиектер тұрақты болады. Лемма, кездейсоқ графтардың кейбір қасиеттерін тығыз графтарға қолдануға мүмкіндік береді, мысалы, графтер ішінде берілген кіші графтардың қанша көшірмесі бар екенін санау. Эндре Сземереди 1975 жылы арифметикалық прогрессиялар туралы теоремасы үшін екі бөлікті графтар бойынша, ал 1978 жылы жалпы графтар бойынша лемманы дәлелдеді. Лемманың түрлері тұрақтылықтың әртүрлі түсініктерін пайдаланады және гиперграфтар сияқты басқа математикалық объектілерге де қолданылады.
In extremal graph theory, Szemerédi’s regularity lemma states that a graph can be partitioned into a bounded number of parts so that the edges between parts are regular. The lemma shows that certain properties of random graphs can be applied to dense graphs like counting the copies of a given subgraph within graphs. Endre Szemerédi proved the lemma over bipartite graphs for his theorem on arithmetic progressions in 1975 and for general graphs in 1978. Variants of the lemma use different notions of regularity and apply to other mathematical objects like hypergraphs.
Графты санау леммасы
Егер графтың реттелілігі туралы жеткілікті ақпарат болса, онда графтың ішіндегі белгілі бір кіші графтың көшірмелерінің санын шағын қателікке дейін санауға болады. Графты санау леммасы. Бұл лемма графтың реттелілік леммасымен біріктіріліп, графты жою леммасын дәлелдеуге мүмкіндік береді. Графты жою леммасы Роттың арифметикалық прогрессиялар туралы теоремасын дәлелдеу үшін қолданылуы мүмкін, ал оның жалпыламасы – гиперграфты жою леммасы, Сземереди теоремасын дәлелдеу үшін қолданылуы мүмкін. Графты жою леммасы тек қана қабырғаларды жоюдың орнына, қабырғаларды өңдеу арқылы индукцияланған кіші графтарға да қолданылады. Бұл Алон, Фишер, Кривелевич және Сегеди 2000 жылы дәлелдеді. Дегенмен, бұл реттелілік леммасының күштірек түрін қажет етті. Сземередидің реттелілік леммасы сиреп кеткен графтарда мағыналы нәтижелер бермейді. Сиреп кеткен графтардың қабырға тығыздығы тұрақты емес болғандықтан, реттелілік тривиальды түрде орындалады. Нәтиже тек теориялық сипатта болғанымен, кейбір әрекеттер жүйелілік әдісін үлкен графтарды қысу әдісі ретінде қолдануға бағытталған.
This can be combined with Szemerédi's regularity lemma to prove the Graph removal lemma. The graph removal lemma can be used to prove Roth's Theorem on Arithmetic Progressions, and a generalization of it, the hypergraph removal lemma, can be used to prove Szemerédi's theorem. The graph removal lemma generalizes to induced subgraphs, by considering edge edits instead of only edge deletions. This was proved by Alon, Fischer, Krivelevich, and Szegedy in 2000. However, this required a stronger variation of the regularity lemma. Szemerédi's regularity lemma does not provide meaningful results in sparse graphs. Since sparse graphs have subconstant edge densities, regularity is trivially satisfied. Even though the result seems purely theoretical, some attempts have been made to use the regularity method as compression technique for large graphs.
Алгоритмдік қолданбалар
Тығыз графтардағы ең үлкен кесілімді бағалауға арналған тиімді алгоритмді табу – әлсіз тұрақтылық леммасын әзірлеудің бастапқы себептерінің бірі болды. Макс кесу мәселесін 16/17-ден асырып шамалау NP-қиын екені көрсетілді, бірақ әлсіз тұрақтылық леммасының алгоритмдік нұсқасы аддитивті қателікпен тығыз графтар үшін макс кесуді шамалауға мүмкіндік беретін тиімді алгоритм ұсынады. Бұл идеялар тығыз графтардағы макс кесуді бағалау үшін тиімді үлгі алу алгоритмдеріне дейін жетілдірілді. Әлсіз тұрақтылық леммасының тар шектері тұрақты бөліністі табуға арналған тиімді алгоритмдерге мүмкіндік береді. Графтық тұрақтылық теориялық компьютерлік ғылымның матрицалық көбейту және коммуникациялық күрделілік сияқты әртүрлі салаларында қолданылады.
Күші бар жүйелілік леммасы
Күшейтілген тұрақтылық леммасы – Алон, Фишер, Кривелевич және Сегедидің 2000 жылы дәлелдеген тұрақтылық леммасының күштірек түрі. Ол интуитивті түрде тұрақты емес жұптар туралы ақпарат береді және индуцирленген графты жою леммасын дәлелдеуге қолданылуы мүмкін.
Теңгерімділік туралы ескертулер
Бөлініс теңдікті сақтаса, кез келген екі жиынның мөлшері ең көп дегенде бірге айырмашылығы болады. Әр итерацияда теңдеуді қолдану арқылы, тұрақтылық леммасының дәлелдемесі тұрақтылық леммасының тең нұсқасын дәлелдеуге бейімделуі мүмкін. Тұрақтылық леммасын оның тең нұсқасымен алмастыру арқылы, жоғарыдағы дәлелдеме мықты тұрақтылық леммасының тең нұсқасын дәлелдей алады, мұнда және тең бөліністер болып табылады.
Мотивация
Бұл қорытынды энергияның шағын артуын одан да терең зерттейді. Ол бізге әр бөліктен үлкен мөлшердегі элементтерді қамтитын, өзара реттелген қосалқы жиындықтармен бірге бөліністі ұсынады. Сонымен қатар, сәйкес келетін қосалқы жиындықтар арасындағы тығыздық, сәйкес келетін бөліктер арасындағы тығыздықтан "қатты ерекшеленбейді".
Қорытынды дәлелдеу
Біз тек екінші шарттың тек қана тұрақты болуын талап ететін әлсіз нәтижені дәлелдейміз. Толық нұсқаны әр бөліктен көбінесе жұптық тұрақты болатын жиынтықтарды таңдап, оларды біріктіру арқылы дәлелдеуге болады. Енді, біз мықты тұрақтылық леммасын қолданып, теңдеулі бөлуді іздейміз, ол тұрақтылықты қамтамасыз ететін бөлу және теңдеулі өңдеуді іздейміз, ол тұрақтылықты қамтамасыз ететін бөлуі, сонда және .
Енді, егер болса, әрбір жиынынан кездейсоқ бір төбе таңдаймыз және жиынында төбесі бар болсын делік. Біз жиынтықтарының барлық шарттарды ықтималдығымен қанағаттандыратынын көрсетеміз.
шартты орнатсақ, теңдеулі бөлу болғандықтан, бірінші шарт тривиальды түрде орындалады. ішіндегі иррегуляр жұптардың саны болғандықтан, жұбының иррегуляр болу ықтималдығы, біріктіру принципі бойынша, кем дегенде бір жұбының иррегуляр болу ықтималдығы .
Олай болса, Марков теңсіздігі бойынша, ықтималдығымен, ең көп жұп иррегуляр болуы мүмкін. Біріктіру принципі бойынша, барлық шарттардың орындалу ықтималдығы .