Проблемы Борсука и Нелсона–Эрдеша–Хадвигера в комбинаторной геометрии

Современная комбинаторная геометрия — это активно развивающаяся область математики, пользующаяся значительной популярностью среди специалистов и имеющая немало важных приложений. Одними из наиболее ярких основополагающих задач комбинаторной геометрии являются проблемы Борсука и Нелсона–Эрдеша–Хадвигера. Можно сказать даже, что сама комбинаторна геометрия не сформировалась бы в том виде, в каком она теперь существует, не будь упомянутые проблемы поставлены в свое время. Обе проблемы весьма легко и доступно формулируются, оставаясь в то же время крайне трудными по сути, и это придает им особенную привлекательность. Первая проблема, предложенная К. Борсуком в 1933 году, состоит в определении минимального числа $f(n)$ частей меньшего диаметра, на которые может быть разбито произвольное ограниченное множество в евклидовом пространстве $R^n$. Вторая проблема, возникшая в начале 50-х годов XX века, сводится к отысканию наименьшего количества цветов, в которые может быть так раскрашено все $R^n$, чтобы точки, отстоящие друг от друга на расстояние 1, были разноцветными. Последняя величина называетс хроматическим числом пространства и обозначается $\chi(R^n)$.
Многочисленные результаты относительно обеих проблем были получены в разное время такими известными специалистами в области комбинаторики и геометрии, как К. А. Роджерс, В. Г. Болтянский, П. Эрдеш, Г. М. Циглер, Н. Алон, Г. Калаи, Ж. Бургейн и др. Однако переломный момент в истории задач, приведший впоследствии к их существенному сближению, может быть датирован 1981-м годом, когда в одной статье П. Франкла и Р. М. Уилсона был разработан нетривиальный линейно-алгебраический метод в комбинаторике, позволивший в конечном счете добиться значительных продвижений как в проблеме Борсука, так и в проблеме Нелсона–Эрдеша–Хадвигера. В последние годы линейно-алгебраический метод был существенно развит докладчиком. Кроме того, им были предложены некоторые новые нетривиальные подходы к задачам — например, так называемый «метод альтернирования». В результате, с одной стороны, удалось улучшить практически все прежние оценки на величины $f(n)$ и $\chi(R^n)$, а с другой стороны, были обнаружены новые неожиданные связи между проблемами.
В докладе сперва будет рассказано об интригующей истории вопроса, которая носит едва ли не детективный характер. Затем мы подробно остановимся на методах решения наших задач. Наконец, будут предложены различные важные обобщения проблем, а также сформулируем некоторые гипотезы.
Для понимания доклада специальных знаний не требуется.