Проблема Макмаллена

Нерешенная задача по математике :

Для скольких точек всегда возможно проективно перевести точки в выпуклое положение?

(еще нерешенные задачи по математике)

Проблема Макмаллена — открытая задача дискретной геометрии, названная в честь Питера Макмаллена .

Заявление

В 1972 году Дэвид Ларман написал о следующей проблеме:

Определить наибольшее число $\nu (d)$ такой, что для любого данного $\nu (d)$ точки общего положения в $d$-мерное аффинное пространство $\mathbb {R} ^{d}$ существует проективное преобразование, переводящее эти точки в выпуклое положение (поэтому они образуют вершины выпуклого многогранника ).

Ларман приписал проблему частному сообщению Питера Макмаллена.

Эквивалентные составы

Преобразование Гейла

Используя преобразование Гейла , эту задачу можно переформулировать так:

Определить наименьшее число $\mu (d)$ такая, что для каждого набора $\mu (d)$ очки $X=\{x_{1},x_{2},\dots ,x_{\mu (d)}\}$ в линейно общем положении на сфере $S^{d-1}$ можно выбрать комплект $Y=\{\varepsilon _{1}x_{1},\varepsilon _{2}x_{2},\dots ,\varepsilon _{\mu (d)}x_{\mu (d)}\}$ где $\varepsilon _{i}=\pm 1$ для $i=1,2,\dots ,\mu (d)$, так что каждое открытое полушарие $S^{d-1}$ содержит не менее двух членов $Y$.

Числа $\nu$ исходной формулировки проблемы Макмаллена и $\mu$ формулировки преобразования Гейла связаны соотношениями $${\begin{aligned}\mu (k)&=\min\{w\mid w\leq \nu (w-k-1)\}\\\nu (d)&=\max\{w\mid w\geq \mu (w-d-1)\}\end{aligned}}$$

Разделение на почти непересекающиеся корпуса

Кроме того, путем простого геометрического наблюдения, его можно переформулировать так:

Определить наименьшее число $\lambda (d)$ такой, что для каждого набора $X$ из $\lambda (d)$ указывает на $\mathbb {R} ^{d}$ существует раздел ​ $X$ на два набора $A$ и $B$ с $$\operatorname {conv} (A\backslash \{x\})\cap \operatorname {conv} (B\backslash \{x\})\not =\varnothing ,\forall x\in X.\,$$

Отношения между $\mu$ и $\lambda$ является $$\mu (d+1)=\lambda (d),\qquad d\geq 1\,$$

Проективная двойственность

Расположение линий, двойственное правильному пятиугольнику. В каждой пятистрочной проективной схеме, подобной этой, есть ячейка, которой касаются все пять линий. Однако добавление линии на бесконечности дает расположение из шести линий с шестью гранями пятиугольника и десятью гранями треугольника; ни одно лицо не затрагивается всеми линиями. Следовательно, решением проблемы Макмаллена для d = 2 является ν = 5.

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

Результаты

Эта проблема все еще открыта. Однако границы $\nu (d)$ заключаются в следующих результатах:

• Дэвид Ларман доказал в 1972 году, что $$2d+1\leq \nu (d)\leq (d+1)^{2}.$$
• Мишель Лас Верньяс доказал в 1986 году, что $$\nu (d)\leq {\frac {(d+1)(d+2)}{2}}.$$
• Хорхе Луис Рамирес Альфонсин доказал в 2001 году, что $$\nu (d)\leq 2d+\left\lceil {\frac {d+1}{2}}\right\rceil .$$

Гипотеза этой проблемы заключается в том, что $\nu (d)=2d+1$. Это было доказано для $d=2,3,4$.