Аннотация:
Гиперграф есть пара (V,E), где V – конечное множество вершин, $E\subset2^V\setminus V \setminus\emptyset$ – множество ребер (для удобства мы предполагаем отсутствие пустых и одновершинных ребер). Гиперграф называется n-однородным, если каждое его ребро имеет размер n. Раскраска вершин гиперграфа в r цветов называется правильной, если каждое ребро содержит вершины хотя бы двух цветов.
Обозначим через m(n,r) минимальное число ребер в гиперграфе, который не красится в r цветов (то есть для которого не найдется правильной раскраски вершин в r цветов). Я расскажу оценку, полученную независимо мной и Козиком в 2013 году:
m(n,r)\ge c(n/ln(n))^{1−1/r} r^n,
а также нижнюю оценку Козика и Шабанова (2014) на функцию Ван дер Вардена.
|
