Просмотр кода страницы Задача Данцера — Грюнбаума

'''Задача Данцера — Грюнбаума''' — проблема [[Комбинаторная геометрия|комбинаторной геометрии]], ставящая вопрос о том, какое максимальное число точек можно разместить в [[Многомерное пространство|многомерном пространстве]], чтобы они не образовывали между собой прямых или тупых углов. Известно, что на плоскости можно расположить максимум три такие точки, в трёхмерном пространстве можно расположить пять таких точек. В 2017 году было доказано, что в пространстве размерности <math>d</math> можно расположить [[Θ-большое|Θ]]<math>(2^d)</math> таких точек.

== Постановка задачи ==
{{рамка}}
Для заданного <math>d</math> обозначим через <math>f(d)</math> максимальное количество различных точек в <math>d</math>-мерном пространстве, такие что любые три точки образуют [[остроугольный треугольник]], то есть, для любых трёх <math>x,y,z</math> [[скалярное произведение]] <math>\langle{y-x,z-x}\rangle > 0</math>.

Как растёт <math>f(d)</math> относительно <math>d</math>?
{{конец рамки}}

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

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

По состоянию на март 2018 года известно, что <math>2^{d-1}+1 \le f(d) \le 2^d</math>.

=== Смежные задачи ===

==== Множества без тупых углов ====
Следующая задача была поставлена Эрдёшем ещё раньше, чем классическая формулировка задачи Данцера — Грюнбаума<ref name="Эрдёш Мичиган">[https://projecteuclid.org/euclid.mmj/1028997963 The Michigan Mathematical Journal, Volume 4, Issue 3 (1957), 291—300, Paul Erdős, Some unsolved problems] {{Wayback|url=https://projecteuclid.org/euclid.mmj/1028997963 |date=20180603043645 }}, с. 296, задача 19</ref>:

{{рамка}}
Для заданного <math>d</math> обозначим через <math>g(d)</math> максимальное количество различных точек в <math>d</math>-мерном пространстве, никакие три из которых не образуют строго тупого угла, то есть для любых трёх <math>x,y,z</math> из которых выполнено <math>\langle{y-x,z-x}\rangle \ge 0</math>

Как растёт <math>g(d)</math> относительно <math>d</math>?
{{конец рамки}}

Известно, что <math>g(d) = 2^d</math>.

==== Вершины куба ====
В первой по-настоящему прорывной работе по этой теме Эрдёш и Фюреди построили большое множество, удовлетворяющее заданным условиям, из вершин <math>d</math>-мерного куба <math>{\left\lbrace{0,1}\right\rbrace}^{d}</math>. Поэтому в дальнейших работах, улучшающих их результат, иногда рассматривалась отдельно следующая задача:

{{рамка}}
Для заданного <math>d</math> обозначим через <math>f_{\square}(d)</math> максимальное количество различных вершин <math>d</math>-мерного куба <math>\left\lbrace{0,1}\right\rbrace^d</math>, никакие три из которых не образуют ни прямой, ни тупой угол, то есть для любых трёх <math>x,y,z</math> из которых выполнено <math>\langle{y-x,z-x}\rangle  > 0</math>

Как растёт <math>f_{\square}(d)</math> относительно <math>d</math>?
{{конец рамки}}

Очевидно, что <math>f_{\square}(d) \le f(d)</math>.

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

=== Первые упоминания (Эрдёш, 1948, 1957) ===
История задачи начинается в 1948 году, когда в разделе «Дополнительные проблемы для решения» журнала «[[The American Mathematical Monthly]]» [[Пал Эрдёш]] опубликовал следующий частный случай будущей задачи Данцера — Грюнбаума<ref>[https://www.jstor.org/stable/2306142 The American Mathematical Monthly, Vol. 55, No. 7, Aug. — Sep., 1948; Paul Erdos, Problems for Solution 4305-4309] {{Wayback|url=https://www.jstor.org/stable/2306142 |date=20180828072518 }}, с. 431, задача 4306</ref>:

{{рамка}}
Пусть даны восемь точек в пространстве <math>{\mathbb R}^3</math>. Докажите, что всегда можно найти три из них, которые не образуют остроугольный треугольник.
{{конец рамки}}

То есть в задаче спрашивалось, верно ли, что <math>f(3) < 8</math>

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

{{рамка}}
Пусть <math>S</math> — множество из <math>2^d+1</math> точек в пространстве размерности <math>k</math>. Верно ли, что тогда среди них обязательно существуют три точки, образующие тупой угол?
{{конец рамки}}

То есть гипотеза утверждала, что <math>g(d) \le 2^d</math>.

В статье говорились, что для <math>d=3</math> доказательство нашли [[Николас Кёйпер]] и Бьёрдийк (Boerdijk), но их доказательство ещё не опубликовано.

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

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

Или, другими словами, верно ли, что <math>f(3) \ge 6</math> или <math>f(3) \ge 7</math>.<ref name="Эрдёш Мичиган" />

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

: <math>
\begin{pmatrix} 1 & 0 & 0 & \cdots & 0 & 0
\\ -\delta_1 & 1 & 0 & \cdots & 0 & 0
\\ -\delta_1 & -1 & 0 & \cdots & 0 & 0
\\ -\delta_2 & 0 & 1 & \cdots & 0 & 0
\\ -\delta_2 & 0 & -1 & \cdots & 0 & 0
\\ \vdots & \vdots & \ddots & \vdots
\\ -\delta_{d-2} & 0 & 0 & \cdots & 1 & 0
\\ -\delta_{d-2} & 0 & 0 & \cdots & -1 & 0
\\ -\delta_{d-1} & 0 & 0 & \cdots & 0 & 1
\\ -\delta_{d-1} & 0 & 0 & \cdots & 0 & -1
\end{pmatrix}
</math>

где <math>\delta_1,\dots,\delta_{d-1}</math> — попарно различные числа, все меньшие единицы.

Простой комбинаторный перебор разных типов возникающих углов позволяет показать, что никакие три из этих точек не образуют прямых или тупых углов. Из этого следует, что <math>f(d) \ge 2d-1</math>

В этой же работе авторы высказали гипотезу, что большего количества точек, выполняющих это условие, построить нельзя, то есть что <math>f(d)=2d-1</math><ref name=kvant>{{Статья |автор=Райгородский А.М. |заглавие=Остроугольные множества |язык=ru |издание=Квант |год=2018 |выпуск=3 |страницы=10–13}}</ref>.

Также в этой работе была доказана оценка сверху <math>f(d) \le g(d) \le 2^d</math>, которая была ранее предположена Эрдёшем.

=== Применение вероятностного метода (Эрдёш, Фюреди, 1983) ===
В 1983 году [[Пол Эрдёш]] и {{iw|Фюреди, Золтан|Золтан Фюре́ди|en|Zoltán Füredi}}, используя [[вероятностный метод]], опровергли гипотезу Данцера — Грюнбаума, показав, что

: <math>f(d) \ge f_{\square}(d) \ge \left\lfloor{\frac{1}{2} {\left({\frac{2}{\sqrt{3}}}\right)}^{d}}\right\rfloor</math>

Это дало возможность построить контрпримеры к гипотезе Данцера — Грюнбаума для <math>d \ge 35</math>.<ref>{{Cite web |url=https://pdfs.semanticscholar.org/b37c/a9ab34d969877e889e0ba25d5f5303eb36de.pdf |title=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 |access-date=2018-03-19 |archive-date=2018-08-28 |archive-url=https://web.archive.org/web/20180828071359/https://pdfs.semanticscholar.org/b37c/a9ab34d969877e889e0ba25d5f5303eb36de.pdf |deadlink=yes }}</ref>{{sfn|Райгородский|2009|c=8}}

Однако, ввиду особенностей вероятностного метода, их доказательство было неэффективным и не позволяло построить это множество явно (кроме как прямым перебором)<ref name=kvant/>.

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

{{Hider|
  title = Краткое описание идеи доказательства|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =
Доказательство Эрдёша и Фюреди заключалось в том, чтобы выбрать случайным образом и независимо друг от друга <math>2n</math> точек из единичного куба <math>\left\lbrace{0,1}\right\rbrace^d</math>, где <math>n=\left\lfloor{\frac{1}{2} {\left({\frac{2}{\sqrt{3}}}\right)}^d}\right\rfloor</math> и доказать, что при таковым выборе вероятность того, что среди них окажутся лишь <math>n</math> тупоугольных или вырожденных треугольников, положительна.

Под случайным выбором точки здесь имеется в виду её генерация по [[Схема Бернулли|схеме Бернулли]] с вероятностью <math>p=\frac{1}{2}</math> генерации единицы или нуля на той или иной координате точки независимо от остальных координат.

Для доказательства оценки на количество тупоугольных треугольников использовалось свойство линейности математического ожидания. Вероятность того, что конкретная тройка точек образует прямой угол, равна <math>\left({\frac{3}{4}}\right)^d</math> - это легко доказать, рассматривая отдельно вклад каждой координаты в скалярное произведения. Умножая эту вероятность на количество таких троек, получим значение математического ожидания, а это уже даст, согласно [[Неравенство Маркова|неравенству Маркова]], положительную вероятность того, что случайная величина его не превосходит.
}}

=== Улучшения константы в оценке Эрдёша — Фюреди ===

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

Айгнер и Циглер в 2003 году, описывая теорему Эрдёша в своей обзорной книге «[[Доказательства из Книги]]», исправили этот параметр и получили, что <math>f_{\square}(d) \ge 2 \left\lfloor{\frac{\sqrt{6}}{9} {\left({\frac{2}{\sqrt{3}}}\right)}^{d}}\right\rfloor</math>.{{sfn|Айгнер|2006|с=93—94}} Это — лучшее, что можно получить таким способом.

{{Hider|
  title = Доказательство|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =
Метод Эрдёша для количества <math>k</math> выбираемых точек устанавливал, что хотя бы раз среди них найдётся не более <math>3 \binom{k}{3} {\left({\frac{3}{4}}\right)}^n \le \frac{k^3}{2} {\left({\frac{3}{4}}\right)}^d</math> острых углов.

Это гарантирует существование множества из <math>h(k) = k - \frac{k^3}{2} {\left({\frac{3}{4}}\right)}^d</math> точек без прямых и тупых углов.

Если взять производную и прооптимизировать эту функцию по <math>k</math>, то получим

: <math>h'(k) = 1 - \frac{3}{2} {\left({\frac{3}{4}}\right)}^d k^2</math>

: <math>k^2 = \frac{2}{3} {\left({\frac{4}{3}}\right)}^d</math>

: <math>k_{best} = \sqrt{\frac{2}{3}} {\left({\frac{2}{\sqrt{3}}}\right)}^d</math>

: <math>h(k_{best}) = {\left({\frac{2}{\sqrt{3}}}\right)}^d \sqrt{\frac{2}{3}} \left({ 1 - \frac{2}{3} \cdot \frac{1}{2} }\right) = {\left({\frac{2}{\sqrt{3}}}\right)}^d \sqrt{\frac{2}{3}} \cdot \frac{2}{3} = \frac{2 \sqrt{6}}{9} {\left({\frac{2}{\sqrt{3}}}\right)}^d</math>
}}

==== Беван (2006) ====
В 2006 году Д. Беван, немного дополнив конструкцию Эрдёша — Фюреди, улучшил оценку до <math>f(d) \ge 2 \left\lfloor{\frac{1}{3} {\left({\frac{2}{\sqrt{3}}}\right)}^{d+1}}\right\rfloor</math>.<ref>{{Cite web |url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/v13i1r12 |title=D. Bevan, «Sets of Points Determining Only Acute Angles and Some Related Colouring Problems», Electron. J. Combin., 13:1 (2006), 24 p. |access-date=2018-03-19 |archive-date=2018-05-02 |archive-url=https://web.archive.org/web/20180502053848/http://www.combinatorics.org/ojs/index.php/eljc/article/view/v13i1r12 |deadlink=no }}</ref>

Однако точки в его конструкции не были вершинами единичного куба, так что оценку для <math>f_{\square}(d)</math> он не улучшил.

{{Hider|
  title = Краткое описание идеи доказательства|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =
В конструкции Бевана к каждой из выбираемых случайных точек добавлялся очень короткий случайный вектор (для каждой свой), [[Непрерывное равномерное распределение|непрерывно и равномерно распределённый]] в <math>d</math>-мерном кубе <math>[-\varepsilon;\varepsilon]^d</math> для некоторого достаточно малого <math>\varepsilon</math>.

Беван ввёл несколько лемм, показывающих, что некоторые многочлены от равномерно и симметрично относительно нуля распределённых случайных величин (рассматриваемые как новая случайная величина) имеют вероятность быть положительными не меньше, чем <math>\frac{1}{2}</math>. Эти леммы позволили показать, что более, чем в половине случаев, сдвиг на добавочные вектора не делает острым угол между точками, находящимися перед этим под прямым углом (поскольку изменение скалярного произведения, являющегося количественным показателем остроты угла, выражается именно через многочлены от координат добавочных векторов).

Всё это позволило усилить оценку на математическое ожидание количества неострых углов и показать, что среди выбираемых случайно <math>k</math> точек может быть лишь <math>\frac{3}{2} \binom{k}{3} {\left({\frac{3}{4}}\right)}^{n}</math> неострых углов.
}}

Кроме того, Беван получил ряд результатов для малых размерностей <math>d</math>, вследствие чего гипотеза Данцера — Грюнбаума была опровергнута при <math>d \ge 7</math>.<ref name="Бучок, 2009">{{Cite web |url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=9271&option_lang=rus |title=Л. В. Бучок, «Остроугольные треугольники Данцера — Грюнбаума», УМН, 2009, том 64, выпуск 3(387), страницы 181—182 |access-date=2018-03-19 |archive-date=2018-06-03 |archive-url=https://web.archive.org/web/20180603141519/http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=9271&option_lang=rus |deadlink=no }}</ref>

==== Бучок (2009) ====
В 2009 году Лариса Бучок, не изменяя методов Эрдёша, Фюреди и Бевана для генерации точек, подсчитала более аккуратно потери от удаления точек, участвующих в неострых углах. Оказалось, что это позволяет получить следующие оценки<ref name="Бучок, 2009" />:

: <math>f_{\square}(d) \ge \frac{3}{2} \left\lfloor{\frac{11 \sqrt{66}}{243} {\left({\frac{2}{\sqrt{3}}}\right)}^d}\right\rfloor</math>

: <math>f(d) \ge \frac{3}{2} \left\lfloor{\frac{22 \sqrt{33}}{243} {\left({\frac{2}{\sqrt{3}}}\right)}^d}\right\rfloor</math>

{{Hider|
  title = Краткое описание идеи доказательства|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =
Прежде всего Бучок, рассматривая произвольное сгенерированное множество точек, выделила из него те тупоугольные треугольные, которые не пересекаются (по точкам) ни с какими другими. Таких треугольников, очевидно, мало - хотя бы в три раза меньше, чем всех точек.

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

Всё это позволяет, зная, что среди <math>k</math> точек содержится <math>s</math> неострых углов, построить остроугольное множество из <math>k - \frac{k}{3} - \frac{3}{4} \left({s - \frac{k}{3}}\right) = \frac{11}{12} k - \frac{3}{4} s</math> точек в отличие от тривиальной оценки, когда выбирается лишь <math>k-s</math> точек
}}

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

: <math>f(d) \ge \frac{3}{2} \left\lfloor{\frac{11 \sqrt{165}}{243} {\left({\frac{2}{\sqrt{3}}}\right)}^d}\right\rfloor</math>

{{Hider|
  title = Краткое описание идеи доказательства|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =
В этой работе Бучок соединяет идею выбора точек из фиксированного множества и идею добавления небольшого отклонения точек от вершин куба.

Как и в методе Эрдёша и Фюреди, Бучок выбирает точки случайно, и каждую координату независимо, по схеме Бернулли, но не с вероятностями

: <math>P(v_i=0)=P(v_i=1)=\frac{1}{2}</math>

а с большим количество вариантов, с вероятностями

<math>P(v_i=0)=P(v_i=1)=P(v_i=-\varepsilon_i)=P(v_i=1+\varepsilon_i)=\frac{1}{4}</math>

где <math>\varepsilon_1,\dots,\varepsilon_n</math> - достаточно малые числа (отдельное число для каждой координаты), удовлетворяющие условиям

: <math>\sum \limits_{i=1}^{d} {(\varepsilon_i + {\varepsilon_i}^2)} < 1 </math>

: <math>\varepsilon_j^2 > \sum \limits_{i=j+1}^{d} {(\varepsilon_i + {\varepsilon_i}^2)}, 1 \le j \le d-1</math>

Всё это позволяет через перебор 64 вариантов изменения вклада той или иной координаты скаляного произведения снизить вероятность того, что некоторые три точки образуют неострый угол, до <math>\frac{2}{5} {\left({\frac{3}{4}}\right)}^d + \frac{3}{5} {\left({\frac{7}{16}}\right)}^d</math> в отличие от стандартной <math>{\left({\frac{3}{4}}\right)}^d</math> в методе Эрдёша - Фюреди и соответствующим образом снизить математическое ожидание количества неострых углов.

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

: <math>f(d) \ge \frac{2}{3} \left\lfloor{\sqrt{2} {\left({\frac{2}{\sqrt{3}}}\right)}^d}\right\rfloor</math>

{{Hider|
  title = Краткое описание идеи доказательства|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =
В отличие от первого метода из этой же работы, который заключался в изменении самого алгоритма выбора случайных точек, вторым методом предлагался обычный выбор по схеме Эрдёша - Фюреди с вероятностями <math>P(v_i=0)=P(v_i=1)=\frac{1}{2}</math> для каждой координаты каждой точки. Основным выигрышем при этом делалось "умное" пододвигание точек в наилучшей комбинации (с наименьшим числом тупых углов).

Как и в первом методе, точки пододвигались на вектор малой фиксированной длины <math>\varepsilon>0</math> (достаточно взять <math>\varepsilon < \frac{1}{4}</math>) в сторону от куба, но только по одной координате и строго в зависимости от того, существует ли для данной центральной точки тупого угла другие тупые углы, для которых она является боковой точкой (то есть, как и в первой работе Бучок, прямоугольные треугольники подразделялись на пересекающиеся и не пересекающиеся, но анализировались немного иначе, чем в первой работе).

Говоря точнее, все точки наилучшей комбинации подразделялись на четыре класса по удовлетворению свойствам:

* <math>Q_1</math>: все углы с вершиной в данной точке - острые;
* <math>Q_2</math>: точка является вершиной хотя бы одного прямого угла, и все острые углы с вершиной в этой точке принадлежат остроугольным треугольникам;
* <math>Q_3</math>: точка является вершиной хотя бы одного прямого угла и ровно одного острого угла прямоугольного треугольника;
* <math>Q_4</math>: точка является вершиной хотя бы одного прямого угла и не менее чем двух острых углов прмоугольных треугольников.

Точки, удовлетворяющие свойству <math>Q_4</math>, просто удалялись из набора (поскольку их не может быть много), а координаты остальных изменялись, как описано выше.

Как и в первом методе, полный перебор таблицы 64 вариантов вклада той или иной координаты в скалярное произведение давал возможность доказать, что после этих изменений координат во множестве не останется прямоугольных или тупоугольных треугольников.
}}

Доказательство второго из результатов было получено не позже 2009 года, поскольку упоминается в обзоре по этой теме.<ref>{{Cite web |url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=mzm&paperid=6610&option_lang=rus |title=Л. В. Бучок, «О двух новых подходах к получению оценок в проблеме Данцера — Грюнбаума, Матем. заметки, 2010, том 87, выпуск 4, страницы 519—527» |access-date=2018-03-19 |archive-date=2018-05-12 |archive-url=https://web.archive.org/web/20180512043718/http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=mzm&paperid=6610&option_lang=rus |deadlink=no }}</ref>{{sfn|Райгородский|2009|с=21}}

=== Улучшение вероятностной схемы через гиперграфы (Аккерман, Бен-Цви, 2008/2009) ===
Пока другие математики работали над элементарными улучшениями метода Эрдёша, Эйял Аккерман и Орен Бен-Цви независимо от них в 2009 году опубликовали полученное в 2008 году доказательство существования константы <math>c>0</math> такой, что

: <math>f_{\square}(d) \ge c \sqrt{d} {\left({\frac{2}{\sqrt{3}}}\right)}^d</math>

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

Доказательство занимало всего одну страницу и заключалось в применении к конструкции Эрдёша — Фюреди одной доказанной ранее алгоритмической леммы, касающейся размера [[Задача о независимом множестве|независимого множества]] в [[гиперграф]]е при специальных условиях.<ref>[https://www.sciencedirect.com/science/article/pii/S0195669808001947 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]</ref>

{{Hider|
  title = Краткое описание идеи доказательства|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =
Аккерман и Цви использовали частный случай леммы из обзора Бертрам-Кретцберга и Лефманн об алгоритмических аспектах поиска независимых множеств в гиперграфах.<ref>[https://epubs.siam.org/doi/abs/10.1137/S0097539797323716 Claudia Bertram-Kretzberg, Hanno Lefmann, "The Algorithmic Aspects of Uncrowded Hypergraphs", SIAM J. Comput., 29(1), 201–230]</ref> Рассматриваемый частный случай утверждал следующее:

{{рамка}}
Пусть заданы константы <math>c, \varepsilon > 0</math>.

Пусть <math>H</math> - гиперграф, все рёбра которого состоят из трёх вершин, который содержит <math>n</math> вершин и средняя степень вершин которого не превышает <math>t^2</math>, где <math>t \to \infty</math> при <math>n \to \infty</math>.

Пусть также количество пар ребёр типа <math>\left({\left\lbrace{a,b,c}\right\rbrace, \left\lbrace{a,b,d}\right\rbrace}\right)</math> (своего рода "циклов" в смысле гиперграфа) не превышает <math>c n t^{3-\varepsilon}</math>.

Тогда можно за полиномиальное от <math>n</math> время найти в <math>H</math> независимое множество вершин размера <math>\Omega \left({\frac{n \sqrt{\log t}}{t}}\right)</math>
{{конец рамки}}

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

Независимое множество точек в таком гиперграфе как раз и будет множеством, не содержащим тупоугольных треугольников, и оно при выборе параметров <math>n = c_1 {\left({\frac{2}{\sqrt{3}}}\right)}^{\frac{101}{100} d}, t = c_2 {\left({\frac{2}{\sqrt{3}}}\right)}^{\frac{d}{100}}</math> имеет размер <math>\Omega \left({\sqrt{d} {\left({\frac{2}{\sqrt{3}}}\right)}^{d}}\right)</math>
}}

=== Улучшение основания степени (Харанги, 2011) ===
В 2011 году Харанги доказал экспоненциальную оценку с лучшим основанием степени, а именно доказал существование константы <math>c > 0</math> такой, что

: <math>f(n) \ge c {\left({\sqrt[10]{\frac{144}{23}}}\right)}^d > c \cdot 1.201^d</math>

Его доказательство также являлось некоторой модификацией конструкции Эрдёша — Фюреди.<ref>{{Cite web |url=https://epubs.siam.org/doi/abs/10.1137/100808095 |title=Viktor Harangi, «Acute Sets In Euclidean Spaces», SIAM J. Discrete Math., 25(3), 1212—1229 |access-date=2018-03-19 |archive-date=2019-05-31 |archive-url=https://web.archive.org/web/20190531100010/https://epubs.siam.org/doi/abs/10.1137/100808095 |deadlink=no }}</ref>

=== Первая конкретная конструкция (Захаров, 2017) ===
30 апреля 2017 года Дмитрий Захаров, учась в 10 классе и являясь учеником [[Райгородский, Андрей Михайлович|Андрея Райгородского]], опубликовал препринт явной (не вероятностной) конструкции, состоящей из <math>2^{\left\lceil{\frac{d}{2}}\right\rceil}</math> точек, которые образуют только острые углы.

Конструкция Захарова не являлась развитием метода Эрдёша, а использовала новую, простую, описываемую на одной странице, идею.<ref name=kvant/><ref>{{Cite web |url=https://arxiv.org/abs/1705.01171 |title=arXiv:1705.01171 D. Zakharov, «Acute sets» |access-date=2018-03-19 |archive-date=2018-08-28 |archive-url=https://web.archive.org/web/20180828102413/https://arxiv.org/abs/1705.01171 |deadlink=no }}</ref>

В ноябре того же года доказательство было опубликовано в журнале «{{iw|Discrete & Computational Geometry}}».<ref>{{Cite web |url=https://link.springer.com/article/10.1007%2Fs00454-017-9947-y |title=Dmitriy Zakharov, «Acute Sets», «Discrete & Computational Geometry» |access-date=2018-03-19 |archive-date=2018-06-10 |archive-url=https://web.archive.org/web/20180610001603/https://link.springer.com/article/10.1007%2Fs00454-017-9947-y |deadlink=no }}</ref>

{{Hider|
  title = Краткое описание идеи доказательства|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =
Метод Захарова заключался в том, чтобы строить множество точек [[Рекуррентная формула|рекуррентно]]. При этом переход осуществлялся от множества для пространства размерности <math>d</math> ко множеству для пространства размерности <math>d+2</math>

За основу брался принцип построения куба (или параллелепипеда), когда все точки "копируются" и копии переносятся на некоторое расстояние по новому измерению, ортогональному всем отрезкам между точками в предыдущей конструкции (и вообще всем прямым в предыдущем пространстве). Это увеличило бы количество точек в два раза и изменило бы величины имевшихся углов (для углов, точки которых принадлежат разным копиям) лишь ненамного (скалярное произведение изменится не более, чем на величину, пропорциональную квадрату сдвига по новому измерению). Однако при таком построении возникают прямые углы вида <math>\angle{v_2 v_1 w_1}</math>, где <math>v_1</math> и <math>v_2</math> - разные копии одной точки.

Чтобы избавиться от прямых углов, Захаров проводил сдвиг сразу по двум новым измерениям, на вектор одной длины, но в разные стороны, причём двигались по новым измерениям обе копии каждой точки, в отличие от построения куба, когда все точки из предыдущей конструкции остаются в границах прежнего своего пространства. Всё это позволило немного "скосить" возникающие "вертикальные" (протяжённые по новому вводимому измерению) отрезки между точками чтобы избавиться от углов, образуемых ими с отрезками, лежащими исключительно в предыдущем пространстве, меньшей размерности.

Говоря конкретнее, имея множество <math>S</math> в <math>{\mathbb R}^d</math> без прямых и тупых углов, Захаров выбирает для каждой точки <math>x \in S</math> двумерный вектор <math>\phi(x) = \left({\alpha(x),\beta(x)}\right)</math> достаточно малой (и, что важно, одинаковой для всех) длины, причём таким образом, чтобы выполнялось <math>\phi(x) \not = \pm \phi(y)</math> для любых различных <math>x,y \in S</math>. Тогда, при достаточно малой длине векторов <math>\phi(x)</math> удаётся доказать, что точки меножества

: <math>S' = \left\lbrace{(x_1,\dots,x_d,\alpha(x),\beta(x)) : x \in S}\right\rbrace \cup \left\lbrace{(x_1,\dots,x_d,-\alpha(x),-\beta(x)) : x \in S}\right\rbrace</math>

также не образуют прямых или тупых углов (а то, что эти множества не пересекаются. очевидно из построения <math>\phi(x)</math>).

Это доказывает рекуррентную зависимость <math>f(d+2) \ge 2 f(d)</math> и, по [[Математическая индукция|индукции]], всю теорему.
}}

=== Оценка через числа Фиббоначи (Захаров, 2017) ===
В июле 2017 года Захаров опубликовал препринт работы, доказывающей, что

: <math>f(d) > F_n > c {\left({\frac{1 + \sqrt{5}}{2}}\right)}^d > c \cdot 1.618^d</math>

где <math>F_n</math> — <math>n</math>-тое [[Числа Фибоначчи|число Фибоначчи]], а <math>c>0</math> — абсолютная константа.<ref>{{Cite web |url=https://arxiv.org/abs/1707.04829 |title=D. Zakharov, «Acute sets» |access-date=2018-03-19 |archive-date=2018-08-28 |archive-url=https://web.archive.org/web/20180828102345/https://arxiv.org/abs/1707.04829 |deadlink=no }}</ref> Второе неравенство следует из [[Числа Фибоначчи#Формула Бине|формулы Бине]].

{{Hider|
  title = Краткое описание идеи доказательства|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =
Идея была та же, что и в первой работе - копирование точек с последующим сдвигом на достаточно малый двумерный вектор по новым размерностям.

Однако теперь рассматривалась комбинация точек в <math>d</math>-мерном множестве, среди которой <math>f(d-1)</math> точек (максимальное возможное количество) лежали в некоторой одной гиперплоскости <math>H \subset {\mathbb R}^d</math> размерности <math>d-1</math>. Соответственно, операция с копированием и сдвигом осуществлялась только для них, причём новые размерности вводились ортогональными <math>H</math>, так что в результате операции общее количество размерностей увеличивалось лишь на единицу, а для количества точек получалось рекуррентное выражение

: <math>f(n+1) \geq f(n) + f(n-1)</math>
}}

=== Оценка порядка максимума (Геренчер, Харанги, 2017) ===
[[Файл:Gerencser-Harangi scheme.gif|thumb|Пример построения в <math>{\mathbb R}^3</math> по методу Геренчера и Харанги]]

Появление работы Захарова спровоцировало попытки поиска лучших контрпримером для малых размерностей.
Была высказана гипотеза, что <math>f(d) \ge 2^{d-1} + 1</math>, после чего были построены примеры остроугольных множеств, доказывающие, что
: <math>f(4) \ge 9</math>
: <math>f(5) \ge 17</math>
Идеей, использованной при построении этих примеров, было небольшое колебание точек <math>(d-1)</math>-мерного куба в <math>{\mathbb R}^d</math>, в том числе по последней координате, не относящейся к <math>(d-1)</math>-мерному подпространству этого куба.<ref>Улучшено (?) решение Эрдёша по остроугольным треугольникам; копия этой страницы приложена к {{arXiv|0906.0290}}</ref>

Эта идея легко обобщается на старшие размерности, что и проделали Геринчер и Харанги в сентябре 2017 года выпустили статью, доказывающую результат <math>f(d) \ge 2^{d-1}+1</math> для любого <math>d</math>.
Как и решение grizzly их результат позволяет строить остроугольное множество данного размера из точек, сколь угодно близких к вершинам куба (отдалённым от них не более чем на <math>\varepsilon > 0</math>).
Обсуждение на форуме также было упомянуто в этой статье.<ref>{{Cite web |url=https://arxiv.org/abs/1709.03411 |title=arXiv:1709.03411, Balázs Gerencsér, Viktor Harangi, «Acute sets of exponentially optimal size» |access-date=2018-03-19 |archive-date=2018-08-28 |archive-url=https://web.archive.org/web/20180828102424/https://arxiv.org/abs/1709.03411 |deadlink=no }}</ref>

{{Hider|
  title = Краткое описание идеи доказательства|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =
Для формализации доказательства использовались две леммы:

* пододвиганием одной из точек <math>(d-1)</math>-мерного куба на сколь угодно малое расстояние можно сделать острыми все углы, содержавшие эту точку (углы, для которых точка была боковой, исчезают из-за свойств куба, а углы, где эта точка центральна, не становятся тупыми благодаря дополнительному смещению точки по <math>d</math>-той координате);
* для любого конечного множества точек существует <math>\varepsilon > 0</math> такое, что пододвигание любой из точек в любую сторону на расстояние меньше <math>\varepsilon</math> не делает образуемые точками множества острые углы прямыми или тупыми. Это утверждение доказывается через взятие минимума из всех '''положительных''' скалярных произведений отрезков углов между точками из этого множества. Поскольку у "худшего" угла скалярное произведение всё равно будет положительное, то у него есть допустимые границы изменения.

Далее для каждой вершины куба делалось следующее:
* выяснялось, при каком <math>\varepsilon</math> уже имеющиеся острые углы не будут повреждены;
* данная вершина пододвигалась в нужную сторону на вектор длины меньше <math>\varepsilon</math> так, чтобы тупые углы с ней стали острыми.

В конце добавлялась ещё одна точка, очень удалённая от куба по <math>d</math>-той координате, а по остальным совпадающая с центром куба. Углы, образуемые этой точкой с остальными, также оказывались острыми.
}}

== Примечания ==
{{примечания}}

== Литература ==
* {{книга |автор=Райгородский, А. М.. |заглавие=Остроугольные треугольники Данцера — Грюнбаума |место=М. |издательство=МЦНМО |год=2009 |страниц=31 |isbn=978-5-94057-539-9 |ссылка=http://www.mcnmo.ru/free-books/mmmf-lectures/book.36.pdf |ref=Райгородский }} {{Wayback|url=http://www.mcnmo.ru/free-books/mmmf-lectures/book.36.pdf |date=20180508112852 }}
* {{книга|автор=Айгнер М. Циглер Г.|заглавие=Доказательства из Книги. Лучшие доказательства со времен Евклида до наших дней|год=2006|серия=|ссылка=|место=|издательство=Мир|тираж=|страниц=|isbn=|ref=Айгнер}}

[[Категория:Комбинаторная геометрия]]