Рамзи теоремасы - Ramseys theorem - Wikipedia

Жылы комбинаторлық математика, Рэмси теоремасы, оның біреуінде графикалық-теориялық монохроматикалық болады деп тұжырымдайды клиптер кез-келгенінде шеткі таңбалау (түстермен) жеткілікті үлкен толық граф. Екі түстің теоремасын көрсету үшін (айталық, көк және қызыл) рұқсат етіңіз р және с кез келген екі оң болуы бүтін сандар.[1] Рэмси теоремасы ең аз оң сан бар деп айтады R(р, с) ол үшін көк-қызыл жиектің әр бояуы толық граф қосулы R(р, с) шыңдарда көк клика бар р шыңдар немесе қызыл клика қосулы с төбелер. (Мұнда R(р, с) екеуіне де тәуелді бүтін санды білдіреді р және с.)

Рэмси теоремасы - бұл комбинаторикадағы іргелі нәтиже. Бұл нәтиженің алғашқы нұсқасы дәлелденді Рэмси Ф.. Бұл қазір аталған комбинаторлық теорияны бастады Рэмси теориясы, тәртіпсіздіктер кезінде заңдылықты іздейді: тұрақты қасиеттері бар құрылымдардың болуының жалпы шарттары. Бұл қосымшада бұл туралы монохроматикалық ішкі жиындар, Бұл, ішкі жиындар бір түсті жалғанған жиектердің.

Бұл теореманың кеңеюі түстердің екеуіне емес, кез-келген ақырғы санына қолданылады. Дәлірек айтқанда, теоремада түстердің кез келген саны үшін, вжәне кез келген берілген бүтін сандар n1, …, nв, нөмір бар, R(n1, …, nв), егер тәртіптің толық графигінің шеттері болса R(n1, ..., nв) -мен боялған в әр түрлі түстер, содан кейін кейбіреулер үшін мен 1 мен аралығында в, ол толығымен болуы керек подограф тәртіп nмен оның шеттері түстерге сәйкес келеді мен. Жоғарыдағы ерекше жағдай бар в = 2 (және n1 = р және n2 = с).

Мысалдар

R(3, 3) = 6

2 шеттік белгісі Қ5 монохроматсыз Қ3

Толық графиктің шеттері 6 төбесінде қызыл және көк түске боялды делік. Шыңды таңдаңыз, v. 5 шеті бар v және солай ( көгершін қағазы ) олардың кем дегенде 3-і бірдей түсті болуы керек. Жалпылықты жоғалтпай біз шыңдарды қосатын осы шеттердің кем дегенде 3-ін аламыз, v, шыңдарға, р, с және т, көк. (Егер олай болмаса, қызыл және көк түстерін келесіге ауыстырыңыз.) Егер шеттері болса, (р, с), (р, т), (с, т), сондай-ақ көгілдір болса, онда бізде көк үшбұрыш бар. Егер олай болмаса, онда бұл үш шеті қызыл және бізде қызыл үшбұрыш бар. Бұл аргумент кез-келген бояуға сәйкес келетіндіктен, кез келген Қ6 құрамында монохромат бар Қ3, демек R(3, 3) ≤ 6. Мұның әйгілі нұсқасы деп аталады достар мен бейтаныс адамдар туралы теорема.

Баламалы дәлелдеу жұмыс істейді қос санау. Бұл келесідей: үш шыңның реттелген санын санау, х, ж, з, шеті, (xy), қызыл және шеті, (yz), көк. Біріншіден, кез-келген шың 0 = 5 = 0 (шыңның барлық шеттері бірдей түсті), 1 × 4 = 4 (төртеуі бірдей түс, бірі басқа түс) немесе 2 × ортасында болады 3 = 6 (үшеуі бірдей түс, екеуі басқа түс) осындай үштік. Сондықтан мұндай үштіктер ең көп дегенде 6 × 6 = 36 болады. Екіншіден, кез-келген монохроматикалық емес үшбұрыш үшін (xyz), дәл осындай үштік үшеуі бар. Сондықтан ең көп дегенде монохроматикалық емес үшбұрыш бар. Демек, ішіндегі 20 үшбұрыштың кем дегенде 2-сі Қ6 монохромат болып табылады.

Керісінше, а-ға 2 түсті болады Қ5 монохроматсыз Қ3, деп көрсетіп R(3, 3)> 5. Бірегей[2] бояу оң жақта көрсетілген. Осылайша R(3, 3) = 6.

Мұны дәлелдеудің міндеті R(3, 3) ≤ 6 проблемалардың бірі болды Уильям Лоуэлл Путнам атындағы математикалық байқау 1953 ж., сондай-ақ Венгрия математика олимпиадасында 1947 ж.

Көп түсті мысал: R(3, 3, 3) = 17

К-ның тек екі 3 бояуы16 монохроматты К.3. Бұрылмаған бояу (жоғарыда) және бұралған бояу (төменде).
K 16 partitioned into three Clebsch graphs twisted.svg

Көп түсті Рамзи нөмірі - бұл 3 немесе одан да көп түстерді қолданатын Рамзи нөмірі. (Симметрияға дейін) тек мән-мағынасы жоқ екі түрлі-түсті емес Рамсейдің саны бар, олар үшін дәл мәні белгілі R(3, 3, 3) = 17 және R(3, 3, 4) = 30.[3]

Бізде қызыл, жасыл және көк түстердің 3 түстерін пайдаланып, толық графиктің шеткі бояуы болды делік. Сонымен, жиек бояғышында монохроматикалық үшбұрыш жоқ деп есептейік. Шыңды таңдаңыз v. Шыңға қызыл жиегі бар шыңдар жиынын қарастырайық v. Бұл қызыл маңай деп аталады v. Қызыл маңы v ешқандай қызыл жиектерді қамтуы мүмкін емес, өйткені әйтпесе сол қызыл жиектің екі шетінен және шыңнан тұратын қызыл үшбұрыш болады v. Осылайша, қызыл аймаққа индукцияланған жиек бояуы v тек екі түсті, яғни жасыл және көк түстермен боялған жиектері бар. Бастап R(3, 3) = 6, қызыл маңы v ең көп дегенде 5 шыңды қамтуы мүмкін. Сол сияқты, жасыл және көк аудандар v әрқайсысында ең көп дегенде 5 шың болуы мүмкін. Басқа шыңнан бастап v өзі қызыл, жасыл немесе көк аудандардың бірінде орналасқан v, толық графикте ең көбі 1 + 5 + 5 + 5 = 16 шыңдар болуы мүмкін. Осылайша, бізде бар R(3, 3, 3) ≤ 17.

Мұны көру үшін R(3, 3, 3) ≥ 17, монохроматикалық үшбұрыштарды болдырмайтын 3 түстермен 16 шыңда толық графикке жиек бояуды салу жеткілікті. Мұндай бояғыштардың дәл екеуі бар екен Қ16, бұралмаған және бұралған деп аталатын бояулар. Екі бояу да оң жақтағы фигураларда көрсетілген, жоғарғы жағында бұралмаған бояу, ал төменгі жағында бұралған бояу.

Егер біз бұралмаған немесе бұралған бояудың кез-келген түсін таңдасақ Қ16, және шеттері көрсетілген түске ие дәл сол жиектер болатын графикті қарастырайық, біз аламыз Клебш графигі.

3 түсті боялған екі бірдей бояу бар екені белгілі Қ15 монохроматикалық үшбұрыштардан аулақ, олар кез-келген төбені бұралмаған және бұралған бояулардан жою арқылы жасалуы мүмкін Қ16сәйкесінше.

Сондай-ақ, 3 түсті бояумен дәл 115 шеткі бояулар бар екендігі белгілі Қ14 монохроматикалық үшбұрыштардан аулақ боламыз, егер біз түстердің ауыстырылуымен ерекшеленетін шеткі бояуларды бірдей деп санасақ.

Дәлел

2 түсті корпус

2 түсті корпусқа арналған теореманы дәлелдеуге болады индукция қосулы р + с.[4] Анықтамадан барлығы үшін екені түсінікті n, R(n, 2) = R(2, n) = n. Бұл индукцияны бастайды. Біз мұны дәлелдейміз R(р, с) оған нақты байланысты табу арқылы бар. Индуктивті гипотеза бойынша R(р − 1, с) және R(р, с − 1) бар.

Лемма 1. R(р, с) ≤ R(р − 1, с) + R(р, с − 1):

Дәлел. Толық графикті қарастырыңыз R(р − 1, с) + R(р, с − 1) шеттері екі түске боялған төбелер. Шыңды таңдаңыз v графиктен және қалған шыңдарды екіге бөліңіз жиынтықтар М және N, әр шыңға арналған w, w ішінде М егер (v, w) көк, ал w ішінде N егер (v, w) қызыл. Себебі графикте бар R(р − 1, с) + R(р, с − 1) = |М| + |N| + 1 шыңдар, бұдан да шығады |М| ≥ R(р − 1, с) немесе |N| ≥ R(р, с − 1). Бұрынғы жағдайда, егер М қызыл бар Қс содан кейін бастапқы график те жасалады және біз аяқтадық. Әйтпесе М көк түске ие Қр−1 солай М ∪ {v} көк түске ие Қр анықтамасы бойынша М. Соңғы жағдай ұқсас. Осылайша, шағым шындыққа сәйкес келеді және біз 2 түсті дәлелдеуді аяқтадық.

Бұл 2 түсті жағдайда, егер R(р − 1, с) және R(р, с − 1) екеуі де тең, индукциялық теңсіздікті:[5]

R(р, с) ≤ R(р − 1, с) + R(р, с − 1) − 1.

Дәлел. Айталық б = R(р − 1, с) және q = R(р, с − 1) екеуі де тең. Келіңіздер т = б + q − 1 және -дің екі түсті графигін қарастырыңыз т төбелер. Егер дәрежесі болып табылады -графиктегі шың, содан кейін, сәйкес Қол алысу леммасы, тең. Мынадай жағдай болса т тақ, жұп болуы керек . Болжам тең, М және N сәйкесінше көк және қызыл субграфтарда 1 шыңына түскен шыңдар болып табылады. Содан кейін екеуі де және тең. Сәйкес Көгілдір саңылау принципі, немесе , немесе . Бастап тең, ал тақ, бірінші теңсіздікті күшейтуге болады, сондықтан да немесе . Айталық . Сонда немесе М подографта қызыл түс бар және дәлелі толық, немесе оның көк түсі бар ол 1 шыңымен бірге көк болады . Іс ұқсас қаралады.

Қосымша түстер корпусы

Лемма 2. Егер c> 2 болса, онда R(n1, …, nв) ≤ R(n1, …, nв−2, R(nв−1, nв)).

Дәлел. Толық кестесін қарастырайық R(n1, …, nв−2, R(nв−1, nв)) шыңдары және оның шеттерін бояйды в түстер. Енді «соқырларға барыңыз» және солай жасаңыз в - 1 және в бірдей түсті. Осылайша график қазір (в - 1) -түсті. Анықтамасына байланысты R(n1, …, nв−2, R(nв−1, nв)), мұндай графикте а Қnмен монохроматикалық түсті мен шамамен 1 for менв - 2 немесе а ҚR(nв − 1, nв)- бұлыңғыр түске боялған. Бұрынғы жағдайда біз аяқтадық. Соңғы жағдайда біз қайтадан көру қабілетімізді қалпына келтіреміз және анықтамасынан көреміз R(nв−1, nв) бізде (в - 1) -монохромды Қnв−1 немесе а в-монохромды Қnв. Екі жағдайда да дәлелдеме толық.

Лемма 1 кез келген екенін білдіреді R (r, s) ақырлы. Лемма 2-дегі теңсіздіктің оң жағы Рэмси нөмірін өрнектейді в Ramsey сандары бойынша түстер азырақ түстерге арналған. Сондықтан кез-келген R(n1, …, nв) түстердің кез келген саны үшін ақырлы. Бұл теореманы дәлелдейді.

Рэмси сандары

Сандар R(р, с) Рэмси теоремасында (және олардың екі түстен артық кеңеюі) Рэмси сандары белгілі. Рэмси нөмірі, R(м, n), қонақтардың минималды санын сұрайтын партиялық мәселенің шешімін береді, R(м, n), мұны ең болмағанда шақыру керек м бір-бірін немесе кем дегенде білетін болады n бір-бірін танымайтын болады. Графикалық теорияның тілінде Рэмси саны - шыңдардың ең аз саны, v = R(м, n), барлық бағытталмаған қарапайым графиктер v, тапсырыс кликасын қамтуы керек м, немесе тәуелсіз тәртіп жиынтығы n. Рэмси теоремасында мұндай санның барлығы үшін бар екендігі айтылған м және n.

Симметрия бойынша бұл шындық R(м, n) = R(n, м). Үшін жоғарғы шекара R(р, с) теореманы дәлелдеуден шығаруға болады, ал басқа аргументтер төменгі шектерді береді. (Бірінші экспоненциалды төменгі шек алынған Paul Erdős пайдаланып ықтималдық әдіс.) Алайда, ең төменгі төменгі шектер мен ең жоғарғы шектер арасында үлкен алшақтық бар. Сандар өте аз р және с ол үшін біз нақты мәнін білеміз R(р, с).

Төменгі шекараны есептеу L үшін R(р, с) әдетте графиктің көк / қызыл бояуын көрсетуді қажет етеді ҚL−1 көк түссіз Қр подография және қызыл түс жоқ Қс подограф. Мұндай қарсы мысал а деп аталады Рэмси графигі. Брендан Маккей белгілі Рэмси графиктерінің тізімін жүргізеді.[6] Жоғарғы шектерді орнату едәуір қиынға соғады: қарсы мысалдың болмауын растау үшін немесе оның болмауына математикалық дәлел келтіру үшін барлық мүмкін бояуларды тексеру керек.

Есептеудің күрделілігі

Ердо бізден әлдеқайда күшті, Жерге қонып, оның құнын талап ететін бөтен күшті елестетуді сұрайды R(5, 5) немесе олар біздің планетамызды құртады. Бұл жағдайда біз барлық компьютерлерімізді және барлық математиктерімізді маршалға айналдырып, мәнін табуға тырысуымыз керек дейді ол. Оның орнына олар сұрайды делік R(6, 6). Бұл жағдайда біз келімсектерді жоюға тырысуымыз керек деп санайды.

Компьютердің күрделі бағдарламасы олардың барлығын жою үшін барлық бояғыштарды жеке қараудың қажеті жоқ; дегенмен, бұл қолданыстағы бағдарламалық жасақтаманы тек кішігірім өлшемдермен басқара алатын өте қиын есептеулер. Әрбір толық граф Қn бар 1/2n(n − 1) жиектері, сондықтан барлығы болады вn(n − 1)/2 іздеуге арналған графиктер (үшін в түстер) егер қатал күш қолданылса.[8] Сондықтан барлық мүмкін графиктерді іздеудің күрделілігі (арқылы қатал күш ) болып табылады O (вn2) үшін в бояғыштар және ең көп дегенде n түйіндер.

Жағдайдың жақсаруы екіталай кванттық компьютерлер. Ең танымал алгоритм[дәйексөз қажет ] тек квадраттық жылдамдықты көрсетеді (м.ғ.к.) Гровердің алгоритмі ) классикалық компьютерлерге қатысты есептеу уақыты әлі де экспоненциалды түстер санында.[9]

Белгілі құндылықтар

Жоғарыда сипатталғандай, R(3, 3) = 6. Мұны дәлелдеу оңай R(4, 2) = 4, және, жалпы, сол R(с, 2) = с барлығына с: график с − 1 барлық жиектері қызыл түске боялған түйіндер қарсы мысал ретінде қызмет етеді және оны дәлелдейді R(с, 2) ≥ с; графикалық бояулар арасында с түйіндер, қызыл түске боялған барлық жиектері бар с-түйін қызыл субография, және барлық басқа бояғыштар а 2-түсін көк подографы (яғни көк жиегімен байланысқан жұп түйін).

Индукциялық теңсіздіктерді қолдана отырып, мынадай қорытынды жасауға болады R(4, 3) ≤ R(4, 2) + R(3, 3) − 1 = 9, демек R(4, 4) ≤ R(4, 3) + R(3, 4) ≤ 18. Тек екеуі бар (4, 4, 16) графиктер (яғни 2- толық графиканың түсі 16 жоқ түйіндер 4-түйін қызыл немесе көк толық субографиялар) арасында 6.4 × 1022 әр түрлі 2-түстер 16-түйін графиктері және тек біреуі (4, 4, 17) график ( Пейли графигі тәртіп 17) арасында 2.46 × 1026 бояғыштар.[6] (Мұны Эванс, Пулхам және Шихан 1979 жылы дәлелдеген.) Бұдан шығады R(4, 4) = 18.

Бұл факт R(4, 5) = 25 алғаш рет Брендан Маккей және Станислав Радзишовский 1995 ж.[10]

Нақты мәні R(5, 5) арасында жататыны белгілі болғанымен, белгісіз 43 (Джеффри Экзу (1989)[11]) және 48 (Angeltveit and McKay (2017))[12]) (қоса).

1997 жылы McKay, Radziszowski және Exoo компьютерлердің көмегімен графиканы құру әдістерін қолданды. R(5, 5) = 43. Олар дәл 656 құра алды (5, 5, 42) әр түрлі маршруттар арқылы бір графикалық жиынтыққа түсетін графиктер. 656 графиктің ешқайсысын а-ға дейін кеңейтуге болмайды (5, 5, 43) график.[13]

Үшін R(р, с) бірге р, с > 5, тек әлсіз шектер ғана қол жетімді. Үшін төменгі шекаралар R(6, 6) және R(8, 8) сәйкесінше 1965 және 1972 жылдардан бері жетілдірілмеген.[3]

R(р, с) бірге р, с ≤ 10 төмендегі кестеде көрсетілген. Нақты белгі белгісіз жерде кестеде ең жақсы белгілі шектер көрсетілген. R(р, с) бірге р, с < 3 арқылы беріледі R(1, с) = 1 және R(2, с) = с барлық мәндері үшін с.

Ramsey нөмірін зерттеуді дамыту бойынша стандартты сауалнама болып табылады Динамикалық шолу 1 туралы Комбинаториканың электронды журналы, арқылы Станислав Радзишовский, ол мезгіл-мезгіл жаңарып отырады.[3] Егер басқаша көрсетілмеген болса, төмендегі кестедегі жазбалар 2017 жылғы наурыздағы басылымнан алынды. (Бастап диагональ бойынша тривиальды симметрия бар екенін ескеріңіз R(р, с) = R(с, р).)

Рэмси сандарына арналған мәндер / белгілі шектер R(р, с) (жүйелі A212954 ішінде OEIS )
с
р
12345678910
11111111111
22345678910
369141823283640–42
41825[10]36–4149–6159[14]–8473–11592–149
543–4858–8780–143101–216133–316149[14]–442
6102–165115[14]–298134[14]–495183–780204–1171
7205–540217–1031252–1713292–2826
8282–1870329–3583343–6090
9565–6588581–12677
10798–23556

Асимптотика

Теңсіздік R(р, с) ≤ R(р − 1, с) + R(р, с − 1) дәлелдеу үшін индуктивті түрде қолданылуы мүмкін

Атап айтқанда, бұл нәтиже Ердо және Секерес, қашан екенін білдіреді р = с,

Экспоненциалды төменгі шекара,

1947 жылы Эрдоус берді және оның ықтималдық әдісін енгізуіне ықпал етті. Бұл екі шекара арасында үлкен алшақтық бар екені анық: мысалы, үшін с = 10, бұл береді 101 ≤ R(10, 10) ≤ 48620. Осыған қарамастан, екі деңгейдің де экспоненциалды өсу факторлары бүгінгі күнге дейін жетілдірілмеген және әлі де бар 4 және 2 сәйкесінше. Экспоненциалды төменгі шекараны шығаратын белгілі бір құрылыс жоқ. Диагональды Рэмси сандарының ең жақсы белгілі төменгі және жоғарғы шектері қазірде тұр

байланысты Спенсер және Конлон сәйкесінше.

Диагональдан тыс Рэмси сандары үшін R(3, т), олардың тәртіп екендігі белгілі ; мұны мүмкін болатын ең кіші деп айтуға болады тәуелсіздік нөмірі ан n-текс үшбұрышсыз граф болып табылады

Үшін жоғарғы шекара R(3, т) арқылы беріледі Ажтай, Комлос, және Семереди, төменгі шекара бастапқыда алынған Ким және оны Гриффитс жақсартты, Моррис, Fiz Pontiveros және Бохман және Кеваш, үшбұрышсыз процесті талдау арқылы. Жалпы, диагональдан тыс Рамзи сандары үшін, R(с, т), бірге с бекітілген және т өсіп келе жатқан, ең жақсы белгілі шектер

Бохман мен Кеваштың арқасында және Ажтай, Комлос және Семереди сәйкесінше.

Теореманың кеңейтілуі

Шексіз графиктер

Одан әрі нәтиже, сонымен қатар әдетте деп аталады Рэмси теоремасы, шексіз графиктерге қолданылады. Шектеулі графиктер талқыланатын жағдайда оны көбінесе «Шексіз Рамзи теоремасы» деп атайды. Ақырлы графиктен шексіз графикке ауысқанда графиктің кескіндемелік кескіндемесімен қамтамасыз етілетін интуиция азайғандықтан, бұл саладағы теоремалар әдетте теориялық терминология.[15]

Теорема. Келіңіздер X элементтерінің шексіз жиынтығы және түсі болуы керек X(n) (ішкі топтар X өлшемі n) в әр түрлі түстер. Сонда кейбір шексіз ішкі жиын бар М туралы X мөлшері n ішкі жиындар М барлығының түсі бірдей.

Дәлел: Дәлел индукция бойынша n, ішкі жиындардың мөлшері. Үшін n = 1, егер сіз шексіз жиынды шекті жиынға бөлсеңіз, онда олардың біреуі шексіз деуге тең. Бұл айқын. Теореманы ақиқат деп есептесек nр, біз оны дәлелдейміз n = р + 1. берілген в-түсті (р + 1) -ның ішкі жиындары X, рұқсат етіңіз а0 элементі болу X және рұқсат етіңіз Y = X \ {а0}. Содан кейін а в-түсті бояу р-элементтің ішкі жиындары Y, жай қосу арқылы а0 әрқайсысына р-элемент жиыны (алу үшін (р + 1) -элемент жиыны X). Индукциялық гипотеза бойынша шексіз ішкі жиын бар Y1 туралы Y осылай әрқайсысы р-элемент ішкі жиыны Y1 индукцияланған бояуда бірдей түске боялған. Осылайша элемент бар а0 және шексіз ішкі жиын Y1 барлық (р + 1) -ның ішкі жиындары X тұратын а0 және р элементтері Y1 бірдей түске ие Сол дәлел бойынша элемент бар а1 жылы Y1 және шексіз ішкі жиын Y2 туралы Y1 бірдей қасиеттерге ие. Индуктивті түрде біз реттілікті аламыз {а0, а1, а2,…} Әрқайсысының түсі (р + 1) -элемент жиыны (амен(1), амен(2), …, амен(р + 1)) бірге мен(1) < мен(2) < ... < мен(р + 1) тек мәніне байланысты мен(1). Сонымен, шексіз көптеген мәндер бар мен(n) бұл түс бірдей болатындай етіп Оларды алыңыз амен(n)алу үшін қажетті монохроматикалық жиынтығы.

Рамсидің графиктерге арналған теоремасының күшті, бірақ теңдестірілмеген шексіз түрі, Эрдис-Душник-Миллер теоремасы, әрбір шексіз графикте а шексіз тәуелсіз жиынтық немесе сол сияқты шексіз клика түпкілікті бастапқы график ретінде.[16]

Шексіз нұсқасы ақырғы мағынаны білдіреді

Рэмси теоремасын шексіз нұсқадан а-ға шығаруға болады қайшылықпен дәлелдеу. Соңғы Рамзи теоремасы жалған болсын делік. Онда бүтін сандар бар в, n, Т әрбір бүтін сан үшін к, бар a в-түсіну монохроматтық өлшемдер жиынтығысыз Т. Келіңіздер Cк белгілеу в-түстер монохроматтық өлшемдер жиынтығысыз Т.

Кез келген үшін к, боялуды шектеу Cк+1 дейін (құрамында барлық жиынтықтардың түсін елемеу арқылы к + 1) бояғыш болып табылады Cк. Анықтаңыз бояғыштар болу Cк олар боялуға шектеулер болып табылады Cк+1. Бастап Cк+1 бос емес, бос емес .

Сол сияқты, кез-келген бояуды шектеу ішінде анықтауға мүмкіндік береді барлық осындай шектеулер жиынтығы ретінде, бос емес жиынтық. Осылай жалғастыра отырып, анықтаңыз барлық сандар үшін м, к.

Енді кез-келген бүтін сан үшін к, , және әрбір жиын бос емес. Сонымен қатар, Cк ретінде шектеулі . Бұдан шығатыны, осы жиындардың барлығының қиылысы бос емес және рұқсат етіледі . Содан кейін әр бояу Д.к түске боялуды шектеу болып табылады Д.к+1. Сондықтан, бояуды шектеусіз Д.к түске дейін Д.к+1, және осылай жалғастыра отырып, бір бояғышты салады кез-келген монохроматикалық жиынтықсыз Т. Бұл шексіз Рамзи теоремасына қайшы келеді.

Егер қолайлы топологиялық көзқарас қабылданса, бұл дәлел стандартқа айналады ықшамдылық теореманың шексіз нұсқасының ақырғы нұсқасын білдіретіндігін көрсету.[17]

Гиперографтар

Теореманы кеңейтуге де болады гиперографтар. Ан м-гипограф - бұл «жиектері» жиындар болатын граф м шыңдар - қалыпты графикте жиек 2 төбенің жиыны болып табылады. Рэмсидің гиперографтарға арналған теоремасының толық тұжырымы кез-келген бүтін сандарға арналған м және вжәне кез келген бүтін сандар n1, …, nв, бүтін сан бар R(n1, …, nв;в, м) егер гипереджалар бүтін болса м- тапсырыс гиперографиясы R(n1, …, nв;в, м) -мен боялған в әр түрлі түстер, содан кейін кейбіреулер үшін мен 1 мен аралығында в, гиперграфта толық ішкі жазба болуы керекм- тапсырыс гиперографиясы nмен олардың гипереджесі түстерге сәйкес келеді мен. Бұл теорема әдетте индукция арқылы дәлелденеді м, графиктің 'гиперемиясы'. Дәлелдеу үшін негізгі жағдай болып табылады м = 2, бұл дәл жоғарыдағы теорема.

Бағытталған графиктер

Сонымен қатар, Рэмси сандарын анықтауға болады бағытталған графиктер; бұлар енгізілген П.Эрдос және Л.Мозер (1964 ). Келіңіздер R(n) ең кіші сан Q жеке бағытталған доғалармен («турнир» деп те аталады) және ≥ кез келген толық графQ түйіндерде ациклик бар (оны «өтпелі» деп те атайды) n-түйінді субтурнир.

Бұл (жоғарыда) аталғанның бағытталған-графикалық аналогы R(nn; 2), ең кіші сан З толық жиектерінің кез-келген 2-бояуы болатындай етіп БҰҰбағытталған графЗ n түйіндерінде монохроматикалық толық график бар. (Екі мүмкін доғаның бағытталған аналогы түстер екеуі бағыттар доғалардан, «монохроматтық» аналогы - «барлық доға жебелері бірдей бағытта»; яғни, «ациклдық».)

Бізде бар R(0) = 0, R(1) = 1, R(2) = 2, R(3) = 4, R(4) = 8, R(5) = 14, R(6) = 28 және 32 ≤R(7) ≤ 54.[18]

Таңдау аксиомасымен байланыс

Жылы кері математика, шексіз графиктерге арналған Рамси теоремасының нұсқасы арасында дәлелдеу күшінде айтарлықтай айырмашылық бар (жағдай n = 2) және шексіз мультиграфтар үшін (жағдай n ≥ 3). Теореманың мультиграфтық нұсқасы күшіне тең арифметикалық түсіну аксиомасы, оны ACA ішкі жүйесінің бөлігі етеді0 туралы екінші ретті арифметика, бірі үлкен бес ішкі жүйе кері математикада. Керісінше, теоремасы бойынша Дэвид Ситапун, теореманың графикалық нұсқасы ACA-ға қарағанда әлсіз0, және (Seetapun нәтижесін басқалармен біріктіру) ол үлкен бес ішкі жүйенің біріне енбейді.[19] Аяқталды ZF дегенмен, графикалық нұсқасы классикалыққа балама Кениг леммасы.[20]

Сондай-ақ қараңыз

Ескертулер

  1. ^ Кейбір авторлар мәндерді біреуден үлкен деп шектейді, мысалы (Brualdi 2010 ) және (Харари 1972 ж ), осылайша, шеттері жоқ графикті жиекпен бояуды талқылаудан аулақ болыңыз, ал басқалары теореманың тұжырымдамасын талап етіп қайта өзгертеді, қарапайым график, не р-клик немесе ан с-тәуелсіз жиынтық, қараңыз (Жалпы 2008 жыл ) немесе (Эрдис және Секерес 1935 ж ). Бұл формада графиктерді бір шыңмен қарастыру табиғи болып табылады.
  2. ^ графиктің автоморфизміне дейін
  3. ^ а б в Радзишовский, Станислав (2011). «Кішкентай Рэмси сандары». Динамикалық сауалнамалар. Комбинаториканың электронды журналы. дои:10.37236/21.
  4. ^ До, Норман (2006). «Партиялық мәселелер және Рэмси теориясы» (PDF). Австр. Математика. Soc. Газет. 33 (5): 306–312.
  5. ^ «Партиялық таныстар».
  6. ^ а б «Рэмси Графтары».
  7. ^ Джоэл Х.Спенсер (1994), Ықтималдық әдісі бойынша он дәріс, СИАМ, б.4, ISBN  978-0-89871-325-1
  8. ^ 2.6 Математикадан алынған Рэмси теориясы
  9. ^ Ванг, Хефенг (2016). «Кванттық компьютерде Рамси сандарын анықтау». Физикалық шолу A. 93 (3): 032301. arXiv:1510.01884. Бибкод:2016PhRvA..93c2301W. дои:10.1103 / PhysRevA.93.032301.
  10. ^ а б Брендан Д. Маккей, Станислав П. Радзишсовский (мамыр 1995). "R(4,5) = 25" (PDF). Графикалық теория журналы. 19 (3): 309–322. дои:10.1002 / jgt.3190190304.
  11. ^ Экзоо, Джеффри (1989 ж. Наурыз). «Үшін төменгі шекара R(5, 5)". Графикалық теория журналы. 13 (1): 97–98. дои:10.1002 / jgt.3190130113.
  12. ^ Vigleik Angeltveit; Брендан Маккей (2017). «". arXiv:1703.08768v2 [математика ].
  13. ^ Брендан Д. Маккей, Станислав П. Радзишовский (1997). «Тұлғалар мен Рэмси сандарын санақ бойынша есептеу» (PDF). Комбинаторлық теория журналы. 69 (2): 193–209. дои:10.1006 / jctb.1996.1741.
  14. ^ а б в г. Экзоо, Джеффри; Татаревич, Милош (2015). «Рамзидің 28 классикалық нөміріне арналған жаңа төменгі шектер». Комбинаториканың электронды журналы. 22 (3): 3. arXiv:1504.02403. Бибкод:2015arXiv150402403E. дои:10.37236/5254.
  15. ^ Мартин Гулд. «Рэмси теориясы» (PDF).
  16. ^ Душник, Бен; Миллер, Е.В. (1941). «Ішінара тапсырыс берілген жиынтықтар». Американдық математика журналы. 63 (3): 600–610. дои:10.2307/2371374. hdl:10338.dmlcz / 100377. JSTOR  2371374. МЫРЗА  0004862.. Әсіресе 5.22 және 5.23 теоремаларын қараңыз.
  17. ^ Диестель, Рейнхард (2010). «8-тарау, шексіз графиктер». Графикалық теория (4 басылым). Гейдельберг: Шпрингер-Верлаг. 209–2010 бб. ISBN  978-3-662-53621-6.
  18. ^ Смит, Уоррен Д .; Экзоо, Джеофф, №27 басқатырғышқа ішінара жауап: Рамзи тәрізді шама, алынды 2020-06-02
  19. ^ Хиршфельдт, Денис Р. (2014). Ақиқатты кесу. Сингапур Ұлттық университеті, Математика ғылымдары институтының дәрістер сериясы. 28. Әлемдік ғылыми.
  20. ^ Лолли, Габриеле (1977 ж. Қазан). «Рэмси теоремасы және таңдау аксиомасы туралы». Нотр-Дам журналы формальды логика журналы. 18 (4): 599–601. дои:10.1305 / ndjfl / 1093888126. ISSN  0029-4527.

Әдебиеттер тізімі

Сыртқы сілтемелер