СУ „Св. Климент Охридски”
ФМИ
КУРСОВ ПРОЕКТ
по
Числа на Ремзи
2011г.
1. Биографична справка:
Франк Плъмптън Ремзи е роден на 22 февруари 1903г. в Кеймбридж, Англия.
Родителите му са Артър Стенли Ремзи и Агнес Мари Уилсън. Артър Ремзи е бил президент на колежа „Магдалена” в Кеймбридж и преподавател по математика в същия колеж. Франк е бил най-големия от четирите деца в семейството. Имал е един брат и две сестри. Брат му става Кентърберийски архиепископ.
Ремзи постъпва в колежа „Уинчестър” през 1915г. и там той спечелва стипендия за колежа „Тринити” в Кеймбридж. През 1920г., след завършването си в Уинчестър, постъпва в колежа Тринити да учи математика. В Кеймбридж Ремзи става стипендиант в по-горните курсове през 1921г. и завършва с титлата Wrangler(студент завършващ с отличие по математика в Кеймбриджския университет) след Mathematical Tripos(изпит за получаване на научна степен в Кеймбридж) през 1923.
След завършването си Ремзи е във Виена за известно време и се връща в Кеймбридж след като е избран за член на научно дружество на King's College Cambridge (някои университети в Кеймбридж) през 1924. Това е изключение, като се има в предвид, че Ремзи е едва втория човек, който някога е избиран за член на King's College, без да е бил преди това студент там.
През 1925г. Ремзи се жени за Летисия Бейкър, с която имат две дъщери. Следващата година той е назначен за университетски преподавател по математика и по-късно става ръководител на Катедрата по Математика в King's College. Кариерата му е била кратка, защото за нещастие Ремзи умира в началото на 1930г – на 19 януари в Лондон.
Въпреки краткото време, през което той е изнасял лекции в Кеймбридж, си е спечелил славата на изключителен преподавател.
Макар, че Ремзи е работил основно в областта на математиката, той е творил в забележително широк кръг области за краткото време на своя живот. В областта на математиката, Ремзи поставя основите на нова математическа теория, сега наречена “Теорията на Ремзи”, той пише и за основите на икономиката (“Статия за теорията на облагането с данъци” и “Математическа теория за спестяванията”) и философията (“Факти и твърдения” и “Общоизвестното за правото и фактите”).
2. Теорема на Ремзи:
2.1. Общи сведения от теория на графите:
Под граф(или по-точно обикновен граф) ще разбираме схемата на познансртвата на някаква компания. По такъв начин на всяка компания се съпоставя гра, който я определя напълно. Точките, които изобразяват членовете на компанията, се наричат върхове на графа, а линиите, изобразяващи познанствата, се наричат ребра на графа.
За два върха на графа че казваме, че са съседни, ако са съединени с ребро. За две ребра на графа ще казваме, че са съседни, ако имат общ връх.
Множество от върхове на графа, всеки два от които съседни, се нарича клика; в случай че броя на върховете от кликата е s, понякога тя се нарича още s-клика. Съгласно тази дефиниция 2-кликата е двойка съседни върхове и поради това се отъждествява често с реброто, което съединява тези върхове. 3-кликата е тройка върхове, всеки два от които са съседни. Естествено 3-кликата наричаме триъгълник. 4-кликите се наричат тетраедри.
Ако в графа G има s-клика, но няма (s+1)-клика, тогава казваме, че G има кликово число s и записваме cl(G) = s.
Граф, в който многеството от всички върхове е клика, се нарича пълен и се означава с K, ако n е броят на върховете му.
2.2 Теорема на Рамзи и числа на Рамзи:
Ще направим кратко резюме на някои от доказаните в настоящия параграф резултати:
(3,3). Числото 6 е най-малкото n, за което при всяко 2-оцветяване на ребрата на K има черна 3-клика или бяла 3-клика.
(3,4). Числото 9 е най-малкото n, за което при всяко 2-оцветяване на ребрата на K има черна 3-клика или бяла 4-клика.
(3,5). Числото 14 е най-малкото n, за което при всяко 2-оцветяване на ребрата на K има черна 3-клика или бяла 5-клика.
(4,5). Числото 18 е най-малкото n, за което при всяко 2-оцветяване на ребрата на K има черна 4-клика или бяла 4-клика.
Към този списък ще прибавим и следните очевидни твърдения:
(2, q). Числото q е най-малкото n, за което при всяко 2-оцветяване на ребрата на K има черна 2-клика или бяла q-клика. (q2).
Разбира се една клика наричаме едноцветна ако всичките и ребра имат един и същи цвят.
Абсолютно естествен е и въпросът, дали за всякакви цели p и q, p2,q2, има такова n, че при всяко 2-оцветяване на ребрата на K непременно да има черна p-клика или бяла q-клика.
Засега отговорът на този върпос ни е известен само в изброените горе случаи.
Положителен отговор на този въпрос за всякакви p и q е дал известният английски математик и логик Франк Пенистън Рамзи (22.1.1903 – 19.1.1930). Рамзи е работил в университета в Кембридж. Основните му трудове са по комбинаторика и логика, а също така и по теория на алгебричните кризи. В трудовете му са получили по-нататъшно развитие идеите на Бертранд Ръсел и Джон Уайтхед от тяхната прочута книга “Принципи на Математиката”. Интересуващата ни работа на Рамзи излиза от печат през 1930 г. ,след неговата смърт.
Теорема 1 (Рамзи): Нека p и q са естествени числа, p2, q2. Съществува такова n, че при всяко 2-оцветяване на ребрата на K има черна p-клика или бяла q-клика.
Най-малкото n с това свойство в чест на Рамзи, се нарича число на Рамзи и се означава твърде често, но не винаги с R(p, q). Очевидно е, че R(q, p).
Вече знаем, че R (3, 3) = 6, R (3, 4) = 9, R (3, 5) = 14, R (4, 4) = 18
От разгледаните и доказани теореми вече са ни известни неравенствата
R (3, 3) 6, R (3, 4) 9, R (3, 5) 14, R(4, 4) 18, тъй като те се основават на една и съша идея, която дава възможност да се докаже твърдението на теорема 6 (за p и q) при предположение, че то е в сила за (p-1,q), (p,q-1). По този начин се доказва теорема 6 и се установява следната:
Теорема 2: Ако p2 и q2, тогава
(1) R(p,q) R(p-1,q)+R(p,q-1).
Забележка. Под R(1,q) е естествено да разбираме числото 1.
Теорема 2 е явно формулирана и доказана от Ердьош и Секереш през 1935 г.
Доказателство: Избираме произволен вртх v на графа K, където
N = R(p −1, q) + R(p, q − 1). Нека c е произволно оцветяване на K. Тогава във v имаме R(p −1, q) + R(p, q − 1) − 1 ребра,от които или R(p − 1, q) са черни или R(p, q − 1)са бели. Без загуба на общност можем да кажем, че имаме R(p − 1, q) върха във v свързани с черни ребра. Тези върхове принадлежат на K. Така получихме, че за всяко оцветяване c имаме или бели q-клики или черни (p-1)-клики в този K граф. Това завършва и доказателството, тъй като Kсе получава като дабавим v към K
Едно уточнение на Теорема 2 се дава от следната теорема, доказана от Грийнууд и Глисън:
Теорема 3: Ако
(2) R(p-1,q) и R(p,q-1) са четни,
тогава
(3) R(p,q)
От теорема 2 и 3 следва, чеR(3,6) 19. Споменатият вече Г.Кери доказва през 1964 г., че R(3,6) = 18.
Освен споменатите вече числа на Рамзи известно е още само едно R(3,7) = 23. То бе намерено от американските математици Грейвър и Якел през 1968 г. Тяхното доказателство е извънредно дълго.
И така, освен тривиалните R(1,q) и R(2,q) известни са общо само 6 числа на Рамзи. Ние тук получихме 4 от тях. Откриването на всяко друго число на Рамзи би било забележително научно постижение.
В заключение отбелязваме следното следствие от Теорема 2:
Следствие 1: За произволни цели p и q, p,q1 е валидно неравенството
(4) R(p,q) .
Доказателство: индукция по p + q
За p, q = 2 доказателството е тривиално.
Нека p, q > 2. използваме теоремата на Ремзи и факта, че
+ = () = =
И положим k = p + q − 3 и l = q − 1
2.3 Теорема на Pамзи за оцветяване на r-Кликите на граф:
2.3.1. 2-оцветяване за 3-кликите на К:
Досега разлгедахме два вида оцветянания в граф – оцветявания на върховете и оцветявания на ребрата. Сега ще изучаваме задачи за оцветявания на 3-кликите. За да си представиме геометрично нещата, към основните елементи на графа – неговите върхове и ребра, ще прибавим още и „пълните триъгълници”. А именно, ако [v,v,v] е произволна 3-клика в графа G, ще присъединим към графа и „пълния триъгълник” с тези върхове. В така попълнения граф ще оцветяваме триъгълниците и за да не се смесва този нов тип оцветяване със стария, ще оцветяваме само вътрешностите на триъгълниците, но не и техните върхове и ребра. Всичко това се отнася към геометричната интерпретация на новия тип оцветяване, което сега ще въведем чрез следната дефиниция:
Казваме, че е зададено 2-оцветяване на 3-кликите на един граф G, ако на всяка негова 3-клика е съпоставен някакъв пределен цвят – един от два предварително взети цвята, например черен и бял.
Когато разглеждахме оцветявания на ребрата, една клика М нарекохме едноцветна, щом ребрата, съединяващи върховете на М имат един и същи цвят. При новия тип оцветяване такава дефиниция би била безмислена, тъй като ребрата въобще не са оцветени. Но новата дефиниция, която ще даден, е също така естествена във възникналата ситуация.
Ако е зададено 2-оцветяване на 3-кликите на G, ще казваме, че една m-клика М е едноцветна при това оцветяване, щом всички 3-клики с върхове в М имат един и същи цвят.
Разполагайки с тези дефиниции, можем да разгледаме задачи аналогични на онези от предишния параграф. Теоремата, която съответства на твърдението за оцветяване на ребрата на К е следната:
Теорема 1: При всяко 2-оцветяване на 3-кликите на пълния граф с 19 върха К непременно има едноцветна 4-клика.
Доказателство: Да вземем един връх v на К и да го отстраним от този граф. Остава пълен граф с 18 върха К.
Да вземем някакво 2-оцветяване на 3-кликите на К. То автоматично индуцира 2-оцветяване на ребрата на К: всяко ребро [v, v] на К ще оцветим в цвета на 3-кликата [v, v, v].
От теорема 5, §1 знаем, че относно индуцираното оцветяване на ребрата на К в този граф може да се намери едноцветна 4-клика. Да означим върховете и с v, v, v, v4, a самата нея с М.
От дефиницията на индуцираното оцветяване следва, че триъгълниците [v, v, vj] имато един и съши цвят – например черен. Ако някоя 3-клика на М е черна в даденото оцветяване на 3-кликите на К, тогава като присъединим към нея върха v, очевидно ще получим едноцветна 4-клика (черна) в даденото оцветяване на 3-кликите. В този случай твърдението на теоремата е доказано.
Остава за разглеждане случая, когато всяка 3-клика на М е бяла в даденото озветяване на 3-кликите на К. Но в такъв случай М е едноцветна 4-клика (бяла) в това оцветяване.
Теорема 1 е доказана.
Най-малкото n, за което при всяко 2-оцветяване на 3-кликите на K сигурно има едноцветна 4-клика, се означава с R(4, 4) и пак се нарича число на Рамзи.
От теорема 1 следва, че:
(1) R(4,4) 19.
Ж. Kалбфлейш през 1968 г. е доказал, че
12 R(4,4) 17,
но чилсото R(4,4) не е известно.
2.3.2. 2-оцветяване на 3-кликите на K
Нека p и q са цели числа, p3, q3. Ще формулираме следното твърдение:
(p, q). Има такова n, че при всяко 2-оцветяване на 3-кликите на K в черен и бял цвят има черна p-клика или бяла q-клика.
За n ще казваме, че удовлетворява (p, q).
Теорема 1 показва, че твърдението (4, 4) е вярно.
Очевидно е, че твърдението (p, q) е вярно единствено ако твърдението (q, p) e вярно.
Ако за някои p, q твърдението (p, q) e вярно, най-малкото n, което го удовлетворява, ще означаваме с R(p, q); така дефинираното число се нарича число на Рамзи. То съществува тогава и само тогава, когато (p, q) е вярно.
Ясно е, че
R(p , 3) = R(3, p) = p.
Ще докажем, че R(p, q) съществува за всякакви p и q. Доказателството е индуктивно и то се опира на същата идея, както и доказателството на Теорема 1. В частност, съществено се използва, че числата R(p, q) съшествуват, т.е използва се теорема 6 от §1. Съшевременно ще докажем и следния аналог на неравенството (1) от предния пункт:
(2) R(p, q) R(R(p-1,q),R(p,q-1))+1.
Ще започнем със следното помощно предложение:
Лема 1: Ако p4 и q4 и твърденията (p-1,q), (p,q-1) са верни, тогава числото n, определено от равенството
(3) n= R (R(p-1, q),R(p, q-1) ) + 1
удовлетворява (p, q).
Доказателство: Да вземем един връх v на K и да го отстраним. Оставащия подграф ще означим с K.
Нека е едно 2-оцветяване в черно и бяло на 3-кликите на K. Трябва да докажем, че в K има при това оцветяване черна p-клика или бяла q-клика.
Ще означим с индуцираното от 2-оцветяване на ребрата на K, дефинирано по следния начин: всяко ребро [v,v] на K оцветяваме в онзи цвят, който има 3-кликата [v,v,v] при .
Да положим
а = R(p-1 ,q) и b = R(p, q-1).
Тъй като n-1 = R(a, b), то съгласно дефиницията на R(a, b), в K има или черна а-клика или бяла b-клика при оцветяването . Ще разгледаме двата случая отделно.
Нека М е черна а-клика при . Тъй като а = R (p-1, q), то М има или черна (p-1) клика, или бяла q-клика при . В последния случай, като присъединим към черната (p-1)-клика при и върха v, ще получим очевидно черна p-клика , с което доказателството завършва.
2.3.3. Обобщена теорема на Рамзи:
Нека S е множество, съдържащо N елемента, а r е естествено число. Нека T е семейството от подмножества на S, съдържащи точно по r елемента. Да разбием Т на две непресичащи се семейства и . Нека p и q са естествени числа, по-малки или равни от r. Тогава съществува минимално число n(p,q,r), зависещо само от числата p, q и r и не зависещо от множеството S, такова че за всяко N n(p,q,r) или съществува подмножество , съдържащо p елемента и такова, че всички негови подмножества с по точно r елемента влизат в семейството , или съществува подмножество , съдържащо q елемента и такова, че всички негови подмножества с по точно r елемента влизат в семейството .
Сподели с приятели: |