Аннотация:
В 50-e годы XX столетия Нельсон сформулировал проблему о величине хроматического числа пространства $\chi(\mathbb R^n)$, равного минимальному количеству цветов, в которые можно так покрасить точки пространства $\mathbb R^n$, чтобы между точками одного цвета не было евклидова расстояния 1. Несмотря на простоту формулировки, эта проблема до сих пор не решена даже для случая евклидовой плоскости. В случае же растущего $n$ долгое время не удавалось получить даже нелинейную по $n$ оценку снизу, пока в 70-е годы не выяснилось, что задача напрямую связана с проблемами экстремальной комбинаторики. Оказалось, что для получения хороших нижних оценок $\chi(\mathbb R^n)$ достаточно оценить сверху величину $m(n,k,t)$ — число ребер в $k$-однородном гиперграфе на $n$ вершинах с запретом на пересечение ребер по $t$ элементам. И уже в 1981 году Франкл и Уилсон при помощи линейно-алгебраического метода и подбора нужных параметров $k$ и $t$ получили блестящий результат о том, что величина $\chi(\mathbb R^n)$ растет экспоненциально при $n\to\infty$.
В ходе доклада мы обсудим, почему задача об отыскании величины $m(n,k,t)$ все еще далека от окончательного решения и как можно получать новые нижние границы в этой и похожих на нее задачах. Мы коснемся проблем в смежных областях: задач теории кодирования, теоремы Алсведе–Хачатряна, а также поймем, как эти результаты могут помочь в наших исследованиях. Наконец, в качестве следствия мы получим новые границы для теории кодов, исправляющих ошибки, и комбинаторной геометрии.
|
