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

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

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

Для заданного $d$$d$  обозначим через $f(d)$$f(d)$  максимальное количество различных точек в $d$$d$ -мерном пространстве, такие что любые три точки образуют остроугольный треугольник, то есть, для любых трёх $x,y,z$$x,y,z$  скалярное произведение $⟨<!--\; ⟨\; -->y-<!--\; -\; -->x,z-<!--\; -\; -->x⟩<!--\; ⟩\; -->>0$$\langle {y-x,z-x}\rangle >0$ . Как растёт $f(d)$$f(d)$  относительно $d$$d$ ?

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

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

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

Смежные задачиПравить

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

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

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

Известно, что $g(d)=2^d$$g(d)=2^{d}$ .

Вершины кубаПравить

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

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

Очевидно, что $f_{\mathrm{◻<!--\; ◻\; -->}}(d)\le <!--\; \le \; -->f(d)$$f_{\square }(d)\leq f(d)$ .

История изученияПравить

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

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

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

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

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

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

То есть гипотеза утверждала, что $g(d)\le <!--\; \le \; -->2^d$$g(d)\leq 2^{d}$ .

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

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

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

Или, другими словами, верно ли, что $f(3)\ge <!--\; \ge \; -->6$$f(3)\geq 6$  или $f(3)\ge <!--\; \ge \; -->7$$f(3)\geq 7$ .

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

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

${\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}}$ 

где ${\mathrm{\delta <!--\; \delta \; -->}}_1,\dots <!--\; \dots \; -->,{\mathrm{\delta <!--\; \delta \; -->}}_{d-<!--\; -\; -->1}$$\delta _{1},\dots ,\delta _{d-1}$  — попарно различные числа, все меньшие единицы.

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

В этой же работе авторы высказали гипотезу, что большего количества точек, выполняющих это условие, построить нельзя, то есть что $f(d)=2d-<!--\; -\; -->1$$f(d)=2d-1$ .

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

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

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

$f(d)\ge <!--\; \ge \; -->f_{\mathrm{◻<!--\; ◻\; -->}}(d)\ge <!--\; \ge \; -->\lfloor \frac{1}{2}{\left(\frac{2}{\sqrt{3}}\right)}^d\rfloor$$f(d)\geq f_{\square }(d)\geq \left\lfloor {{\frac {1}{2}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}\right\rfloor$ 

Это дало возможность построить контрпримеры к гипотезе Данцера — Грюнбаума для $d\ge <!--\; \ge \; -->35$$d\geq 35$ .

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

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

Краткое описание идеи доказательства

Доказательство Эрдёша и Фюреди заключалось в том, чтобы выбрать случайным образом и независимо друг от друга $2n$$2n$  точек из единичного куба ${\left\{0,1\right\}}^d$$\left\lbrace {0,1}\right\rbrace ^{d}$ , где $n=\lfloor \frac{1}{2}{\left(\frac{2}{\sqrt{3}}\right)}^d\rfloor$$n=\left\lfloor {{\frac {1}{2}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}\right\rfloor$  и доказать, что при таковым выборе вероятность того, что среди них окажутся лишь $n$$n$  тупоугольных или вырожденных треугольников, положительна.

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

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

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

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

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

Айгнер и Циглер в 2003 году, описывая теорему Эрдёша в своей обзорной книге «Доказательства из Книги», исправили этот параметр и получили, что $f_{\mathrm{◻<!--\; ◻\; -->}}(d)\ge <!--\; \ge \; -->2\lfloor \frac{\sqrt{6}}{9}{\left(\frac{2}{\sqrt{3}}\right)}^d\rfloor$$f_{\square }(d)\geq 2\left\lfloor {{\frac {\sqrt {6}}{9}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}\right\rfloor$ . Это — лучшее, что можно получить таким способом.

Доказательство

Метод Эрдёша для количества $k$$k$  выбираемых точек устанавливал, что хотя бы раз среди них найдётся не более $3(\genfrac{}{}{0ex}{}{k}{3}){\left(\frac{3}{4}\right)}^n\le <!--\; \le \; -->\frac{k^3}{2}{\left(\frac{3}{4}\right)}^d$$3{\binom {k}{3}}{\left({\frac {3}{4}}\right)}^{n}\leq {\frac {k^{3}}{2}}{\left({\frac {3}{4}}\right)}^{d}$  острых углов.

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

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

$h^{\prime }(k)=1-<!--\; -\; -->\frac{3}{2}{\left(\frac{3}{4}\right)}^d{k}^2$$h'(k)=1-{\frac {3}{2}}{\left({\frac {3}{4}}\right)}^{d}k^{2}$ 

$k^2=\frac{2}{3}{\left(\frac{4}{3}\right)}^d$$k^{2}={\frac {2}{3}}{\left({\frac {4}{3}}\right)}^{d}$ 

$k_{best}=\sqrt{\frac{2}{3}}{\left(\frac{2}{\sqrt{3}}\right)}^d$$k_{best}={\sqrt {\frac {2}{3}}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}$ 

$h(k_{best})={\left(\frac{2}{\sqrt{3}}\right)}^d\sqrt{\frac{2}{3}}\left(1-<!--\; -\; -->\frac{2}{3}\cdot <!--\; \cdot \; -->\frac{1}{2}\right)={\left(\frac{2}{\sqrt{3}}\right)}^d\sqrt{\frac{2}{3}}\cdot <!--\; \cdot \; -->\frac{2}{3}=\frac{2\sqrt{6}}{9}{\left(\frac{2}{\sqrt{3}}\right)}^d$$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}$ 

Беван (2006)Править

В 2006 году Д. Беван, немного дополнив конструкцию Эрдёша — Фюреди, улучшил оценку до $f(d)\ge <!--\; \ge \; -->2\lfloor \frac{1}{3}{\left(\frac{2}{\sqrt{3}}\right)}^{d+1}\rfloor$$f(d)\geq 2\left\lfloor {{\frac {1}{3}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d+1}}\right\rfloor$ .

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

Краткое описание идеи доказательства

В конструкции Бевана к каждой из выбираемых случайных точек добавлялся очень короткий случайный вектор (для каждой свой), непрерывно и равномерно распределённый в $d$$d$ -мерном кубе $[-<!--\; -\; -->\mathrm{\epsilon <!--\; \epsilon \; -->};\mathrm{\epsilon <!--\; \epsilon \; -->}{]}^d$$[-\varepsilon ;\varepsilon ]^{d}$  для некоторого достаточно малого $\mathrm{\epsilon <!--\; \epsilon \; -->}$$\varepsilon$ .

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

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

Кроме того, Беван получил ряд результатов для малых размерностей $d$$d$ , вследствие чего гипотеза Данцера — Грюнбаума была опровергнута при $d\ge <!--\; \ge \; -->7$$d\geq 7$ .

Бучок (2009)Править

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

$f_{\mathrm{◻<!--\; ◻\; -->}}(d)\ge <!--\; \ge \; -->\frac{3}{2}\lfloor \frac{11\sqrt{66}}{243}{\left(\frac{2}{\sqrt{3}}\right)}^d\rfloor$$f_{\square }(d)\geq {\frac {3}{2}}\left\lfloor {{\frac {11{\sqrt {66}}}{243}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}\right\rfloor$ 

$f(d)\ge <!--\; \ge \; -->\frac{3}{2}\lfloor \frac{22\sqrt{33}}{243}{\left(\frac{2}{\sqrt{3}}\right)}^d\rfloor$$f(d)\geq {\frac {3}{2}}\left\lfloor {{\frac {22{\sqrt {33}}}{243}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}\right\rfloor$ 

Краткое описание идеи доказательства

Прежде всего Бучок, рассматривая произвольное сгенерированное множество точек, выделила из него те тупоугольные треугольные, которые не пересекаются (по точкам) ни с какими другими. Таких треугольников, очевидно, мало - хотя бы в три раза меньше, чем всех точек.

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

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

Бучок (2009/2010)Править

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

$f(d)\ge <!--\; \ge \; -->\frac{3}{2}\lfloor \frac{11\sqrt{165}}{243}{\left(\frac{2}{\sqrt{3}}\right)}^d\rfloor$$f(d)\geq {\frac {3}{2}}\left\lfloor {{\frac {11{\sqrt {165}}}{243}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}\right\rfloor$ 

Краткое описание идеи доказательства

В этой работе Бучок соединяет идею выбора точек из фиксированного множества и идею добавления небольшого отклонения точек от вершин куба.

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

$P(v_i=0)=P(v_i=1)=\frac{1}{2}$$P(v_{i}=0)=P(v_{i}=1)={\frac {1}{2}}$ 

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

$P(v_i=0)=P(v_i=1)=P(v_i=-<!--\; -\; -->{\mathrm{\epsilon <!--\; \epsilon \; -->}}_i)=P(v_i=1+{\mathrm{\epsilon <!--\; \epsilon \; -->}}_i)=\frac{1}{4}$$P(v_{i}=0)=P(v_{i}=1)=P(v_{i}=-\varepsilon _{i})=P(v_{i}=1+\varepsilon _{i})={\frac {1}{4}}$ 

где ${\mathrm{\epsilon <!--\; \epsilon \; -->}}_1,\dots <!--\; \dots \; -->,{\mathrm{\epsilon <!--\; \epsilon \; -->}}_n$$\varepsilon _{1},\dots ,\varepsilon _{n}$  - достаточно малые числа (отдельное число для каждой координаты), удовлетворяющие условиям

$\sum \limits _{i=1}^{d}{(\varepsilon _{i}+{\varepsilon _{i}}^{2})}<1$ 

${\mathrm{\epsilon <!--\; \epsilon \; -->}}_j^2>\underset{i=j+1}{\overset{d}{\sum <!--\; \sum \; -->}}({\mathrm{\epsilon <!--\; \epsilon \; -->}}_i+{{\mathrm{\epsilon <!--\; \epsilon \; -->}}_i}^2),1\le <!--\; \le \; -->j\le <!--\; \le \; -->d-<!--\; -\; -->1$$\varepsilon _{j}^{2}>\sum \limits _{i=j+1}^{d}{(\varepsilon _{i}+{\varepsilon _{i}}^{2})},1\leq j\leq d-1$ 

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

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

$f(d)\ge <!--\; \ge \; -->\frac{2}{3}\lfloor \sqrt{2}{\left(\frac{2}{\sqrt{3}}\right)}^d\rfloor$$f(d)\geq {\frac {2}{3}}\left\lfloor {{\sqrt {2}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}\right\rfloor$ 

Краткое описание идеи доказательства

В отличие от первого метода из этой же работы, который заключался в изменении самого алгоритма выбора случайных точек, вторым методом предлагался обычный выбор по схеме Эрдёша - Фюреди с вероятностями $P(v_i=0)=P(v_i=1)=\frac{1}{2}$$P(v_{i}=0)=P(v_{i}=1)={\frac {1}{2}}$  для каждой координаты каждой точки. Основным выигрышем при этом делалось "умное" пододвигание точек в наилучшей комбинации (с наименьшим числом тупых углов).

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

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

• $Q_1$$Q_1$ : все углы с вершиной в данной точке - острые;
• $Q_2$$Q_{2}$ : точка является вершиной хотя бы одного прямого угла, и все острые углы с вершиной в этой точке принадлежат остроугольным треугольникам;
• $Q_3$$Q_{3}$ : точка является вершиной хотя бы одного прямого угла и ровно одного острого угла прямоугольного треугольника;
• $Q_4$$Q_{4}$ : точка является вершиной хотя бы одного прямого угла и не менее чем двух острых углов прмоугольных треугольников.

Точки, удовлетворяющие свойству $Q_4$$Q_{4}$ , просто удалялись из набора (поскольку их не может быть много), а координаты остальных изменялись, как описано выше.

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

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

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

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

$f_{\mathrm{◻<!--\; ◻\; -->}}(d)\ge <!--\; \ge \; -->c\sqrt{d}{\left(\frac{2}{\sqrt{3}}\right)}^d$$f_{\square }(d)\geq c{\sqrt {d}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}$ 

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

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

Краткое описание идеи доказательства

Аккерман и Цви использовали частный случай леммы из обзора Бертрам-Кретцберга и Лефманн об алгоритмических аспектах поиска независимых множеств в гиперграфах. Рассматриваемый частный случай утверждал следующее:

Пусть заданы константы $c,\mathrm{\epsilon <!--\; \epsilon \; -->}>0$$c,\varepsilon >0$ . Пусть $H$$H$  - гиперграф, все рёбра которого состоят из трёх вершин, который содержит $n$$n$  вершин и средняя степень вершин которого не превышает $t^2$$t^{2}$ , где $t\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}$$t\to \infty$  при $n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}$$n\to \infty$ . Пусть также количество пар ребёр типа $\left(\left\{a,b,c\right\},\left\{a,b,d\right\}\right)$$\left({\left\lbrace {a,b,c}\right\rbrace ,\left\lbrace {a,b,d}\right\rbrace }\right)$  (своего рода "циклов" в смысле гиперграфа) не превышает $cn{t}^{3-<!--\; -\; -->\mathrm{\epsilon <!--\; \epsilon \; -->}}$$cnt^{3-\varepsilon }$ . Тогда можно за полиномиальное от $n$$n$  время найти в $H$$H$  независимое множество вершин размера $\mathrm{\Omega <!--\; \Omega \; -->}\left(\frac{n\sqrt{\log <!--\; \; -->t}}{t}\right)$$\Omega \left({\frac {n{\sqrt {\log t}}}{t}}\right)$

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

Независимое множество точек в таком гиперграфе как раз и будет множеством, не содержащим тупоугольных треугольников, и оно при выборе параметров $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}}$$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}}$  имеет размер $\mathrm{\Omega <!--\; \Omega \; -->}\left(\sqrt{d}{\left(\frac{2}{\sqrt{3}}\right)}^d\right)$$\Omega \left({{\sqrt {d}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}\right)$ 

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

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

$f(n)\ge <!--\; \ge \; -->c{\left(\sqrt[10]{\frac{144}{23}}\right)}^d>c\cdot <!--\; \cdot \; -->{1.201}^d$$f(n)\geq c{\left({\sqrt[{10}]{\frac {144}{23}}}\right)}^{d}>c\cdot 1.201^{d}$ 

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

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

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

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

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

Краткое описание идеи доказательства

Метод Захарова заключался в том, чтобы строить множество точек рекуррентно. При этом переход осуществлялся от множества для пространства размерности $d$$d$  ко множеству для пространства размерности $d+2$$d+2$ 

За основу брался принцип построения куба (или параллелепипеда), когда все точки "копируются" и копии переносятся на некоторое расстояние по новому измерению, ортогональному всем отрезкам между точками в предыдущей конструкции (и вообще всем прямым в предыдущем пространстве). Это увеличило бы количество точек в два раза и изменило бы величины имевшихся углов (для углов, точки которых принадлежат разным копиям) лишь ненамного (скалярное произведение изменится не более, чем на величину, пропорциональную квадрату сдвига по новому измерению). Однако при таком построении возникают прямые углы вида $\mathrm{\angle <!--\; \angle \; -->}{v}_2{v}_1{w}_1$$\angle {v_{2}v_{1}w_{1}}$ , где $v_1$$v_{1}$  и $v_2$$v_{2}$  - разные копии одной точки.

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

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

$S^{\prime }=\left\{(x_1,\dots <!--\; \dots \; -->,x_d,\mathrm{\alpha <!--\; \alpha \; -->}(x),\mathrm{\beta <!--\; \beta \; -->}(x)):x\in <!--\; \in \; -->S\right\}\cup <!--\; \cup \; -->\left\{(x_1,\dots <!--\; \dots \; -->,x_d,-<!--\; -\; -->\mathrm{\alpha <!--\; \alpha \; -->}(x),-<!--\; -\; -->\mathrm{\beta <!--\; \beta \; -->}(x)):x\in <!--\; \in \; -->S\right\}$$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$ 

также не образуют прямых или тупых углов (а то, что эти множества не пересекаются. очевидно из построения $\mathrm{\varphi <!--\; \varphi \; -->}(x)$$\phi(x)$ ).

Это доказывает рекуррентную зависимость $f(d+2)\ge <!--\; \ge \; -->2f(d)$$f(d+2)\geq 2f(d)$  и, по индукции, всю теорему.

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

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

$f(d)>F_n>c{\left(\frac{1+\sqrt{5}}{2}\right)}^d>c\cdot <!--\; \cdot \; -->{1.618}^d$$f(d)>F_{n}>c{\left({\frac {1+{\sqrt {5}}}{2}}\right)}^{d}>c\cdot 1.618^{d}$ 

где $F_n$$F_{n}$  — $n$$n$ -тое число Фибоначчи, а $c>0$$c>0$  — абсолютная константа. Второе неравенство следует из формулы Бине.

Краткое описание идеи доказательства

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

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

$f(n+1)=f(n)+f(n-<!--\; -\; -->1)$$f(n+1)=f(n)+f(n-1)$ 

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

 

Пример построения в ${\mathbb{R}}^3$${\mathbb {R} }^{3}$  по методу Геренчера и Харанги

Появление работы Захарова спровоцировало попытки поиска лучших контрпримером для малых размерностей. Была высказана гипотеза, что $f(d)\ge <!--\; \ge \; -->2^{d-<!--\; -\; -->1}+1$$f(d)\geq 2^{d-1}+1$ , после чего были построены примеры остроугольных множеств, доказывающие, что

$f(4)\ge <!--\; \ge \; -->9$$f(4)\geq 9$ 

$f(5)\ge <!--\; \ge \; -->17$$f(5)\geq 17$ 

Идеей, использованной при построении этих примеров, было небольшое колебание точек $(d-<!--\; -\; -->1)$$(d-1)$ -мерного куба в ${\mathbb{R}}^d$${\mathbb {R} }^{d}$ , в том числе по последней координате, не относящейся к $(d-<!--\; -\; -->1)$$(d-1)$ -мерному подпространству этого куба.

Эта идея легко обобщается на старшие размерности, что и проделали Геринчер и Харанги в сентябре 2017 года выпустили статью, доказывающую результат $f(d)\ge <!--\; \ge \; -->2^{d-<!--\; -\; -->1}+1$$f(d)\geq 2^{d-1}+1$  для любого $d$$d$ . Как и решение grizzly их результат позволяет строить остроугольное множество данного размера из точек, сколь угодно близких к вершинам куба (отдалённым от них не более чем на $\mathrm{\epsilon <!--\; \epsilon \; -->}>0$$\varepsilon >0$ ). Обсуждение на форуме также было упомянуто в этой статье.

Краткое описание идеи доказательства

Для формализации доказательства использовались две леммы:

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

Далее для каждой вершины куба делалось следующее:

• выяснялось, при каком $\mathrm{\epsilon <!--\; \epsilon \; -->}$$\varepsilon$  уже имеющиеся острые углы не будут повреждены;
• данная вершина пододвигалась в нужную сторону на вектор длины меньше $\mathrm{\epsilon <!--\; \epsilon \; -->}$$\varepsilon$  так, чтобы тупые углы с ней стали острыми.

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

ЛитератураПравить

• Райгородский, А. М.. Остроугольные треугольники Данцера — Грюнбаума. — М.: МЦНМО, 2009. — 31 с. — ISBN 978-5-94057-539-9. Архивная копия от 8 мая 2018 на Wayback Machine
• Айгнер М. Циглер Г. Доказательства из Книги. Лучшие доказательства со времен Евклида до наших дней. — Мир, 2006.