Гіпотеза Борсука

Гіпотеза Борсука (задача Борсука) — спростована гіпотеза в комбінаторній геометрії:

Розрізання відрізка, трикутника та тетраедра на частини меншого діаметра

Чи можливо довільне тіло скінченного одиничного діаметра в $n$ -вимірному евклідовому просторі розбити на не більш ніж $n+1$ частину так, що діаметр кожної частини буде меншим за 1?

Висунув Кароль Борсук^[pl] 1933 року. Відіграла значну роль у розвитку комбінаторної геометрії XX століття: протягом тривалого періоду гіпотезу підтверджено для низки окремих випадків^[⇨] та основні зусилля були спрямовані на пошук доведень у загальному випадку, оскільки вагомих сумнівів у її справедливості не виникало^[1]. Однак 1993 року знайдено контрприклад^[⇨].

Станом на 2023 доведено, що гіпотеза істинна при $n\leqslant 3$ , і хибна для $n\geqslant 64$ , статус твердження для $4\leqslant n<64$ залишається нез'ясованим.

Розрізання правильного шестикутника ширини 1 на 3 частини діаметром менше ніж 1.

Сприятливі розв'язки ред.

Випадок $n=1$ очевидний. Випадок $n=2$ довів 1933 року сам Борсук, скориставшись результатом Дюли Пала^[hu] 1929 року, згідно з яким будь-яку фігуру діаметра 1 можна помістити в правильний шестикутник ширини 1, а такий шестикутник у свою чергу допускає розрізання на три п'ятикутники діаметра ${\tfrac {\sqrt {3}}{2}}<1$ . Крім того, Борсук довів, що $n$ -вимірну кулю не можна розділити на $n$ частин меншого діаметра, тим самим затвердивши нижню оцінку кількості частин (доведення ґрунтується на теоремі Борсука — Уляма).

1946 року Гадвігер^[en] довів справедливість гіпотези при всіх $n$ для опуклих тіл із гладкою межею^[2].

1947 року Юліан Перкаль^[pl] довів випадок $n=3$ для всіх обмежених тіл^[3], незалежно від нього 1955 року цей самий результат отримав британський математик Егглстон; просте доведення, подібний до Борсукового, знайшли пізніше Бранко Ґрюнбаумом і Альдар Геппеш; вони довели, що будь-яке тіло діаметра 1 можна помістити у певний октаедр з відсіченими трьома вершинами, який у свою чергу допускає розбиття на 4 частини діаметра менше 0,9888.

Щонайменше від початку 1970-их років гіпотезу підтверджено для центрально-симетричних тіл. 1971 року Клод Роджерс довів гіпотезу для будь-якої множини, інваріантної відносно дії групи перетворень, які залишають на місці правильний $n$ -вимірний симплекс.

1993 року Борис Декстер установив справедливість гіпотези для опуклих тіл з поясом із регулярних точок^[4], 1995 року він позитивно розв'язав задачу для всіх тіл обертання в довільних розмірностях^[5].

Число Борсука ред.

Число Борсука $f(n)$ — найменша кількість можливих частин меншого діаметра, на які можна розбити будь-яке обмежене тіло в $n$ -вимірному просторі. Паралельно з підтвердженням гіпотези $f(n)=n+1$ в окремих випадках, покращувалися нижні та верхні оцінки для $f(n)$ . Порівняно легко отримані оцінки $f(n)\leqslant (2{\sqrt {n}}+1)^{n}$ і $f(n)\leqslant 2^{n}$ . 1983 року Маршалл Лассак з'ясував, що $f(n)\leqslant 2^{n-1}+1$ .

Серед асимптотичних верхніх оцінок довгий час найкращою була оцінка Клода Роджерса^[en] (1965): $f(n)\leqslant {\big (}{\sqrt {2}}+o(1){\big )}^{n}$ ; 1988 року Одед Шрамм^[en] показав, що:

f(n)\leqslant {\Big (}{\sqrt {\tfrac {3}{2}}}+o(1){\Big )}^{n}

.

Заперечні розв'язки ред.

Заперечний розв'язок задачі в загальному випадку виявили 1993 року Гіль Калаї^[en] і Джефф Кан^[en]^[6], які побудували контрприклад у розмірності $n=1325$ та довели невиконання гіпотези для всіх $n>2014$ . Крім того, вони показали, що для досить великих $n$ , існують $n$ -вимірні тіла, які не можна розбити на ${\big (}1{,}203+o(1){\big )}^{\sqrt {n}}$ частин меншого діаметра. В наступні роки розмірність, вище від якої гіпотеза не виконується, послідовно знижувалася:

1993 — $n\geqslant 2015$ (Калаї — Кан),
1994 — $n\geqslant 946$ (Ніллі),
1997 — $n\geqslant 903$ (Вайсбах — Грей),
1997 — $n\geqslant 561$ (Райгородський)^[7],
2000 — $n\geqslant 560$ (Вайсбах),
2001 — $n\geqslant 324$ (Гінрігз),
2002 — $n\geqslant 323$ (Піхурко),
2003 — $n\geqslant 298$ (Гінрігз — Ріхтер)^[8],
2013 — $n\geqslant 65$ (Бондаренко)^[9],
2013 — $n\geqslant 64$ (Єнріх)^[10].

Для побудови контприкладів у всіх випадках використано скінченні множини та тонкі комбінаторні результати^[11]. Нижні оцінки для найменшого числа частин меншого діаметра в більшості контрприкладів — ${\big (}1{,}203+o(1){\big )}^{\sqrt {n}}$ , у одному з результатів Райгородського (1999) цю оцінку покращено до ${\big (}1{,}2255+o(1){\big )}^{\sqrt {n}}$ .

Варіації та узагальнення ред.

1953 року Девід Ґейл^[en] висунув гіпотезу, що будь-яке тіло одиничного діаметра в тривимірному просторі допускає розбиття на 4 частини з діаметром:

{\sqrt {\frac {3+{\sqrt {3}}}{6}}}\approx 0{,}888

,

тобто, куля є «найгіршим» у цьому сенсі тілом^[12].

1971 року гіпотезу Борсука підтверджено для сферичного та гіперболічного просторів при $n=2,3$ ^[13].

1991 року цей результат узагальнено на довільні розмірності для центрально-симетричних опуклих гіперповерхонь^[14].

2012 року вивчено аналоги проблеми Борсука у просторі $\mathbb {Q} ^{n}$ з евклідовою метрикою та з метрикою $l_{p}$ ^[15].

2019 року розглянуто питання про розбиття довільних обмежених метричних просторів на задану кількість підмножин меншого діаметра, та виявлено критерії здійсненності та нездійсненності такого розбиття залежно від відстані за метрикою Громова — Гаусдорфа від заданого простору до симплексів заданої потужності, де під симплексом розуміють метричний простір, у якому всі ненульові відстані однакові^[16].

Примітки ред.

↑ Райгородский, 2006, с. 27.
↑ Болтянский — Гохберг, 1965, с. 34.
↑ Грюнбаум, 1971, с. 62.
↑ B. V. Dekster. The Borsuk conjecture holds for convex bodies with a belt of regular points // Geometriae Dedicata. — 1993. — Т. 45 (12 травня). — С. 301–306.
↑ B. V. Dekster. The Borsuk conjecture holds for bodies of revolution // Journal of Geometry. — 1995. — Т. 52 (12 травня). — С. 64–73.
↑ J. Kahn, G. Kalai. A counterexample to Borsuk’s conjecture // Bull. Amer. Math. Soc. (N.S.). — 1993. — Vol. 29, no. 1 (12 May). — P. 60—62. — arXiv:math.MG/9307229.
↑ А. М. Райгородский. О размерности в проблеме Борсука // УМН. — 1997. — Т. 52, № 6(318) (12 травня). — С. 181—182.
↑ A. Hinrichs, C. Richter. New sets with large Borsuk numbers // Discrete Mathematics. — 2003. — Т. 270 (12 травня). — С. 137—147. Архівовано з джерела 27 вересня 2007.
↑ Andriy V. Bondarenko. On Borsuk’s conjecture for two-distance sets. — 2013. — 12 травня. — arXiv:1305.2584.
↑ Thomas Jenrich. A 64-dimensional two-distance counterexample to Borsuk’s conjecture. — 2013. — 12 травня. — arXiv:1308.0206.
↑ Райгородский, 2006.
↑ Райгородский, 2006, с. 16.
↑ А. С. Рисслинг. Проблема Борсука в пространствах постоянной кривизны // Украинский геометрический сборник. — Харьков. — Т. 11. — С. 78—83. Архівовано з джерела 9 січня 2021.
↑ А. Д. Милка. Аналог проблемы Борсука // Известия вузов. Серия математическая. — 1992. — № 5 (12 травня). — С. 58—63.
↑ А. Б. Купавский, Е. И. Пономаренко, А. М. Райгородский. О некоторых аналогах проблемы Борсука в пространстве $\mathbb {Q} ^{n}$ // Труды МФТИ. — 2012. — Т. 12, № 1 (12 травня). — С. 81—90.
↑ А. О. Иванов, А. А. Тужилин. Solution to Generalized Borsuk Problem in Terms of the Gromov–Hausdorff Distances to Simplexes. — arXiv:1906.10574v1.

Література ред.

В. Г. Болтянский, И. Ц. Гохберг. Теоремы и задачи комбинаторной геометрии. — М. : Наука, 1965. — 108 с. — (Математическая библиотечка) (містить доведення гіпотези в розмірностях 2 і 3)
В. Г. Болтянский, И. Ц. Гохберг. Разбиение фигур на меньшие части/ серия = Популярные лекции по математике, выпуск 50. — М. : Наука, 1971. — 88 с.
Б. Грюнбаум. Этюды по комбинаторной геометрии и теории выпуклых тел. — М. : Наука, 1971.
А. М. Райгородский. Проблема Борсука. — М. : МЦНМО, 2006. — 56 с.
А. Б. Скопенков. $n$ -мерный куб, многочлены и решение проблемы Борсука // Математическое просвещение. — М. : МЦНМО, 1999. — Вип. 3 (3) (12 травня).

[FOOTNOTEРайгородский200627-1] Райгородский, 2006, с. 27.

[FOOTNOTEБолтянский_—_Гохберг196534-2] Болтянский — Гохберг, 1965, с. 34.

[FOOTNOTEГрюнбаум197162-3] Грюнбаум, 1971, с. 62.

[4] B. V. Dekster. The Borsuk conjecture holds for convex bodies with a belt of regular points // Geometriae Dedicata. — 1993. — Т. 45 (12 травня). — С. 301–306.

[5] B. V. Dekster. The Borsuk conjecture holds for bodies of revolution // Journal of Geometry. — 1995. — Т. 52 (12 травня). — С. 64–73.

[6] J. Kahn, G. Kalai. A counterexample to Borsuk’s conjecture // Bull. Amer. Math. Soc. (N.S.). — 1993. — Vol. 29, no. 1 (12 May). — P. 60—62. — arXiv:math.MG/9307229.

[7] А. М. Райгородский. О размерности в проблеме Борсука // УМН. — 1997. — Т. 52, № 6(318) (12 травня). — С. 181—182.

[8] A. Hinrichs, C. Richter. New sets with large Borsuk numbers // Discrete Mathematics. — 2003. — Т. 270 (12 травня). — С. 137—147. Архівовано з джерела 27 вересня 2007.

[9] Andriy V. Bondarenko. On Borsuk’s conjecture for two-distance sets. — 2013. — 12 травня. — arXiv:1305.2584.

[10] Thomas Jenrich. A 64-dimensional two-distance counterexample to Borsuk’s conjecture. — 2013. — 12 травня. — arXiv:1308.0206.

[FOOTNOTEРайгородский2006-11] Райгородский, 2006.

[FOOTNOTEРайгородский200616-12] Райгородский, 2006, с. 16.

[13] А. С. Рисслинг. Проблема Борсука в пространствах постоянной кривизны // Украинский геометрический сборник. — Харьков. — Т. 11. — С. 78—83. Архівовано з джерела 9 січня 2021.

[14] А. Д. Милка. Аналог проблемы Борсука // Известия вузов. Серия математическая. — 1992. — № 5 (12 травня). — С. 58—63.

[15] А. Б. Купавский, Е. И. Пономаренко, А. М. Райгородский. О некоторых аналогах проблемы Борсука в пространстве $\mathbb {Q} ^{n}$ // Труды МФТИ. — 2012. — Т. 12, № 1 (12 травня). — С. 81—90.

[16] А. О. Иванов, А. А. Тужилин. Solution to Generalized Borsuk Problem in Terms of the Gromov–Hausdorff Distances to Simplexes. — arXiv:1906.10574v1.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]