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

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

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

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

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

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

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

${\displaystyle h'(k)=1-{\frac {3}{2}}{\left({\frac {3}{4}}\right)}^{d}k^{2}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle P(v_{i}=0)=P(v_{i}=1)=P(v_{i}=-\varepsilon _{i})=P(v_{i}=1+\varepsilon _{i})={\frac {1}{4}}}$

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

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

${\displaystyle \varepsilon _{j}^{2}>\sum \limits _{i=j+1}^{d}{(\varepsilon _{i}+{\varepsilon _{i}}^{2})},1\leq j\leq d-1}$

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

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

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

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

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

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

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

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

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

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

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

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

За основу брался принцип построения куба (или параллелепипеда), когда все точки "копируются" и копии переносятся на некоторое расстояние по новому измерению, ортогональному всем отрезкам между точками в предыдущей конструкции (и вообще всем прямым в предыдущем пространстве). Это увеличило бы количество точек в два раза и изменило бы величины имевшихся углов (для углов, точки которых принадлежат разным копиям) лишь ненамного (скалярное произведение изменится не более, чем на величину, пропорциональную квадрату сдвига по новому измерению). Однако при таком построении возникают прямые углы вида ${\displaystyle \angle {v_{2}v_{1}w_{1}}}$, где ${\displaystyle v_{1}}$ и ${\displaystyle v_{2}}$ - разные копии одной точки.

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

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

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

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

Это доказывает рекуррентную зависимость ${\displaystyle f(d+2)\geq 2f(d)}$ и, по индукции, всю теорему.

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

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

${\displaystyle f(n+1)=f(n)+f(n-1)}$

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

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

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

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

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