"Записки научных семинаров ПОМИ"
Том 488, стр. 168-176
Задача Эрдёша--Хайнала для 3-графов
Д. Д. Черкашин
Chebyshev Laboratory,
St.Petersburg State University;
Moscow Institute of Physics and Technology,
Lab. of advanced combinatorics and network applications,
Institutsky lane 9, Dolgoprudny,
Moscow region, 141700, Russia;
National Research University Higher School of Economics,
Soyuza Pechatnikov str., 16,
St. Petersburg, Russia
matelk@mail.ru
- Аннотация:
Пусть $m(n,r)$ -- минимальное число ребер в $n$-однородном гиперграфе, который не может быть
правильно раскрашен в $r$-цветов.
Широкая история задачи освещена в обзоре Райгородского и Шабанова. Известно, что для фиксированного $n$
последовательность
\[
\frac{m(n,r)}{r^n}
\]
имеет предел.
Единственным тривиальным случаем является $n=2$, в котором $m(2,r) = \binom{r+1}{2}$.
Эта заметка посвящена случаю $n=3$.
Мы сравниваем имеющиеся методы, а затем улучшаем нижнюю оценку.
Библ. -- 11 назв.
- Ключевые слова: экстремальная комбинаторика, раскраски гиперграфов
[ extremal combinatorics, hypergraph colorings]
Полный текст(.pdf)