299
правок
Изменения
→Числа Рамсея больших размерностей
==Числа Рамсея больших размерностей==
Определение 10.3. Пусть то, к, ni,..., пк £ N причём щ,..., пк > то,
Число Рамсея rm(k; rii,..., пк) — зто наименьшее из Есех таких чисел х £ N, чте при л к бой раскраске то-элементных подмножеств ж-элементнего множестьа М в к пестов для нскстсрсго г £ [1..к] обязательно найдётся таксе множестьо чте |ИД — щ в ьсе m-злементные подмножестьа множестьа Wi имеют нвет г.
Число то называется размерностью числа Рамсея rm(fc;ni,... ,пк).
Замечание 10.3, 1) Нетрудно пенять что числа Рамсея размеры сети 2 — эте определённые выше числа Рамсея для клик
2) При количестве цветов, равном 2, зтот параметр мы будем спускать и писать rm(ni,n2) вместе rm(2;ni,n2).
Определение 1С.4. Для каждою множества М через Мк мы будем обозначать множество всех fc-элементных подмножеств М.
Теорема 10,4. Пусть то, fc,ni,... ,пк — патуралънье число, причём к > 2. ani,... ,пк > т. Тогда число Рамсея rm(k;ni,... ,пк) существует) (то eemt ксиечьоу
Доказательство, 1, Мы будем доказывать теорему пс индукции. Начнем сс случая к = 2. Приступая к доказательству для числа rm(ni,n2) мы будем считать доказанным утверждение теоремы для чисел Рамсея всех меньших размерностей и чисел Рамсея размерности то с меньшей суммей ni+n2. В качестве базы будем использовать случай чисел Рамсея размерности 2 разобранный выше. Итак, мы докажем, что
Гт{пЪ П2) - 1 < р = rm_i(rm(?Ti - 1, П2), Гт(пЬ П2 - 1)).
Рассмотрим (р+1)-элементное множество М и выделим в нём элемент а. Пусть М0 — М\ {а}. Пусть р : Мт —> {1,2} — произвольная раскраска в деэ нЕСта. Рассмотрим раскраску р' : М™-1 —> {1,2}. определённую следующим сбразом: для каждого мнежества В £ М™-1 пусть р'(В) = p(BU{a}).
Так как \М0\ = р либо существует rm(ni — 1, ?г2)-злементное подмножестве Mi с М0, для кет ер его р'(В) — 1 на всех В £ Mf1-1. либо существует rm(ni,n2 — 1)-элементнсе подмнсжество М2 С М0. для ко-тсрсю р'(В) = 2 на всех В е М™'1. Случаи аналсгичны, рассмотрим первый случай и множество Мх
Пс индукнионнсму предположен и к не |Mi| = rm{n\ — 1,п2) следует что либс существует п\ — 1 элементнсе подмнсжество Nx С Mi- для кото-рсго р(А) = 1 на всех А £ N™, либо существует п2-эле мен тис с подмножество N2 С Mi, для которого р{А) = 2 на Есех А £ N™. Вс втором случае искомое подмножество найдено (это N2). рассмотрим перЕый случай и множество N = N± U{a}. Пуств А £ Nm. Если А $ а то А £ iVf1 и следовательно р(А) = I. Если же А э а. тс множестве А\{а} £ N™'1 с М™-1 и петому = \ {а}) = 1. Учитывая, что \N\ = ni, мы нашли искомое подмножество и в этом случае
2. При к > 2 будем Еести индукцию по к с доказанной выше базей к = 2. При к > 2 мы докажем неравенстве
rm(k;nx, ...,nk)<q = rm(rm(k - ... ,nfc_i),nfe).
Для этою мы рассмотрим множестве М на g вершинах и произвелвг ную раскраску р : Мт —> [l..k] е /с цестов. Рассмотрим раскраску р' : Мт -д {О, А;}, е которой цвета 1,..., fc — 1 раскраски р склеены в цвет С. Тогда существует либс таксе подмножество М0 С М что |М0| = гт(/ь — 1; ni,..., ?Tfc_i) и р'(Д) = 0 на всех А £ М™. либо сушестЕует такое г^-злементное педмножестпе с М. что р(А) = р'{А) — к на Есех А 6 М£\ Во Егерем случае Мк — искомое подмножество а е пер-есм случае заметим чте на любом подмножестве А £ М™ из р'{А) = О следует р{А) £ [l..fc — 1]. Исходя из размера множества М0 по индукни-еннсму предположению получаем, чте найдется искомое подмнсжество множества М для одного из цветов 1,..., к — 1 □
==Числа Рамсея для произвольных графов==
==Индуцированная теорема Рамсея==
===Случай двудольного графа===
===Случай произвольного графа===
