Русская Википедия:Гипотеза Борсука
Гипотеза Бо́рсука (проблема Борсука) — опровергнутая гипотеза в комбинаторной геометрии:
- Возможно ли произвольное тело конечного единичного диаметра в <math>n</math>-мерном евклидовом пространстве разбить на не более чем <math>n+1</math> часть так, что диаметр каждой части будет меньше 1?
Выдвинута Каролем Борсуком в 1933 году. Сыграла значительную роль в развитии комбинаторной геометрии XX века: в течение длительного периода гипотеза подтверждалась для ряда частных случаевШаблон:Переход и основные усилия были направлены на поиск доказательства в общем случае, поскольку весомых сомнений в её справедливости не возникалоШаблон:Sfn. Однако в 1993 году был найден контрпримерШаблон:Переход.
По состоянию Шаблон:На доказано, что гипотеза верна при <math>n \leqslant 3</math>, и неверна для <math>n\geqslant 64</math>, статус утверждения для <math>4 \leqslant n < 64</math> остаётся невыясненным.
Положительные решения
Случай <math>n=1</math> очевиден. Случай <math>n = 2</math> был доказан самим Борсуком в 1933 году, он воспользовался результатом Шаблон:Нп2 1929 года, согласно которому любую фигуру диаметра 1 можно поместить в правильный шестиугольник ширины 1, а такой шестиугольник в свою очередь допускает разрезание на три пятиугольника диаметра <math>\tfrac{\sqrt 3}2 < 1</math>. Кроме того, Борсук доказал, что <math>n</math>-мерный шар нельзя разделить на <math>n</math> частей меньшего диаметра, тем самым утвердив нижнюю оценку для количества частей (доказательство основано на теореме Борсука — Улама).
В 1946 году Хадвигер доказал справедливость гипотезы при всех <math>n</math> для выпуклых тел с гладкой границейШаблон:Sfn.
В 1947 году Шаблон:Нп2 доказал случай <math>n = 3</math> для всех ограниченных телШаблон:Sfn, независимо от него в 1955 году этот же результат получил британский математик Эгглстон; простое доказательство, сходное с доказательством Борсука, было найдено несколько позже Бранко Грюнбаумом и Альдаром Хеппешем; они доказывают, что любое тело диаметра 1 можно поместить в определённый октаэдр с отсечёнными тремя вершинами, который в свою очередь допускает разбиение на 4 части диаметра меньше 0,9888.
По меньшей мере с начала 1970-х годов гипотеза подтверждена для центрально-симметричных тел. В 1971 году Клод Роджерс доказал гипотезу для всякого множества, инвариантного относительно действия группы преобразований, оставляющих на месте правильный <math>n</math>-мерный симплекс.
В 1993 году Борис Декстер установил справедливость гипотезы для выпуклых тел с поясом из регулярных точек[1], в 1995 году им же положительно решена проблема для всех тел вращения в произвольных размерностях[2].
Число Борсука
Число Борсука <math>f(n)</math> — наименьшее число возможных частей меньшего диаметра, на которые можно разбить всякое ограниченное тело в <math>n</math>-мерном пространстве. Параллельно с подтверждением гипотезы <math>f(n) = n+1</math> в частных случаях, улучшались нижние и верхние оценки для <math>f(n)</math>. Сравнительно легко получены оценки <math>f(n) \leqslant (2 \sqrt n + 1)^n</math> и <math>f(n) \leqslant 2^n</math>. В 1983 году Маршалл Лассак установил, что <math>f(n) \leqslant 2^{n-1} + 1</math>.
Среди асимптотических верхних оценок долгое время лучшей была оценка Шаблон:Нп2: <math>f(n) \leqslant \big(\sqrt 2 + o(1)\big)^n</math>; в 1988 году Одед Шрамм установил, что:
- <math>f(n) \leqslant \Big(\sqrt \tfrac{3}{2} + o(1)\Big)^n</math>.
Отрицательные решения
Отрицательное решение проблемы в общем случае выявлено в 1993 году Шаблон:Нп2 и Шаблон:Нп2[3], построившими контрпример в размерности <math>n = 1325</math>, и доказавшими невыполнение гипотезы для всех <math>n>2014</math>. Кроме того, они показали, что для достаточно больших <math>n</math>, существуют <math>n</math>-мерные тела, которые нельзя разбить на <math>\big(1{,}203+o(1)\big)^{\sqrt{n}}</math> частей меньшего диаметра. В последующие годы размерность, выше которой гипотеза не выполняется, последовательно снижалась:
- 1993 — <math>n \geqslant 2015</math> (Калай — Кан),
- 1994 — <math>n \geqslant 946</math> (Нилли),
- 1997 — <math>n \geqslant 903</math> (Вайссбах — Грей),
- 1997 — <math>n \geqslant 561</math> (Райгородский)[4],
- 2000 — <math>n \geqslant 560</math> (Вайссбах),
- 2001 — <math>n \geqslant 324</math> (Хинрихс),
- 2002 — <math>n \geqslant 323</math> (Пихурко),
- 2003 — <math>n \geqslant 298</math> (Хинрихс — Рихтер)[5],
- 2013 — <math>n \geqslant 65</math> (Бондаренко)[6],
- 2013 — <math>n \geqslant 64</math> (Йенрих)[7].
Для построения контпримеров во всех случаях использовались конечные множества и использованы тонкие комбинаторные результатыШаблон:Sfn. Нижние оценки для минимального числа частей меньшего диаметра в большинстве контрпримеров — <math>\big( 1{,}203+o(1)\big)^{\sqrt{n}}</math>, в одном из результатов Райгородского (1999) эта оценка улучшена до <math>\big( 1{,}2255+o(1)\big)^{\sqrt{n}}</math>.
Вариации и обобщения
В 1953 году Дэвид Гейл выдвинул гипотезу, что любое тело единичного диаметра в трёхмерном пространстве допускает разбиение на 4 части с диаметром:
- <math>\sqrt{\frac{3+\sqrt{3}}6}\approx0{,}888</math>,
то есть шар является «наихудшим» в этом смысле теломШаблон:Sfn.
В 1971 году гипотеза Борсука подтверждена для сферического и гиперболического пространств при <math>n=2,3</math>[8].
В 1991 году этот результат обобщён на произвольные размерности для центрально-симметрических выпуклых гиперповерхностей[9].
В 2012 году изучены аналоги проблемы Борсука в пространстве <math>\Q^n</math> с евклидовой метрикой и с метрикой <math>l_p</math>[10].
В 2019 году рассмотрен вопрос о разбиении произвольных ограниченных метрических пространств на заданное количество подмножеств меньшего диаметра, и выявлены критерии осуществимости и неосуществимости такого разбиения в зависимости от расстояния по метрике Громова — Хаусдорфа от заданного пространства до симплексов заданной мощности, где под симплексом понимается метрическое пространство, в котором все ненулевые расстояния одинаковы[11].
Примечания
Литература
- Шаблон:Книга (содержит доказательство гипотезы в размерностях 2 и 3)
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
