Задача Данцера — Грюнбаума

Задача Данцера — Грюнбаума — проблема комбинаторной геометрии, ставящая вопрос о том, какое максимальное число точек можно разместить в многомерном пространстве, чтобы они не образовывали между собой прямых или тупых углов. Известно, что на плоскости можно расположить максимум три такие точки, в трёхмерном пространстве можно расположить пять таких точек. В 2017 году было доказано, что в пространстве размерности можно расположить Θ таких точек.

Постановка задачи

Для заданного обозначим через максимальное количество различных точек в -мерном пространстве, такие что любые три точки образуют остроугольный треугольник, то есть, для любых трёх скалярное произведение .

Как растёт относительно ?

Иными словами, задача состоит в том, чтобы найти простую формулу, выражающую через с как можно лучшей точностью (а также найти алгоритм построения множества из точек).

Множества, точки которых образуют только острые углы, называют остроугольными множествами. Заметим, что из определения следует, что никакие три точки в остроугольном множестве не могут лежать на одной прямой.

По состоянию на март 2018 года известно, что .

Множества без тупых углов

Следующая задача была поставлена Эрдёшем ещё раньше, чем классическая формулировка задачи Данцера — Грюнбаума[1]:

Для заданного обозначим через максимальное количество различных точек в -мерном пространстве, никакие три из которых не образуют строго тупого угла, то есть для любых трёх из которых выполнено

Как растёт относительно ?

Известно, что .

Вершины куба

В первой по-настоящему прорывной работе по этой теме Эрдёш и Фюреди построили большое множество, удовлетворяющее заданным условиям, из вершин -мерного куба . Поэтому в дальнейших работах, улучшающих их результат, иногда рассматривалась отдельно следующая задача:

Для заданного обозначим через максимальное количество различных вершин -мерного куба , никакие три из которых не образуют ни прямой, ни тупой угол, то есть для любых трёх из которых выполнено

Как растёт относительно ?

Очевидно, что .

История изучения

Первые упоминания (Эрдёш, 1948, 1957)

История задачи начинается в 1948 году, когда в разделе «Дополнительные проблемы для решения» журнала «The American Mathematical Monthly» Пал Эрдёш опубликовал следующий частный случай будущей задачи Данцера — Грюнбаума[2]:

Пусть даны восемь точек в пространстве . Докажите, что всегда можно найти три из них, которые не образуют остроугольный треугольник.

То есть в задаче спрашивалось, верно ли, что

В 1957 году в журнале Michigan Mathematical Journal, в статье со множеством гипотез, Эрдёш опубликовал уже общую гипотезу, но относительно тупоугольных множеств.

Пусть  — множество из точек в пространстве размерности . Верно ли, что тогда среди них обязательно существуют три точки, образующие тупой угол?

То есть гипотеза утверждала, что .

В статье говорились, что для доказательство нашли Николас Кёйпер и Бьёрдийк (Boerdijk), но их доказательство ещё не опубликовано.

Рядом с гипотезой содержался следующий вопрос:

Верно ли, что существует множество из шести (семи) точек в трёхмерном пространстве такие, что любые три из них образуют острый угол?

Или, другими словами, верно ли, что или .[1]

Первая гипотеза (Данцер, Грюнбаум, 1962)

Первую общую конструкцию для решения этой задачи построили Людвиг Данцер и Бранко Грюнбаум в статье 1962 года. Они построили в -мерном пространстве точку, матрица координат которых выглядела следующим образом (строки — разные точки, столбцы — разные координаты):

где  — попарно различные числа, все меньшие единицы.

Простой комбинаторный перебор разных типов возникающих углов позволяет показать, что никакие три из этих точек не образуют прямых или тупых углов. Из этого следует, что

В этой же работе авторы высказали гипотезу, что большего количества точек, выполняющих это условие, построить нельзя, то есть что [3].

Также в этой работе была доказана оценка сверху , которая была ранее предположена Эрдёшем.

Применение вероятностного метода (Эрдёш, Фюреди, 1983)

В 1983 году Пол Эрдёш и Золтан Фюре́ди, используя вероятностный метод, опровергли гипотезу Данцера — Грюнбаума, показав, что

Это дало возможность построить контрпримеры к гипотезе Данцера — Грюнбаума для .[4][5]

Однако, ввиду особенностей вероятностного метода, их доказательство было неэффективным и не позволяло построить это множество явно (кроме как прямым перебором)[3].

Основная идея Эрдёша и Фюреди состояла в том, чтобы выбрать некоторое множество точек, в котором (с положительной вероятностью) будет очень мало прямых и тупых углов, а потом просто удалить по одной точке у каждого из этих углов, тем самым устранив их все.

Улучшение без изменения метода

Даже не изменяя метода Эрдёша в самой его сути, можно получить лучшее оценку, просто выбрав другое число в качестве параметра, определяющего, сколько случайных точек следует выбирать.

Айгнер и Циглер в 2003 году, описывая теорему Эрдёша в своей обзорной книге «Доказательства из Книги», исправили этот параметр и получили, что .[6] Это — лучшее, что можно получить таким способом.

Беван (2006)

В 2006 году Д. Беван, немного дополнив конструкцию Эрдёша — Фюреди, улучшил оценку до .[7]

Однако точки в его конструкции не были вершинами единичного куба, так что оценку для он не улучшил.

Кроме того, Беван получил ряд результатов для малых размерностей , вследствие чего гипотеза Данцера — Грюнбаума была опровергнута при .[8]

Бучок (2009)

В 2009 году Лариса Бучок, не изменяя методов Эрдёша, Фюреди и Бевана для генерации точек, подсчитала более аккуратно потери от удаления точек, участвующих в неострых углах. Оказалось, что это позволяет получить следующие оценки[8]:

Бучок (2009/2010)

В 2010 году Бучок опубликовала сразу два метода улучшения предыдущих неравенств до результатов:

Доказательство второго из результатов было получено не позже 2009 года, поскольку упоминается в обзоре по этой теме.[9][10]

Улучшение вероятностной схемы через гиперграфы (Аккерман, Бен-Цви, 2008/2009)

Пока другие математики работали над элементарными улучшениями метода Эрдёша, Эйял Аккерман и Орен Бен-Цви независимо от них в 2009 году опубликовали полученное в 2008 году доказательство существования константы такой, что

Это стало первым асимптотическим улучшением оценки со времени статьи Эрдёша — Фюреди.

Доказательство занимало всего одну страницу и заключалось в применении к конструкции Эрдёша — Фюреди одной доказанной ранее алгоритмической леммы, касающейся размера независимого множества в гиперграфе при специальных условиях.[11]

Улучшение основания степени (Харанги, 2011)

В 2011 году Харанги доказал экспоненциальную оценку с лучшим основанием степени, а именно доказал существование константы такой, что

Его доказательство также являлось некоторой модификацией конструкции Эрдёша — Фюреди.[13]

Первая конкретная конструкция (Захаров, 2017)

30 апреля 2017 года Дмитрий Захаров, учась в 10 классе и являясь учеником Андрея Райгородского, опубликовал препринт явной (не вероятностной) конструкции, состоящей из точек, которые образуют только острые углы.

Конструкция Захарова не являлась развитием метода Эрдёша, а использовала новую, простую, описываемую на одной странице, идею.[14][3]

В ноябре того же года доказательство было опубликовано в журнале «Discrete & Computational Geometry».[15]

Оценка через числа Фиббоначи (Захаров, 2017)

В июле 2017 года Захаров опубликовал препринт работы, доказывающей, что

где  — -тое число Фибоначчи, а  — абсолютная константа.[16] Второе неравенство следует из формулы Бине.

Оценка порядка максимума (Геренчер, Харанги, 2017)

Пример построения в по методу Геренчера и Харанги

Появление работы Захарова спровоцировало попытки поиска лучших контрпримером для малых размерностей. Была высказана гипотеза, что , после чего были построены примеры остроугольных множеств, доказывающие, что

Идеей, использованной при построении этих примеров, было небольшое колебание точек -мерного куба в , в том числе по последней координате, не относящейся к -мерному подпространству этого куба.[17]

Эта идея легко обобщается на старшие размерности, что и проделали Геринчер и Харанги в сентябре 2017 года выпустили статью, доказывающую результат для любого . Как и решение grizzly их результат позволяет строить остроугольное множество данного размера из точек, сколь угодно близких к вершинам куба (отдалённым от них не более чем на ). Обсуждение на форуме также было упомянуто в этой статье.[18]

Примечания

  1. The Michigan Mathematical Journal, Volume 4, Issue 3 (1957), 291—300, Paul Erdős, Some unsolved problems, с. 296, задача 19
  2. The American Mathematical Monthly, Vol. 55, No. 7, Aug. — Sep., 1948; Paul Erdos, Problems for Solution 4305-4309, с. 431, задача 4306
  3. Райгородский А.М. Остроугольные множества // Квант. — 2018. Вып. 3. С. 10–13.
  4. P. Erdos, Z. Furedi. The greatest angle among n points in the d-dimensional Euclidean space // Combinatorial mathematics.--Marseille-Luminy, 1981.--P. 275—283; North-Holland Math. Stud.--75.--North-Holland, Amsterdam, 1983 (недоступная ссылка). Дата обращения: 19 марта 2018. Архивировано 28 августа 2018 года.
  5. Райгородский, 2009, с. 8.
  6. Айгнер, 2006, с. 93—94.
  7. D. Bevan, «Sets of Points Determining Only Acute Angles and Some Related Colouring Problems», Electron. J. Combin., 13:1 (2006), 24 p.
  8. Л. В. Бучок, «Остроугольные треугольники Данцера — Грюнбаума», УМН, 2009, том 64, выпуск 3(387), страницы 181—182
  9. Л. В. Бучок, «О двух новых подходах к получению оценок в проблеме Данцера — Грюнбаума, Матем. заметки, 2010, том 87, выпуск 4, страницы 519—527»
  10. Райгородский, 2009, с. 21.
  11. Eyal Ackerman, Oren Ben-Zwi, «On sets of points that determine only acute angles», European Journal of Combinatorics, Volume 30, Issue 4, May 2009, Pages 908—910
  12. Claudia Bertram-Kretzberg, Hanno Lefmann, "The Algorithmic Aspects of Uncrowded Hypergraphs", SIAM J. Comput., 29(1), 201–230
  13. Viktor Harangi, «Acute Sets In Euclidean Spaces», SIAM J. Discrete Math., 25(3), 1212—1229
  14. arXiv:1705.01171 D. Zakharov, «Acute sets»
  15. Dmitriy Zakharov, «Acute Sets», «Discrete & Computational Geometry»
  16. D. Zakharov, «Acute sets»
  17. Улучшено (?) решение Эрдёша по остроугольным треугольникам; копия этой страницы приложена к arXiv:0906.0290
  18. arXiv:1709.03411, Balázs Gerencsér, Viktor Harangi, «Acute sets of exponentially optimal size»

Литература

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.