Су „Св. Климент Охридски

ФМИ

по

2011г.

Родителите му са Артър Стенли Ремзи и Агнес Мари Уилсън. Артър Ремзи е бил президент на колежа „Магдалена” в Кеймбридж и преподавател по математика в същия колеж. Франк е бил най-големия от четирите деца в семейството. Имал е един брат и две сестри. Брат му става Кентърберийски архиепископ.

Ремзи постъпва в колежа „Уинчестър” през 1915г. и там той спечелва стипендия за колежа „Тринити” в Кеймбридж. През 1920г., след завършването си в Уинчестър, постъпва в колежа Тринити да учи математика. В Кеймбридж Ремзи става стипендиант в по-горните курсове през 1921г. и завършва с титлата Wrangler(студент завършващ с отличие по математика в Кеймбриджския университет) след Mathematical Tripos(изпит за получаване на научна степен в Кеймбридж) през 1923.

След завършването си Ремзи е във Виена за известно време и се връща в Кеймбридж след като е избран за член на научно дружество на King's College Cambridge (някои университети в Кеймбридж) през 1924. Това е изключение, като се има в предвид, че Ремзи е едва втория човек, който някога е избиран за член на King's College, без да е бил преди това студент там.

През 1925г. Ремзи се жени за Летисия Бейкър, с която имат две дъщери. Следващата година той е назначен за университетски преподавател по математика и по-късно става ръководител на Катедрата по Математика в King's College. Кариерата му е била кратка, защото за нещастие Ремзи умира в началото на 1930г – на 19 януари в Лондон.

Въпреки краткото време, през което той е изнасял лекции в Кеймбридж, си е спечелил славата на изключителен преподавател.

Макар, че Ремзи е работил основно в областта на математиката, той е творил в забележително широк кръг области за краткото време на своя живот. В областта на математиката, Ремзи поставя основите на нова математическа теория, сега наречена “Теорията на Ремзи”, той пише и за основите на икономиката (“Статия за теорията на облагането с данъци” и “Математическа теория за спестяванията”) и философията (“Факти и твърдения” и “Общоизвестното за правото и фактите”).

2. Теорема на Ремзи:

За два върха на графа че казваме, че са съседни, ако са съединени с ребро. За две ребра на графа ще казваме, че са съседни, ако имат общ връх.

Множество от върхове на графа, всеки два от които съседни, се нарича клика; в случай че броя на върховете от кликата е 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 г.

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 = 2 доказателството е тривиално.

Нека p, q > 2. използваме теоремата на Ремзи и факта, че

+ = () = =

И положим k = p + q − 3 и l = q − 1

Казваме, че е зададено 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) не е известно.

(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-клика при оцветяването . Ще разгледаме двата случая отделно.

N