Су „Св. Климент Охридски” фми курсова работа по Числа на Ремзи

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. Теорема на Ремзи:

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

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

a) за тройката (p,q,1) лесно се вижда, че n(p,q,1)=p+q-1, т.е. че ако множеството S има Np+q-1 елемента, то като го разбием на две непресичащи се подмножества или в едното ще има поне p елемента, или в другото ще има поне q елемента. Ако N<p+q-1, то ясно е че S може да се разбие на две подмножества, такива че едното има по-малко от p елемента, a другото – по-малко от q елемента. По този начин n(p,q,1)=p+q-1.

б) да докажем, че n(r,q,r)=q.

Действително нека Nq. Ако семейството не е празно, то всяко r-подмножество (подмножество с точно r елемента) от може да бъде взето в качество на множеството А.

Ако семейството е празно, то всички r-подмножества се съдържат в и тогова в качеството на B може да бъде взето произволно подмножество с q елемента от цялото множество N.

в) по същия начин се доказва че n(p,r,r)=p.

В противен случей това множество от елемента съдържа подмножество от p-1 елемента, всички r-подмножества на което принадлежат на и това подмножество от p-1 елемента, което заедно с образува подмножество с p елемента в S, всичките r-подмножества, на които принадлежат на семейството - отново изискването е удовлетворено.

Аналогично се разсъждава и тогава, когато съдържа множество от елемента, всичките (r-1)-подмножества на което принадлежат на . По този начин доказахме, че n(p,q,r) съществува и , където и

Тъй като по индукционното предположение , и съществуват, то съществува и n(p,q,r) и с това теоремата на Ремзи е доказана.

Сега да преминем към доказателството на теоремата на Ердьош-Секереш:

Да вземем множеството от N точки и разгледаме семейството Т от 4-подмножества на N, т.е. от подмножествата, които съдържат точно по четири точки. Ясно е че семейството Т е еквивалентно на множеството от всички четириъгълници с върхове в N. Да разбием Т на две подсемейства – , съответстващо на множеството на изпъкналите четириъгълници и , съответстващо на множеството на вдлъбнатите четириъгълници. В този случей по теоремата на Ремзи, ако NN(n,5,4), то съществува n-ъгълник, всички четириъгълници на който принадлежат на семейството , т.е. са изпъкнали, или петоъгълник, всички четириъгълници на който принадлежат на семейството , т.е. са вдлъбнати. Втората възможност е изключена по силата на лема 1 и значи остава първата – съществува n-ъгълник, на който всички четириъгълници са изпъкнали – самият той е изпъкнал по силата на лема 2 и с това теоремата е доказана.
4.Нови по-малки граници на многоцветното число на Рамзи r_k(C₄)

Резюме: Многоцветното число на Рамзи rk (C₄)е най-малкото цяло число n, за което всяко к-оцветяване на ребрата на пълния граф Кn трябва да произведе монохроматичен 4-циклен.В [6] и [3] беше доказано,4е rk(C₄) ≥к²­ к +2 за к – 1 проста степен. Така установяваме rk(C₄) ≥к² + 2 за к нечетна проста степен.

1. 
   Въведение
   

Нека к ≥ 1 е цяло число и нека G₁,.........,Gк са графи. Многоцветното число на Рамзи r(G₁,.........,Gк) е дефинирано да е най-малкото цяло n=n(к) със свойството,че всяко к-оцветяване на ребрата на пълния граф Кn трябва да даде монохроматичен подграф на Кn изоморфен на Gi за някое i.(Тук под монохроматичен подграф се разбира подграф, при който всичките му ребра са с един и същ цвят. Когато всички графи Gi са тъждествени, обикновено съкращаваме r(G,.........,G) с rk(G). Очевидно, представата за многоцветното число на Рамзи е етествено обобщение на тази за класическото число на Рамзи r(s, t) := r(Ks,Kt).

Ще фокусираме вниманието си на специалния случай, когато Gi е 4-циклен _C4. Тук е известно,че к²­ к +2 ≤ rk(C₄)≤ к² +к +1, и горна граница в сила за всяко к ≥ 1, и долна граница в сила за всяко к – 1 проста степен. В тази забележка показваме ,че (1.1) к² + 2 ≤ rk(C₄) за к нечетна проста степен. За да извършим това, трябва първо да опишем специалния C₄ свободен граф от ред q² и размер q(q² − 1)/2, където q e нечетна проста степен. ( Припомняме си, че редът на граф е сума от върховете му, и размерът му е сума от ребрата му.)Ще покажем как да оцветим ребрата на пълния граф Кq² в q цвята, така че всеки максимален монохраматичен подграф е изоморфен на Г.

Такива оцветявания могат да бъдат също видяни като разлагания на ребрата на Кq² в изоморфни копия на Г. Очевидно, наличието на такива оцветявания означава, че rq(C₄)≥ q² + 1. После показваме,че оцветяванията на ребрата на Кq² може да бъде разширени до q оцветявания на ребрата на Кq²+1 такива,че всеки монохроматичен подграф е C₄-свободен.Това ще се докаже.

(1.1).

2. 
   Доказателства
   

Нека q е проста степен и F_q е крайно поле от q елемента.Нека множеството V = F_q × F_q . Взимаме прост граф Г с връх множеството V и ребро множество дефинирано по следния начин: два различни върха (a₁, a₂) и (b₁, b₂) са съседни тогава и само тогава, когато

(2.1) a₂ + b₂ = a₁b_1.

Използвайки тази дефиниция за съседство, степента на произволен връх (x, y) от Г може да бъде пресметнат както следва. Съседите на (x, y) са очевидно тези върхове (u, xu – y) които са различни от (x, y). Тъй като (u, xu – y) = (x, y) тогава и само тогава когато u = x и y = x²/2, всеки от q върховете от формата (x, x²/2) има точно q – 1 съседа, като всеки от останалите q² – q върха има точно q съседа. Това означава, че броят на ребрата от Г е ½(q(q − 1) + (q² − q)q) = q(q² − 1)/2.

(2.2) b₂ + c₂ = b₁c₁

c₂ + d₂ = c₁d₁

d₂ + a₂ = d₁a₁

което значи (a₁ – c₁)(b₁ – d₁) = 0. Тоест или а₁ = c₁ или b₁ = d₁, което значи че или (a₁, a₂) = (c₁, c₂) или (b₁, b₁) = (d₁, d₂), което е противоречие. Следователно Г е C₄-свободен. За да докажем второто твърдение ще определим множеството върхове от Kq² с V. Това прави Г обхващащ подграф в Kq². За всяко  є F_q, дефинираме изображение _ : V  V чрез (x, y)  (x, y + ). Очевидно _ е биекция. Сега дефинираме _(Г) като обхващащ подграф в Kq² с два различни върха (a₁, a₂ + ) и (b₁, b₂ + ) съседни тогава и само тогава, когато върховете (a₁, a₂) и (b₁, b₂) са съседни в Г. Непосредствено от дефиницията, че подграфа _(Г) е изоморфен на Г за всяко  є F_q; наистина _ е изоморфизъм.

Изискваме подграфите _(Г),  є F_q да са различни. Наистина да предположим, че два различни върха (x, y) и (u, w) са съседни и в _(Г), и в _(Г). Тогава двойките върхове {(x, y – ), (u, w – )} и {(x, y – ), (u, w – )} са ребра в Г. От (2.1) следва:

(y – ) + (w – ) = (y – ) + (w – ) = xu,

което значи че  = . Тъй като размерите на Г и Kq² са съответно q(q² − 1)/2 и q²(q² − 1)/2, получаваме деление на ребрата от Kq² като q изоморфни копия от Г. За да довършим доказателството просто избираме F_q като нашето множество цветове и оцветяваме всички ребра на _(Г) с цвета на .

Непосредствено от Теорема 1 имаме следният резултат.
Извод 1. Ако q е нечетно проста степен, то r_q(C₄)  q² + 1.
Но всъщност тази граница може да бъде малко подобрена.
Теорема 2. Ако q е нечетно проста степен, то r_q(C₄)  q² + 2.
Доказателство. Достатъчно е да се покаже,че q- оцветяване на ребрата на Кq²+1 в което няма монохроматичен C₄. Фиксираме връх v от Кq²+1 и показваме подграфът индуциран с множеството му от съседи до N. Тъй като N е изоморфен на Кq², то ние можем да оцветим q-цветните му ребра, съгласно с Теорема 1, тоест да зададем цвят  є F_q на всички ребра от N от формата {(a₁, a₂), (b₁, a₁b₁ – a₂ + 2)}. Така остава да оцветим само ребрата {v, u} за u є V (N), което става като зададем цвят  на всяко ребро {v, u} ако  е първата координата на u. Изискваме конструираното q-оцветяване на ребрата от Кq²+1 да не съдържа монохроматичен 4-циклен.

Допускаме че съществува монохромен 4-циклен, например от цвят . Очевидно v трябва да е от неговите върхове, така че означаваме последователните върхове на този цикъл с v, w, x, y. Тогава w и y имат обща първа координата , тоест w = (, w₂) и y = (, y₂). Следователно за x имаме x = (x₁, x₁ – w₂ + 2) (от съседството на x със w) и x = (x₁, x₁ – y2 + 2) (от съседството на x със y). Тъй като w₂ = y₂ достигаме до противоречието w = y.

Лесно е да се докаже, че е невъзможно да се разшири съществуващото q-оцветяване от Кq²+1 до q-оцветяване от Кq²+2 без създаването на монохроматичен 4-циклен.

2. 
   Обобщителни и заключителни забележки
   

В [1] е доказано,че r₃(C₄) = 11(виж също [4]), но това е единствения случай, в който r_к(C₄) е известно. Има, обаче по-малки граници за много малко к, които разширяват общата по-малка граница от [6] и [3], а именно r₄(C₄) ≥ 18 (подобряващ

r₃(C₄) ≥14) и r₅(C₄) ≥25(подобряващ r₅ (C₄) ≥22), виж [5].От тези два случая, теоремата ни важи за вторият и резултатът е граница, кояте е r₅(C₄) ≥27. Наистина има r₅(C₄){27, 28, 29},който е последица от резултатът в [9] и показва,че всеки граф от ред 29 и размер 81 трябва да съдържа 4-циклен.

Построението на граф Г и резултатите от тази бележка позволяват следващото обобщение:

Нека R е комутативен пръстен. За всяко цяло I, 2  i n, нека

f_i : R^2i-2R е функция, която удоволетворява

f_i(x₁,y₁,…….,x_i-1,y_i-1)=(y₁,x₁,….,y_i-1,x_i-1),
за всяко x_i, y_j  R. Определяме Г_n = Х(R; f₂,…,f_n) е граф с множество върхове V(Г_n)=Rⁿ , където различните върхове (a₁,a₂,….,a_n) и b=(b₁,b₂,…,b_n) са съседни тогава и само тогава, когато за следващите n – 1 връзки на техните координати важи:

a₂ + b₂ = f₂(a₁, b₁)

a₃ + b₃ = f₃(a₁, b₁, a₂, b₂)

... ...

Граф Г в това пояснение е с точно определен начин на построение, именно , когато n=2 R= F_q, и f₂(x₁,y₁)=x₁y₁.

5. Използвана литература:

За 2 и 3 част:

Маршал Хол – Комбинаторика, „Мир”, Москва 1970

and Combin. (Ed. B. Bollob´as), Academic Press, London (1984), 29-33.

[2] F. R. K. Chung, On triangular and cyclic Ramsey numbers with k colors, in Graphs and

Combinatorics (Ed. R. Bari and F. Harari), Springer LNM 406, Berlin (1974), 236-242.

[3] F. R. K. Chung and R. L. Graham, On multicolor Ramsey numbers for complete bipartite

graphs, J. Combin. Theory Ser. B 18 (1975), 164-169.

[4] C. Clapham, The Ramsey number r(C4,C4,C4), Periodica Math. Hungarica 18 (1987), 317-

318.

[6] R. W. Irving, Generalized Ramsey numbers for small graphs, Discrete Mathematics 9 (1974),

251 – 264.

[7] F. Lazebnik and A. J. Woldar, General properties of some families of graphs defined by

systems of equations, submitted.

[8] S. P. Radziszowski, Small Ramsey numbers, Electronic J. Combin. 1 DS1 (1994), 1–30.

[9] Y. Yuansheng and P. Rowlinson, On extremal graphs without four-cycles, Utilitas Math. 41

(1992), 204-210.