マクマレン問題

マクマレン問題は、ピーター・マクマレンにちなんで名付けられた離散幾何学における未解決問題です。

1972年にデイビッド・G・ラーマンは次のような問題について書いた。^[1]

次元アフィン空間の一般的な位置にある任意の点に対して、これらの点を凸位置にマッピングする射影変換が存在するような最大の数を決定します（つまり、それらは凸多面体の頂点を形成します）。${\displaystyle \nu (d)}$${\displaystyle \nu (d)}$${\displaystyle d}$${\displaystyle \mathbb {R} ^{d}}$

ラーマン氏は、この問題はピーター・マクマレン氏による私的な通信によるものだと主張した。

ゲイル変換を使用すると、この問題は次のように再定式化できます。

球面上の線形一般位置にある点 のあらゆる集合に対して、に対してとなる集合を選択することが可能であり、 のすべての開半球に の少なくとも 2 つの要素が含まれるような最小の数を決定します。${\displaystyle \mu (d)}$${\displaystyle \mu (d)}$${\displaystyle X=\{x_{1},x_{2},\dots ,x_{\mu (d)}\}}$${\displaystyle S^{d-1}}$${\displaystyle Y=\{\varepsilon _{1}x_{1},\varepsilon _{2}x_{2},\dots ,\varepsilon _{\mu (d)}x_{\mu (d)}\}}$${\displaystyle \varepsilon _{i}=\pm 1}$${\displaystyle i=1,2,\dots ,\mu (d)}$${\displaystyle S^{d-1}}$${\displaystyle Y}$

マクマレン問題の元の定式化とゲール変換定式化の数値は、次の関係で結びついている。 ${\displaystyle \nu }$${\displaystyle \mu }$$${\displaystyle {\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}}}$$

また、単純な幾何学的観察により、次のように再定式化することもできます。

の点の集合ごとに、を2つの 集合に分割し、${\displaystyle \lambda (d)}$${\displaystyle X}$${\displaystyle \lambda (d)}$${\displaystyle \mathbb {R} ^{d}}$${\displaystyle X}$${\displaystyle A}$${\displaystyle B}$$${\displaystyle \operatorname {conv} (A\backslash \{x\})\cap \operatorname {conv} (B\backslash \{x\})\not =\varnothing ,\forall x\in X.\,}$$

と の関係は ${\displaystyle \mu }$${\displaystyle \lambda }$$${\displaystyle \mu (d+1)=\lambda (d),\qquad d\geq 1\,}$$

マクマレン問題と同等の射影双対ステートメントは、 d次元実射影空間の一般的な位置にある超平面のすべてのセットが、セルの 1 つがすべての超平面によって囲まれる超平面の配置を形成するような最大数を決定することです。 ${\displaystyle \nu (d)}$${\displaystyle \nu (d)}$

この問題はまだ未解決です。ただし、 の境界は次の結果に示されています。 ${\displaystyle \nu (d)}$

• デイヴィッド・ラーマンは1972年に^{[1]を証明した。} $${\displaystyle 2d+1\leq \nu (d)\leq (d+1)^{2}.}$$
• ミシェル・ラス・ベルニャスは1986 年に次のことを証明しました^[2] $${\displaystyle \nu (d)\leq {\frac {(d+1)(d+2)}{2}}.}$$
• ホルヘ・ルイス・ラミレス・アルフォンシンは 2001 年に次のことを証明しました^[3] $${\displaystyle \nu (d)\leq 2d+\left\lceil {\frac {d+1}{2}}\right\rceil .}$$

この問題の予想は です。これは に対して証明されています。^{[1] [4]}${\displaystyle \nu (d)=2d+1}$${\displaystyle d=2,3,4}$