Раскраска в 5 цветов

[marie-la]

Помогите, пожалуйста, никак не выходит.

Дано семейство различных $k$-элементных подмножеств $S=\{A_1,...,A_m\}$ множества ${1, 2,. . . , n}$ . Назовём элементы $i$ и $j$ соседями, если они вместе входят хотя бы в одно из множеств $A_p, p= 1, 2, . . . ,m$. Пусть у каждого $i\in{1,2,...,n}$ существует не более чем $2k$ (здесь $k>5$- некоторое натуральное число) соседей (включая сам $i$ ). Докажите, что элементы $1,2,...,n$ при всех достаточно больших $k$ можно раскрасить пятью красками так, чтобы никакое подмножество из $S$ не было одноцветным.

По идее тут речь об одноцветных кликах размера $k$ идёт. То есть, если соединим соседние вершины ребром, то у каждой степень не больше $2k-1$. И нужно доказать, что можно раскрасить 5 цветами так, чтоб одноцветных клик размера $k$ не было. Я на тему одноцветных клик только числа Рамсея нашла. Может, есть какие-нибудь ещё результаты?

[marie-la]

Хотя так не пойдёт, похоже. Тут раскраска вершин, а не рёбер ведь.

[DeBill]

marie-la
Странная задача: лишние условия? Или то $k$ и другое $k$ - различны?
Давайте покрасим все абы как, а затем будем перекрашивать элементы так, чтобы количество одноцветных подмножеств уменьшалось... Пусть есть (красное) одноцветное подмножество. Перекрасим его элемент $x$ в другой цвет. Что будет означать (в смысле количества соседей у $x$), что при любом из 4-х перекрашиваний, количество одноцветных подмножеств не уменьшилось?

[marie-la]

DeBill
О, похоже, поняла! Спасибо :) Так получается, что достаточно трёх цветов, что ли?

[DeBill]

marie-la
Ну да, что и странно. Похоже, можно убрать "включая сам", "достаточно больших", а вместо $2k$ написать аж $4k$...