Кіріспе
Математикалық комбинаторикадағы мәлімдеме
Комбинаторикада Рамзи теоремасы, өзінің графтық теориялық формаларының бірінде, жеткілікті үлкен толық графтың кез келген жиектерінің түсті таңбалауында (түстермен) монохроматикалық кликалар табылатынын айтады. Теореманы екі түс үшін (мысалы, көк және қызыл) көрсету үшін, r және s кез келген екі оң бүтін сан болсын. Рамзи теоремасы R(r, s) ең кіші оң бүтін саны бар екенін көрсетеді, онда R(r, s) төбелері бар толық графтың кез келген көк-қызыл жиектерінің таңбалауында r төбелі көк клика немесе s төбелі қызыл клика болады. (Мұнда R(r, s) – r және s-ке тәуелді бүтін санды білдіреді.)
Рамзи теоремасы комбинаторикадағы негізгі нәтиже болып табылады. Бұл нәтиженің алғашқы нұсқасын Фрэнк Рамзи дәлелдеді. Бұл қазір Рамзи теориясы деп аталатын комбинаторлық теорияны бастады, ол тәртіпсіздіктің арасындағы реттелілікті іздейді: тұрақты қасиеттері бар субструктуралардың болуының жалпы шарттары. Бұл қолданыста монохроматикалық ішкі жиынның, яғни бір түстің ғана жалғасқан жиектерінен тұратын ішкі жиынның болуы туралы сұрақ туындайды. Бұл теореманың кеңейтімі кез келген шекті түстер санына, екі емес, қолданылады. Нақтырақ айтқанда, теорема кез келген берілген түстер саны үшін c, және кез келген берілген бүтін сандар үшін , мұндай сан бар, , егер реттегі толық графтың жиектері c түрлі түспен боялған болса, онда 1 мен c арасындағы кейбір i үшін, оның жиектері i түсімен толық субграфты қамтиды. Жоғарыдағы ерекше жағдайда 1=c = 2 (және және ).
R ((3, 3) = 6
6 төбесі бар толық графтың қабырғалары қызыл және көк түспен боялған делік. v төбесін таңдаңыз. v төбесіне 5 қабырға түседі, сондықтан (көгершін ұясы принципі бойынша) олардың кем дегенде 3-і бір түс болуы керек. Жалпылықты жоғалтпай, осы қабырғалардың кем дегенде 3-і – v төбесін r, s және t төбелерімен байланыстыратын – көк деп есептейміз. (Егер олай болмаса, келесіде қызыл мен көкті ауыстырыңыз.) Егер (rs), (rt), (st) қабырғаларының кез келгені де көк болса, онда бізде толығымен көк үшбұрыш болады. Әйтпесе, осы үш қабырғаның барлығы қызыл болады және бізде толығымен қызыл үшбұрыш болады. Бұл аргумент кез келген бояу үшін жұмыс істейтіндіктен, кез келген бояуда монохроматикалық үшбұрыш болады, сондықтан R(3, 3) ≤ 6. Бұл мәселенің танымал түрі «достар мен жаттар туралы теорема» деп аталады. Дәлелдеудің тағы бір әдісі – екі рет санау. Ол былай жүзеге асырылады: (xy) қабырғасы қызыл және (yz) қабырғасы көк болатындай x, y, z төбелерінің реттелген үштіктерінің санын санаңыз. Біріншіден, кез келген төбе 1=0 × 5 = 0 (төбеден шығатын барлық қабырғалар бір түсті), 1=1 × 4 = 4 (төрт қабырға бір түсті, біреуі басқа түсті) немесе 1=2 × 3 = 6 (үш қабырға бір түсті, екеуі басқа түсті) мұндай үштіктердің ортасында болады. Сондықтан 1=6 × 6 = 36 мұндай үштік болуы мүмкін. Екіншіден, кез келген монохроматикалық емес үшбұрыш (xyz) үшін дәл осындай екі үштік болады. Сондықтан ең көп дегенде 18 монохроматикалық емес үшбұрыш бар. Демек, 20 үшбұрыштың кем дегенде 2-сі монохроматикалық. Керісінше, R(3, 3) > 5 екенін көрсету үшін монохроматикалық үшбұрышсыз 2 түспен бояуға болады. Бірегей бояу оң жақта көрсетілген. Осылайша R(3, 3) = 6. R(3, 3) ≤ 6 екенін дәлелдеу міндеті 1953 жылы Уильям Лоуэлл Путнам математикалық сайысының, сондай-ақ 1947 жылы Венгрия математикалық олимпиадасының тапсырмаларының бірі болды.
Түстердің көп болуы
2-лемма. Егер c > 2 болса, онда
Дәлелдеме. c төбесі бар толық графты қарастырып, оның қабырғаларын c түспен бояңыз. Енді "түс соқырлығына" ұшырап, c − 1 және c түстерінің бір түс екенін елестетіңіз. Осылайша, граф қазір (c − 1) түспен боялған. Мұндай графтың анықтамасы бойынша, онда 1 ≤ i ≤ c − 2 үшін i түсімен монохроматикалық боялған немесе "қосылған түспен" боялған болады. Бірінші жағдайда дәлелдеме аяқталды. Екінші жағдайда, көру қабілетімізді қалпына келтіріп, анықтамадан, (c − 1) монохромды немесе c монохромды болуы керек екенін көреміз. Екі жағдайда да дәлелдеме толық. 1-лемма кез келген R(r,s) шекті екенін көрсетеді. 2-леммадағы теңсіздіктің оң жағы c түс үшін Рамзи санын, аз түстер үшін Рамзи сандары арқылы көрсетеді. Сондықтан, кез келген түс саны үшін шекті. Бұл теореманы дәлелдейді.
Рамзи сандары
Рамзи теоремасындағы R(r, s) сандары (және олардың екі түстен артық түстерге кеңейтілуі) Рамзи сандары деп аталады. Рамзи саны R(m, n) қонақтардың ең аз санын анықтайды, яғни R(m, n) қонақты шақыру керек, сонда кем дегенде m адам бір-бірін таниды немесе кем дегенде n адам бір-бірін танымайды. Графтар теориясының тілінде, Рамзи саны – бұл 1=v = R(m, n) төбелерінің ең аз саны, сондықтан v реттік барлық бағытталмаған қарапайым графтарда m реттік толық граф немесе n реттік тәуелсіз жиын болады. Рамзи теоремасы мұндай санның барлық m және n үшін бар екенін көрсетеді. Симметрия бойынша 1=R(m, n) = R(n, m) теңдігі дұрыс. R(r, s) үшін жоғарғы шекті теореманың дәлелінен алуға болады, ал басқа аргументтер төменгі шектерді береді. (Бірінші экспоненциалды төменгі шекті Пауль Эрдос ықтималдық әдісін қолдана отырып тапқан.) Дегенмен, ең шағын төменгі және ең жоғарғы шектер арасында үлкен айырмашылық бар. Сонымен қатар, R(r, s) сандарының нақты мәнін білетін r және s сандары өте аз. R(r, s) үшін төменгі шекті L есептеу үшін көбінесе графтың көк және қызыл түсті субграфтары болмайтын көк/қызыл бояуын көрсету қажет. Мұндай қарсы мысал Рамзи графигі деп аталады. Брендан Маккей белгілі Рамзи графтарының тізімін жүргізеді. Жоғарғы шектерді анықтау көбінесе әлдеқайда қиын: қарсы мысалдың жоқтығын растау үшін барлық мүмкін бояуларды тексеру керек немесе оның жоқтығын математикалық тұрғыдан дәлелдеу керек.
By symmetry, it is true that 1=R(m, n) = R(n, m). An upper bound for R(r, s) can be extracted from the proof of the theorem, and other arguments give lower bounds. (The first exponential lower bound was obtained by Paul Erdős using the probabilistic method.) However, there is a vast gap between the tightest lower bounds and the tightest upper bounds. There are also very few numbers r and s for which we know the exact value of R(r, s). Computing a lower bound L for R(r, s) usually requires exhibiting a blue/red colouring of the graph with no blue subgraph and no red subgraph. Such a counterexample is called a Ramsey graph. Brendan McKay maintains a list of known Ramsey graphs. Upper bounds are often considerably more difficult to establish: one either has to check all possible colourings to confirm the absence of a counterexample, or to present a mathematical argument for its absence.
Есептеу күрделілігі
Күрделі компьютерлік бағдарлама барлық бояуларды жеке-жеке қарастырмастан, оларды жоюға қабілді; алайда, бұл өте қиын есептеу міндеті, және қазіргі бағдарламалық жасақтамалар оны тек шағын өлшемде ғана шеше алады. Әрбір толық графтың *n*( *n* - 1) / 2 жиегі болады, сондықтан күшпен іздеу (brute force) әдісі қолданылса, *c* түс үшін іздеуге *c*<sup>*n*</sup> графтарды қарастыру қажет. Демек, *c* бояу және ең көп дегенде *n* түйін үшін барлық мүмкін графтарды (күшпен іздеу арқылы) іздеудің күрделілігі *O*( *c*<sup>*n*</sup>) болады. Кванттық компьютерлердің пайда болуымен жағдай күрт өзгермейді. Құрылымсыз деректер жиынтығын іздеуге арналған ең белгілі алгоритмдердің бірі классикалық компьютерлерге қарағанда тек квадраттық жылдамдыққа ие (мысалы, Гровер алгоритмі), сондықтан есептеу уақыты түйіндер санына қатысты экспоненциалды болып қала береді.
Индукцияланған Рамзи
Индуцированды субграфтар үшін Рамзи теоремасының көпке танылмаған, бірақ қызықты аналогы бар. Шамамен айтқанда, монохроматикалық субграфты табудың орнына, енді бізден монохроматикалық индуцирленген субграфты табу талап етіледі. Бұл түрінде толық графтарға ғана назар аудару жеткіліксіз, себебі толық субграфтың болуы индуцирленген субграфтың болуын қамтамасыз етпейді. Келесі бөлімдегі теореманың сапалық тұжырымын 1970 жылдары Эрдос, Хайнал және Поса, сондай-ақ Деубер мен Рёдль дербес түрде дәлелдеген. Одан бері индуцирленген Рамзи сандарының жақсы шектерін табуға қатысты көптеген зерттеулер жүргізілді.
Айтылым
H графигі n төбесінде болсын. Онда, G графигі бар, оның жиектерін екі түспен бояғанда, әр бояу H графигінің монохроматикалық индукцияланған көшірмесін (яғни, H-ге изоморфты және жиектері монохроматикалық болатын G графигінің индукцияланған кіші графигін) қамтиды. G графигінің ең кішкентай төбелер саны – индукцияланған Рамзи саны. Кейде біз мәселенің асимметриялық түрін де қарастырамыз. Біз оны G графигінің ең кішкентай төбелер саны деп анықтаймыз, сондықтан G графигінің жиектерін тек қызыл немесе көк түспен бояғанда, X графигінің қызыл индукцияланған кіші графигі немесе Y графигінің көк индукцияланған кіші графигі табылады.
Sometimes, we also consider the asymmetric version of the problem. We define to be the smallest possible number of vertices of a graph G such that every coloring of the edges of G using only red or blue contains a red induced subgraph of X or blue induced subgraph of Y.
Ерекше жағдайлар
Индуцияланған Рамзи сандарының жалпы шектері графиктің мөлшеріне қатысты экспоненциалды болғанымен, ерекше графтар кластарында (әсіресе, сиректерінде) мінез-құлқы мүлдем басқаша. Осы кластардың көптегені үшін индуцияланған Рамзи сандары төбелерінің санына қатысты полиномдық болады. Егер H графы k төбелі цикл, жол немесе жұлдыз болса, онда ол k-ға қатысты сызықтық екені белгілі. Сондай-ақ, ол сызықтықтан артық екені белгілі (яғни ). Бұл, дәстүрлі Рамзи сандарынан өзгеше, себебі Бурр-Эрдёс болжамы (қазір дәлелденген) r(H) сызықтық екенін көрсетеді (ағаштар 1-дегенеративті болғандықтан). H графы k төбелі және шектелген Δ дәрежелі болса, онда , деп болжанған, мұндағы d тұрақтысы тек Δ-ға ғана тәуелді. Бұл нәтижені алғаш рет Łuczak және Rödl 1996 жылы дәлелдеді, d(Δ) биіктігі Δ-ға байланысты екіден тұратын мұнара түрінде өседі. Содан бері d(Δ) үшін одан да ақылға қонымды шектер алынды. 2013 жылы Конлон, Фокс және Чжао сирек псевдорандомдық графтар үшін санау леммасын қолданып, , екенін көрсетті, мұндағы көрсеткіш тұрақты факторларға дейін ең жақсы мәнге ие.
Жалпылау
Рамзи сандарына ұқсас, біз гиперграфтар мен көп түсті жағдайлар үшін индуцияланған Рамзи сандарының ұғымын жалпылауға болады.
Түстердің көптігі
Сонымен қатар, Рэмси теоремасын көп түстік жағдайға жалпылауға болады. Графтар үшін, G графигіндегі жиектердің r түске боялған кез келген түсі үшін, барлық жиектері i-ші түспен боялған (1 ≤ i ≤ r) индукцияланған H-ға изоморфты кішіграфты қамтитын ең аз төбелер саны деп анықтаймыз. (H-тың q көшірмесі). Екі түстік жағдайдағы шектеуді итеративті түрде қолдану арқылы, шамамен биіктігі ~ log q екілік мұнарасы болатын шектеу алуға болады. Қазіргі кездегі ең жақсы белгілі шектеу Фокс пен Судаковқа тиесілі, ол , мұнда k – H графигінің төбелерінің саны, ал c – тек q-ға тәуелді тұрақты сан.
Гиперграфтар
Біз индуцирленген Рамзи сандарының анықтамасын d біркелкі гиперграфтарға қарапайым ғана «граф» сөзін «гиперграф» деп өзгерту арқылы кеңейте аламыз. Сонымен қатар, индуцирленген Рамзи сандарының көп түсті нұсқасын да алдыңғы тармақшадағыдай анықтауға болады. H – k төбесі бар d біркелкі гиперграф болсын. Функцияны былай анықтаймыз: және i ≥ 1 үшін. Гиперграф контейнері әдісін қолдана отырып, Конлон, Деламоника, Ла Флер, Рёдль және Шахт d ≥ 3, q ≥ 2 үшін, тек d және q-ға ғана тәуелді болатын кейбір тұрақты c үшін екенін көрсетті. Атап айтқанда, бұл нәтиже 1=d = 3 жағдайындағы дәстүрлі Рамзи санының ең жақсы белгілі шегімен сәйкес келеді.
Шексіз графиктер
Тағы бір нәтиже, сонымен қатар Рамзи теоремасы деп аталады, шексіз графтарға қолданылады. Егер шекті графтар да талқыланса, оны көбінесе «Шексіз Рамзи теоремасы» деп атайды. Графты суреттеу арқылы туындайтын түсінік, шекті графтардан шексіз графтарға көшкенде азаяды, сондықтан осы саладағы теоремалар әдетте жиындық теориялық терминологияда тұжырымдалады. Теорема. X – шексіз жиын болсын және оның элементтерін (X жиынының n мөлшерлі ішкі жиындарын) c түрлі түспен бояңыз. Онда X-тің шексіз M ішкі жиыны бар, сонда M-нің n мөлшерлі барлық ішкі жиындары бір түспен боялған болады. Дәлел. Дәлел n, ішкі жиынның мөлшері бойынша индукциямен жүргізіледі. Егер n = 1 болса, онда бұл тұжырымдама шексіз жиынды шекті сандарға бөлгенде, олардың біреуі шексіз болады дегенмен тең. Бұл айқын. Егер теорема n ≤ r үшін дұрыс деп есептесек, оны n = r + 1 үшін дәлелдейміз. X жиынының (r + 1) элементті ішкі жиындарының c бояуын берілген болсын, X элементін және Y жиынын қарастырайық. Әр r элементті ішкі жиынға (X жиынының (r + 1) элементті ішкі жиынын алу үшін) қосып, Y жиынының r элементті ішкі жиындарына c бояуын индукциялаймыз. Индукциялық гипотеза бойынша, Y-тің шексіз ішкі жиыны бар, онда оның әрбір r элементті ішкі жиыны индукцияланған бояуда бір түспен боялған. Демек, элемент және шексіз ішкі жиын бар, сонда X-тің барлық (r + 1) элементті ішкі жиындары, оның ішіндегі элементтер мен Y-тің r элементтері бір түспен боялған. Сол аргумент бойынша, Y-тің ішінде элемент және сол қасиеттері бар Y-тің шексіз ішкі жиыны бар. Индукциялық түрде, біз әрбір (r + 1) элементті ішкі жинның түсі i(1) < i(2) < … < i(r + 1) тек i(1) мәніне ғана тәуелді болатын тізбекті аламыз. Бұдан әрі, осы түс бірдей болатындай i(n) мәндерінің саны шексіз көп. Осы мәндерді таңдап, қажетті монохроматикалық жиынды аламыз. Рамзи теоремасының графтар үшін күштірек, бірақ теңгерімсіз шексіз түрі – Эрдос-Душник-Миллер теоремасы, әр шексіз графта санауға болатын шексіз тәуелсіз жиын немесе түпнұсқа графтың кардиналдығымен бірдей кардиналды шексіз клика бар екенін айтады.
Гиперграфтар
Теореманы гиперграфтарға да қолдануға болады. m гиперграф – "қабырғалары" m төбелер жиынынан тұратын граф. Ал қалыпты графта қабырға 2 төбелер жиыны болып табылады. Гиперграфтар үшін Рамзи теоремасының толық тұжырымы: кез келген m және c бүтін сандары және кез келген бүтін сандар үшін , мұндай бір сан бар, егер ретті толық m гиперграфтың гиперқабырғалары c түрлі түспен боялса, онда 1 мен c арасындағы кейбір i үшін гиперграфта толық sub m ретті гиперграф болуы керек, оның гиперқабырғаларының бәрі i түсімен боялған. Бұл теорема әдетте графтың "гиперлігі" m-ге индукция арқылы дәлелденеді. Дәлелдің базалық жағдайы 1=m = 2, бұл жоғарыдағы теоремамен толық сәйкес келеді. 1=m = 3 үшін біз бір тривиалды емес Рамзи санының нақты мәнін білеміз, атап айтқанда 1=R(4, 4; 3) = 13. Бұл фактіні Брендан Маккей және Станислав Радисзовский 1991 жылы анықтады. Сонымен қатар, бізде: R(4, 5; 3) ≥ 35, R(4, 6; 3) ≥ 63 және R(5, 5; 3) ≥ 88 бар.
Сансыз көп кардиналдар
Бөлімдеу есебі тұрғысынан Рамзи теоремасын барлық шекті n және k үшін де тұжырымдауға болады. Вацлав Сиерпинский Рамзи теоремасы өлшемді графтарға қатысты қолданылмайтынын көрсетті. Атап айтқанда, континуум гипотезасы Стево Тодорчевичтің ZFC-де , екенін көрсетті, бұл Джастин Т. Мурдің мәлімдемесінен әлдеқайда күшті. Жағымды жағынан, Рамзи кардиналы, , – байланысты формулаға сәйкес келу үшін аксиоматикалық түрде анықталған үлкен кардинал: Рамзи кардиналдарының бар екендігі ZFC-де дәлелдене алмайды.
Таңдау аксиомасының байланысы
Кері математикада Рамзи теоремасының шексіз графтар (n = 2 жағдайы) мен шексіз мультиграфтар (n ≥ 3 жағдайы) арасындағы дәлелдеу күшінде маңызды айырмашылық бар. Теореманың мультиграф түрі арифметикалық түсінік аксиомасымен шамалас, осылайша ол екінші реттік арифметиканың ACA0 кіші жүйесінің құрамына кіреді, кері математикадағы бес үлкен кіші жүйенің бірі. Ал Дэвид Ситапунның теоремасы бойынша, теореманың граф түрі ACA0-дан әлсіз және (Ситапунның нәтижесін басқа нәтижелермен біріктіргенде) ол бес үлкен кіші жүйенің біріне жатпайды. Дегенмен, ZF аксиомалары бойынша граф түрі классикалық Кёниг леммасын тудырады, бірақ керісінше дұрыс емес, себебі Кёниг леммасы осы контексте шекті жиындардан саналатын таңдаумен эквивалентті.