Перегляд вихідного коду сторінки Задача Данцера — Ґрюнбаума

'''Задача Данцера&nbsp;— Ґрюнбаума'''&nbsp;— проблема [[Комбінаторна геометрія|комбінаторної геометрії]], що ставить питання про те, яку найбільшу кількість точок можна розмістити в [[Старші розмірності|багатовимірному просторі]], щоб вони не утворювали між собою прямих або тупих кутів. Відомо, що на площині можна розташувати щонайбільше три такі точки, в тривимірному просторі можна розташувати п'ять таких точок. 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>.

=== Суміжні задачі ===

==== Множини без тупих кутів ====
Ердеш ще до появи класичного формулювання задачі Данцера&nbsp;— Ґрюнбаума поставив таку задачу<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] {{Webarchive|url=https://web.archive.org/web/20180603043645/https://projecteuclid.org/euclid.mmj/1028997963 |date=2018-06-03 }}, с. 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]] " [[Пал Ердеш]] опублікував такий окремий випадок майбутньої задачі Данцера&nbsp;— Ґрюнбаума<ref>[https://www.jstor.org/stable/2306142 The American Mathematical Monthly, Vol. 55, No. 7, Aug.&nbsp;— Sep., 1948; Paul Erdos, Problems for Solution 4305-4309] {{Webarchive|url=https://web.archive.org/web/20180828072518/https://www.jstor.org/stable/2306142 |date=2018-08-28 }}, с. 431, задача 4306</ref>:{{Рамка}}
Нехай дано вісім точок у просторі <math>{\mathbb R}^3</math>. Доведіть, що завжди можна знайти три з них, які не утворюють гострокутного трикутника.
{{/рамка}}
Тобто в задачі питалося, чи правильно, що <math>f(3) < 8</math>.

1957 року в журналі {{Не перекладено|Michigan Mathematical Journal}}, у статті з багатьма гіпотезами, Ердеш опублікував уже загальну гіпотезу, але щодо тупокутних множин.
{{Рамка}}
Нехай <math>S</math>&nbsp;— множина з <math>2^d+1</math> точок у просторі розмірності <math>k</math>. Чи правда, що тоді серед них обов'язково існують три точки, що утворюють тупий кут?
{{/рамка}}
Тобто, гіпотеза стверджувала, що <math>g(d) \le 2^d</math>.

У статті говорилося, що для <math>d=3</math> доведення знайшли {{Нп|Ніколас Кейпер|3=en|4=Nicolaas Kuiper}} і Бьордійк (Boerdijk), але їхнє доведення ще не опубліковано.

Поруч із гіпотезою містилося таке питання:
{{Рамка}}
Чи правда, що існує множина зі шести (семи) точок у тривимірному просторі таких, що будь-які три з них утворюють гострий кут?
{{/рамка}}
Або, іншими словами, чи правильно, що <math>f(3) \ge 6</math> або <math>f(3) \ge 7</math>.<ref name="Эрдёш Мичиган"/>

=== Перша гіпотеза (Данцер, Ґрюнбаум, 1962) ===
Першу загальну побудову для розв'язання цієї задачі виконали у статті 1962 року {{Не перекладено|Людвіг Данцер||en|Ludwig Danzer}} та [[Бранко Ґрюнбаум]]. Вони побудували в <math>d</math>-вимірному просторі <math>2d-1</math> точку, матриця координат яких виглядала так (рядки&nbsp;— різні точки, стовпці&nbsp;— різні координати):

: <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>&nbsp;— попарно різні числа, менші від одиниці.

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

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

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

=== Застосування імовірнісного методу (Ердеш, Фюреді, 1983) ===
1983 року [[Пал Ердеш]] і {{Не перекладено|Золтан Фюреді|Золтан Фюре́ді|en|Zoltán Füredi}}, скориставшись [[Імовірнісний метод|імовірнісним методом]], спростували гіпотезу Данцера&nbsp;— Ґрюнбаума, показавши, що

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

Це дозволило побудувати контрприклади до гіпотези Данцера&nbsp;— Ґрюнбаума для <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|accessdate=2018-03-19|archivedate=2018-08-28|archiveurl=https://web.archive.org/web/20180828071359/https://pdfs.semanticscholar.org/b37c/a9ab34d969877e889e0ba25d5f5303eb36de.pdf|deadurl=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> - це легко довести, розглядаючи окремо внесок кожної координати до скалярного добутку. Помноживши цю ймовірність на кількість таких трійок, отримаємо значення математичного сподівання, а це вже дасть, згідно з [[Нерівність Маркова|нерівністю Маркова]], додатну ймовірність того, що випадкова величина його не перевищує.}}

=== Поліпшення сталої в оцінці Ердеша&nbsp;— Фюреді ===

==== Поліпшення без зміни методу ====
Навіть не змінюючи методу Ердеша в самій його суті, можна отримати кращу оцінку, просто вибравши інше число як параметр, який визначає, скільки випадкових точок слід вибирати.

Айґнер і Ціґлер 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}} Це найкраще, що можна отримати в такий спосіб.
{{Hidden|title=Доведення|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 року Д. Беван, трохи доповнивши побудову Ердеша&nbsp;— Фюреді, покращив оцінку до <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.|accessdate=2018-03-19|archivedate=2018-05-02|archiveurl=https://web.archive.org/web/20180502053848/http://www.combinatorics.org/ojs/index.php/eljc/article/view/v13i1r12|deadurl=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>, що спростувало гіпотезу Данцера&nbsp;— Ґрюнбаума для <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|accessdate=2018-03-19|archivedate=2018-06-03|archiveurl=https://web.archive.org/web/20180603141519/http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=9271&option_lang=rus|deadurl=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>
{{Hidden|title=Короткий опис ідеї доведення|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>
{{Hidden|title=Короткий опис ідеї доведення|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>
{{Hidden|title=Краткое описание идеи доказательства|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»|accessdate=2018-03-19|archivedate=2018-05-12|archiveurl=https://web.archive.org/web/20180512043718/http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=mzm&paperid=6610&option_lang=rus|deadurl=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>

Це стало першим [[Асимптотична рівність|асимптотичним покращенням]] оцінки від часу статті Ердеша&nbsp;— Фюреді.

Доказ займало лише одну сторінку і полягало в застосуванні до побудови Ердеша&nbsp;— Фюреді однієї доведеної раніше алгоритмічної леми, яка стосується розміру [[Задача про незалежну множину|незалежної множини]] в [[гіперграф]]і за особливих умов<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>.

{{Hidden|title=Короткий опис ідеї доведення|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>&nbsp;— гіперграф, усі ребра якого складаються з трьох вершин, який містить <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>
{{/рамка}}

Автори використали побудову Ердеша&nbsp;— Фюреді, не змінюючи алгоритму вибору точок. Але поряд із математичним сподіванням кількості негострокутних трикутників вони порахували також математичне сподівання кількості циклів (у згаданому вище сенсі) в гіперграфі, ребра якого відповідають трійкам точок, що утворюють прямі або тупі кути (це підраховується через лінійність математичного сподівання кутів, але через розгляд не трійок точок, а четвірок).

Незалежна множина точок у такому гіперграфі якраз і буде множиною, що не містить тупокутних трикутників, і вона при виборі параметрів <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>

Його доведення також було деякою модифікацією побудови Ердеша&nbsp;— Фюреді<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|accessdate=2018-03-19|archivedate=2019-05-31|archiveurl=https://web.archive.org/web/20190531100010/https://epubs.siam.org/doi/abs/10.1137/100808095|deadurl=no}}</ref>.

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

Побудова Захарова не була розвитком методу Ердеша, а використовувала нову, просту, описану на одній сторінці, ідею<ref>{{Cite web|url=https://arxiv.org/abs/1705.01171|title=arXiv:1705.01171 D. Zakharov, «Acute sets»|accessdate=2018-03-19|archivedate=2018-08-28|archiveurl=https://web.archive.org/web/20180828102413/https://arxiv.org/abs/1705.01171|deadurl=no}}</ref><ref name="kvant"/>.

У листопаді того ж року доведення опубліковано в журналі "{{Не перекладено|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»|accessdate=2018-03-19|archivedate=2018-06-10|archiveurl=https://web.archive.org/web/20180610001603/https://link.springer.com/article/10.1007%2Fs00454-017-9947-y|deadurl=no}}</ref>.

{{Hidden|title=Короткий опис ідеї доведення|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>&nbsp;— <math>n</math>-не [[Числа Фібоначчі|число Фібоначчі]], а <math>c>0</math>&nbsp;— абсолютна стала.<ref>{{Cite web|url=https://arxiv.org/abs/1707.04829|title=D. Zakharov, «Acute sets»|accessdate=2018-03-19|archivedate=2018-08-28|archiveurl=https://web.archive.org/web/20180828102345/https://arxiv.org/abs/1707.04829|deadurl=no}}</ref> Друга нерівність випливає з [[Послідовність Фібоначчі#Формула Біне|формули Біне]].

{{Hidden|title=Короткий опис ідеї доведення|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) = f(n) + f(n-1)</math>}}

=== Оцінка порядку максимуму (Геренчер, Харангі, 2017) ===
[[Файл:Gerencser-Harangi_scheme.gif|міні| Приклад побудови в <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»|accessdate=2018-03-19|archivedate=2018-08-28|archiveurl=https://web.archive.org/web/20180828102424/https://arxiv.org/abs/1709.03411|deadurl=no}}</ref><ref>{{Cite web|title=Посетители форума улучшили оценку Эрдёша|url=https://nplus1.ru/news/2017/09/13/erdos-forum|website=N + 1 — главное издание о науке, технике и технологиях|accessdate=2024-01-22|language=ru|first=Дмитрий|last=Трунин}}</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>-тою координатою, яка за рештою координат збігалася з центром куба. Кути, утворені цією точкою з іншими, також виявлялися гострими.}}

== Примітки ==
{{примітки|2}}

== Література ==

* {{Книга
|автор = Райгородский, А. М..
|заголовок = Остроугольные треугольники Данцера — Грюнбаума
|місце = М.
|видавництво = МЦНМО
|рік = 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 = Айгнер
|назва = Доказательства из Книги. Лучшие доказательства со времен Евклида до наших дней
}}
[[Категорія:Дискретна геометрія]]