Аннотация:
Гиперграф есть пара $(V, E)$, где $V$ — конечное множество вершин, $E\subset 2^V$ — семейство его подмножеств. Гиперграф называется $n$-однородным, если каждое его ребро имеет размер $n$.
Я расскажу о задаче Эрдёша–Хайнала, которая заключается в нахождении минимального (по количеству ребер) $n$-однородного гиперграфа с хроматическим числом 3 (то есть такого, что любая 2-раскраска вершин содержит одноцветное ребро), и её обобщениях.
Наиболее общий вид задачи — поиск маленьких “нетривиальных” гиперграфов. Большинство результатов в этой области получается вероятностными методами.
|
