ペルムトヘドロン

数学において、 $n次$ パーミュトヘドロン（ permutahedronとも綴る）は、 $n$ 次元空間に埋め込まれた $($ $n$ $- 1)$ 次元多面体である。その頂点座標（ラベル）は、最初の $n 個の$ 自然数の順列である。辺は、2 つの頂点（順列）を接続する最短経路（転置の集合）を識別する。辺で接続された 2 つの順列は、2 か所のみ異なり（1 つの転置）、これらの場所の数は近傍である（値が 1 だけ異なる）。

右の画像は、切頂八面体である 4 次順の順列八面体を示しています。その頂点は $(1, 2, 3, 4)$ の 24 通りの順列です。平行な辺は同じ色です。6 つの辺の色は、4 つの要素の 6 つの可能な転置に対応しています。つまり、接続された順列がどの 2 つの場所で異なるかを示しています。(たとえば、赤い辺は最後の 2 つの場所で異なる順列を接続します。)

歴史

ギュンター・M・ツィーグラー（1995）によると、ペルムトヘドラはピーター・ヘンドリック・スハウテ（1911）によって初めて研究された。ペルムトエドラ という名前はジョルジュ・Th・ギルボーとピエール・ローゼンスティール（1963）によって作られた。彼らはこの言葉を野蛮だが覚えやすいと表現し、読者の批判にさらしている。^[1]

別の綴りであるpermut a hedronも時々使用される。^[2]パーミュトヘドラは、順列多面体と呼ばれることもあるが、この用語は、順列行列の凸包として定義される関連するバーコフ多面体にも使用される。より一般的には、V.ジョセフ・ボウマン (1972) は、頂点がある集合の順列と一対一になる多面体に対してこの用語を使用している。

頂点、辺、面

$n$ 次パーミュトヘドロンには $n!$ 個の頂点があり、各頂点は $n - 1$ 個の頂点と隣接しています。辺の数は $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠( n − 1) n !/2⁠$ 、長さは√2 $です。$

2つの接続された頂点は、値が1異なる2つの座標を交換することで異なります。^[3]交換された場所のペアは、エッジの方向に対応します。（例の画像では、頂点 $（3、2、1、4）$ と $（2、3、1、4）$ は青いエッジで接続されており、最初の2つの場所で2と3を交換することで異なります。値2と3は1異なります。すべての青いエッジは、最初の2つの場所の座標の交換に対応しています。）

ファセットの数は $2 n - 2$ です。なぜならそれらは ${1 ...$ $n$ $}$ の空でない真部分集合 $Sに対応するからです。部分集合$ $S$ に対応するファセットの頂点は、 $S$ 内の場所の座標が他の頂点よりも小さいという共通点があります。^[4]

より一般的には、次元 0 (頂点) から $n$ $- 1$ (パーミュトヘドロン自体)までの面は、集合 ${1 ...$ $n$ $}の$ 厳密な弱い順序に対応します。したがって、すべての面の数は $n$ 番目の順序ベル数です。^[5] 次元 $dの面は、$ $k$ $=$ $n$ $-$ $d$ 同値類を持つ順序に対応します。

$n$ 次のパーミュトヘドロンにおける次元 $d = n - k$ の面の数は、三角形 $T$ （OEISのシーケンスA019538）で与えられます。ここで、は第二種スターリング数を表します。 $T(n,k)=k!\cdot \left\{{n \atop k}\right\}$ $\textstyle \left\{{n \atop k}\right\}$

右側には、行の合計、つまり順序付けられたベル数とともに表示されます。

その他のプロパティ

パーミュトヘドロンには頂点推移性があります。対称群 $S n は$ 座標の置換によってパーミュトヘドロンに作用します。

パームトヘドロンはゾノトープであり、パームトヘドロンの平行移動コピーは、標準基底ベクトルのペアを結ぶ $n$ $（$ $n$ $-1）/2$ 個の線分のミンコフスキー和として生成することができます。^[6]

パーミュトヘドロンの頂点と辺は、対称群のケイリーグラフの1つ、つまり連続する要素を交換する転置によって生成されるグラフと同型である。ケイリーグラフの頂点は、パーミュトヘドロンの頂点の逆順列である。 ^[7]右の図は、 $S$ $4$ のケイリーグラフを示している。辺の色は、3つの生成転置（1, 2）、（2, 3）、（3, 4）を表す。

このケイリーグラフはハミルトングラフです。ハミルトンサイクルはシュタインハウス・ジョンソン・トロッターアルゴリズムによって見つけることができます。

空間のモザイク化

3次および4次のパーミュトヘドラによる空間のモザイク化

$n$ 次の置換面体は、座標の合計が次の数になるすべての点からなる $(n - 1)$ 次元超平面内に完全に位置する。

$1+2+\ldots +n={\frac {n(n+1)}{2}}$

さらに、この超平面は、無限に多くの変換されたパーミュトヘドロンのコピーでタイル張りすることができます。それらのそれぞれは、特定の $($ $n$ $- 1)$ 次元格子の要素によって基本的なパーミュトヘドロンとは異なります。この格子は、合計がゼロで剰余( $nを法とする) がすべて等しい$ $n$ 組の整数で構成されます。 ${\begin{aligned}&x_{1}+x_{2}+\ldots +x_{n}=0\\&x_{1}\equiv x_{2}\equiv \ldots \equiv x_{n}{\pmod {n}}.\end{aligned}}$

これは格子であり、ルート格子の双対格子である。言い換えれば、パーミュトヘドロンはのボロノイセルである。したがって、この格子はパーミュトヘドラル格子と呼ばれることもある。^[8] $A_{n-1}^{*}$ $A_{n-1}$ $A_{n-1}^{*}$

このように、上に示した4次のパーミュトヘドロンは、平行移動によって3次元空間を敷き詰めます。ここで、3次元空間は、合計が10である実数の4つの組で構成される、座標 $x$ $、$ $y$ $、$ $z$ $、$ $w$ を持つ4次元空間のアフィン部分空間です。 $\mathbb {R} ^{4}$

$x+y+z+w=10.$

次の4つのベクトルのそれぞれについて、

$(1,1,1,-3),\ (1,1,-3,1),\ (1,-3,1,1),\ (-3,1,1,1),$

座標の合計はゼロで、すべての座標は 1 (mod 4) に一致します。これらのベクトルの任意の 3 つが変換格子を生成します。

このようにして、次数 2、次数 3、次数 4 のパーミュトヘドラから形成されるテッセレーションは、それぞれ、アペイロゴン、正六角形タイリング、および二分円立方ハニカムです。双対テッセレーションには、次数 3 を超える正多面体ではありませんが、すべての単体面が含まれています。

例

参照

注記

^ フランス語原文: 「le mot permutoèdre est barbare, mais il est facile à retenir; soumettons-le aux critiques des lecteurs」。
^ トーマス（2006年）。
^ ガイハ＆グプタ（1977年）。
^ Lancia (2018)、p. 105（「Permutahedron」の章を参照）。
^ 例えば、Ziegler (1995)、p. 18を参照。
^ ジーグラー（1995）、200ページ。
^ このケイリーグラフのラベル付けは、例えばZiegler (1995)によって示されています。
^ Baek、Adams、Dolson（2013年）。

参考文献

Baek, Jongmin; Adams, Andrew; Dolson, Jennifer (2013)、「格子ベースの高次元ガウスフィルタリングとパームトヘドラル格子」、Journal of Mathematical Imaging and Vision、46 (2): 211–237、doi :10.1007/s10851-012-0379-2、hdl : 1721.1/105344、MR 3061550
ボウマン、V. ジョセフ (1972)、「順列多面体」、SIAM 応用数学ジャーナル、22 (4): 580–589、doi :10.1137/0122054、JSTOR 2099695、MR 0305800。
ガイハ、プラバ; グプタ、SK (1977)、「パームトヘドロン上の隣接頂点」、SIAM Journal on Applied Mathematics、32 (2): 323–327、doi :10.1137/0132025、JSTOR 2100417、MR 0427102。
ギルボー、ジョルジュ Th.ローゼンシュティール、ピエール(1963)、「分析における代数の精査」、数学と科学、人類、4 : 9–33。
ランチア、ジュゼッペ（2018）、コンパクト拡張線形計画モデル、シャム、スイス：シュプリンガー、ISBN 978-3-319-63975-8。
Schoute、Pieter Hendrik (1911)、「規則的なポリトープから規則的に派生したポリトープの分析処理」、Verhandelingen der Koninklijke Akademie van Wetenschappen te Amsterdam、11 (3): 87 ppGooglebook、370～381 KNAW デジタルライブラリでもオンラインで公開されています (http://www.dwc.knaw.nl/toegangen/digital-library-knaw/?pagetype=publDetail&pId=PU00011495)
Thomas, Rekha R. (2006)、「第 9 章順列面体」、幾何学的組合せ論の講義、学生数学図書館: IAS/Park City 数学サブシリーズ、第 33 巻、アメリカ数学会、pp. 85–92、ISBN 978-0-8218-4140-2。
ジーグラー、ギュンター・M.（1995）、多面体に関する講義、シュプリンガー・フェアラーク、数学大学院テキスト152。

さらに読む

ル・コント・ド・ポリ＝バルビュット、Cl. (1990)、「製品のダイアグラムの交差を示す図」、数学、情報科学、人間科学、112 : 49–53。
ポストニコフ、アレクサンダー (2009)、「ペルムトヘドラ、アソシアヘドラ、そしてそれ以上」、国際数学研究通知、2009 ( 6): 1026–1106 、arXiv : math.CO/0507163、doi:10.1093/imrn/rnn153、MR 2487491
サントマイヤー、ジョー (2007)、「すべての可能な距離については、パームトヘドロンをご覧ください」、数学雑誌、80 (2): 120–125、doi :10.1080/0025570X.2007.11953465

外部リンク

ブライアン・ジェイコブス、「Permutohedron」、MathWorld

[1] フランス語原文: 「le mot permutoèdre est barbare, mais il est facile à retenir; soumettons-le aux critiques des lecteurs」。

[2] トーマス（2006年）。

[3] ガイハ＆グプタ（1977年）。

[4] Lancia (2018)、p. 105（「Permutahedron」の章を参照）。

[zface-5] 例えば、Ziegler (1995)、p. 18を参照。

[FOOTNOTEZiegler1995200-6] ジーグラー（1995）、200ページ。

[7] このケイリーグラフのラベル付けは、例えばZiegler (1995)によって示されています。

[FOOTNOTEBaekAdamsDolson2013-8] Baek、Adams、Dolson（2013年）。