タッカーの補題

数学において、タッカーの補題は、アルバート・W・タッカーにちなんで名付けられた、ボルスク・ウラム定理の組み合わせ論的類似物です。

T をn次元閉球の三角形分割とする。T は境界球面上で反対称であると仮定する。つまり、に含まれる T の単体の部分集合は の三角形分割を提供する。ここで、σ が単体であれば −σ も単体である。を 上の奇関数、すなわちすべての頂点 に対して となる T の頂点のラベル付けとする。すると、タッカーの補題によれば、T には相補辺、つまり頂点に同じ番号が付けられているが符号が反対の辺 (1 単体)が含まれる。 ^[1] ${\displaystyle B_{n}}$ ${\displaystyle S_{n-1}}$${\displaystyle S_{n-1}}$${\displaystyle S_{n-1}}$${\displaystyle L:V(T)\to \{+1,-1,+2,-2,...,+n,-n\}}$${\displaystyle S_{n-1}}$${\displaystyle L(-v)=-L(v)}$${\displaystyle v\in S_{n-1}}$

最初の証明は、矛盾を理由とした非構成的なものでした。^[2]

その後、構成的証明が発見され、補完的なエッジを見つけるアルゴリズムも提供されました。^{[3] [4]}基本的に、アルゴリズムはパスベースです。つまり、三角形分割の特定のポイントまたはエッジから開始し、規定のルールに従って単体から単体へと進み、それ以上進めなくなるまで進みます。パスは補完的なエッジを含む単体で終了する必要があることが証明できます。

タッカーの補題のより簡単な証明では、より一般的なKy Fan 補題を使用します。これは、アルゴリズムによる証明が簡単です。

以下の説明は のアルゴリズムを示しています。^[5]この場合 は円盤であり、右上の図のように という4つのラベルが考えられることに注意してください。 ${\displaystyle n=2}$${\displaystyle B_{n}}$${\displaystyle -2,-1,1,2}$

ボールの外側から始めて、境界の頂点のラベルを考えます。ラベル付けは境界上の奇関数であるため、境界には正と負の両方のラベルが必要です。

• 境界に のみ、または のみが含まれる場合、境界上に補完エッジが存在する必要があります。完了。${\displaystyle \pm 1}$${\displaystyle \pm 2}$
• それ以外の場合、境界にはエッジが含まれている必要があります。さらに、境界上のエッジの数は奇数でなければなりません。${\displaystyle (+1,-2)}$${\displaystyle (+1,-2)}$

エッジを選択して通過します。次の 3 つのケースがあります。 ${\displaystyle (+1,-2)}$

• これでシンプレックスになりました。完了です。${\displaystyle (+1,-2,+2)}$
• これでシンプレックスになりました。完了です。${\displaystyle (+1,-2,-1)}$
• 別のエッジを持つ単体にいます。それを通過し、続行します。${\displaystyle (+1,-2)}$

最後のケースでは、ボールの外側に移動できます。ただし、境界上のエッジの数は奇数でなければならないため、境界上には新しい、まだ訪問されていないエッジが存在する必要があります。それを通過し、続行します。 ${\displaystyle (+1,-2)}$${\displaystyle (+1,-2)}$

このウォークは、ボールの内側、または単体で終了する必要があります。完了。 ${\displaystyle (+1,-2,+2)}$${\displaystyle (+1,-2,-1)}$

上で説明したアルゴリズムの実行時間は、三角形分割のサイズに対して多項式です。三角形分割が非常に大きくなる可能性があるため、これは良くないと考えられます。三角形分割のサイズに対して対数的なアルゴリズムを見つけることが望ましいでしょう。しかし、相補辺を見つける問題は、次元に対してもPPA完全です。これは、高速なアルゴリズムを見つける望みがあまりないことを意味します。^[6]${\displaystyle n=2}$

不動点定理には、代数的位相変種、組み合わせ変種、集合被覆変種の 3 つの同等の変種があります。各変種は、まったく異なる議論を使用して個別に証明できますが、各変種は同じ行の他の変種に還元することもできます。さらに、最上行の各結果は、同じ列のその下の行の結果から演繹できます。^[7]

• 位相的組合せ論