Преглед на материал

Първа теорема на Ремзи



Нека X е множество, а k е естествено число. Ще казваме, че е зададено k-оцветяване на X, ако част от k-елементните подмножества на X са обявени за черни, а останалите - за бели. Едно подмножество Y на X с поне k елемента ще наричаме едноцветно (черно или бяло) при дадено k-оцветяване, ако всичките ми k-елементни подмножества са оцветени еднакво при това оцветяване.

Ако υ X и Xυ се състои от различните от υ елементи на Х, а γ е k-оцветяване на Х, с γυ ще означим (k-1)-оцветяването на Хυ, дефинирано по следния начин: всяко (к-1)-елементно подмножество М на Хυ има цвета при оцветяването γ на k-елементното множество М υ; ще казваме, че оцветяването γυ е индуцирано по γ.

Лема 1. Нека υX, γ е k-оцветяване на X и γυ е (k-1)-оцветяване на Xυ, индуцирано по γ. Ако Y е подмножество на X и υ Y, множеството Y е едноцветно при γ тогава и само тогава, когато Yυ e едноцветно при γ и същевременно е едноцветно от същия цвят при γυ.

Първа теорема на Ремзи. Нека k, p, q саестествени числа и p≥ k, q≥ k. Съществува естествено число n със свойството (k; p, q) : ако X е n-елементно множество и γе k-оцветяване на Х, в множеството Х има...

Коментари


Няма намерени коментари