分離可能な順列

組合せ数学において、分離可能順列とは、自明な順列 1 から直和と歪和で得られる順列のことである。^{[1]分離可能順列は、禁制}順列パターン2413 と 3142によって特徴付けられる。 ^{[2]分離可能順列は、}順列グラフがコグラフである順列や、直列-並列半順序を実現する順列でもある。与えられた分離可能順列がより大きな順列のパターンであるかどうかを多項式時間でテストしたり、2 つの分離可能順列の最長共通サブパターンを見つけたりすること が可能である。

Bose、Buss、Lubiw (1998) は、分離可能な順列を、分離木を持つ順列と定義しています。分離木とは、順列の要素が (順列の順序で) 木の葉に現れ、各木ノードの子孫がこれらの要素の連続したサブセットを形成する根付き二分木です。木の各内部ノードは、左の子のすべての子孫が右のノードのすべての子孫よりも小さい正のノード、または左のノードのすべての子孫が右のノードのすべての子孫よりも大きい負のノードのいずれかです。特定の順列に対して複数の木が存在する場合があります。同じ木で隣接する 2 つのノードが同じ符号を持つ場合、木の回転操作を使用して、異なるノードのペアに置き換えることができます。

分離木の各サブツリーは、それ自体が、より小さな分離可能な順列を表すと解釈できます。その要素の値は、サブツリーの形状と符号パターンによって決まります。1 ノードのツリーは、自明な順列を表します。ルート ノードが正であるツリーは、その 2 つの子サブツリーによって与えられる順列の直和を表します。ルート ノードが負であるツリーは、その 2 つの子サブツリーによって与えられる順列の歪和を表します。このように、分離木は、自明な順列から始めて、直和と歪和による順列の構築と同等です。

Bose、Buss、Lubiw（1998）が証明しているように、分離可能な順列は順列パターンの観点からも特徴付けられる。つまり、順列が分離可能であるのは、パターンとして2413も3142も含まれていない場合のみである。^[2]

分離可能な順列は代数幾何学からの特徴も持っています。異なる実多項式の集合が、ある数値xにおいてすべて等しい値を持つ場合、多項式の数値順序がxにおいてどのように変化するかを記述する順列は分離可能であり、すべての分離可能な順列はこのように実現できます。^[3]

分離可能な順列はシュレーダー数で列挙される。つまり、長さ1の分離可能な順列は1つ、長さ2の分離可能な順列は2つ存在し、一般に、与えられた長さ（長さ1から始まる）の分離可能な順列の数は

1、2、6、22、90、394、1806、8558、....（OEISの配列A006318）

この結果は、分離可能順列と等価な順列行列のクラスに対して、各ノードの右の子ノードがノード自体とは異なる符号を持つ分離ツリーの標準形式を使用し、これらのツリーに生成関数の理論を適用することによって、シャピロとスティーブンス（1991）によって証明されました。分離可能順列自体にもっと直接適用する別の証明は、ウェスト（1995）によって与えられました。^[4]

Bose、Buss、Lubiw (1998) は、分離不可能な順列の場合はNP 完全であるのに対し、分離可能な順列がより大きな順列のパターンであるかどうかを多項式時間で判定できることを示しました。

入力順列の集合に共通する最長の分離可能なパターンを見つける問題は、入力順列の数が固定されている場合は多項式時間で解けるかもしれないが、入力順列の数が可変である場合はNP困難であり、入力がすべて分離可能である場合でもNP困難のままである。^[5]

分離可能な順列は、Avis と Newborn (1981) の研究で初めて登場しました。彼らは、分離可能な順列が、任意の数のポップ スタックを連続して並べることでソートできる順列であることを示しました。ポップ スタックとは、任意のポップ操作で一度にすべての項目がポップされるスタックの制限された形式です。

Shapiro と Stephens (1991) は、ブートストラップ パーコレーションの研究で、分離可能な順列を再度検討しました。ブートストラップ パーコレーションとは、 2 つ以上の直交近傍が 1 である任意の行列係数を繰り返し 1 つに変更することによって、初期の順列行列を修正するプロセスです。彼らが示すように、このプロセスによってすべてが 1 の行列に変換される順列のクラスは、まさに分離可能な順列のクラスです。

「分離可能な順列」という用語は、後にアルゴリズムの特性を考慮した Bose、Buss、Lubiw (1998) によって導入されました。

すべての順列は、順列グラフを定義するために使用できます。順列グラフとは、頂点が順列の要素であり、辺が順列の反転であるグラフです。分離可能な順列の場合、このグラフの構造は、順列の分離木から読み取ることができます。グラフの2つの頂点は、分離木におけるそれらの最低共通祖先が負である場合にのみ隣接しています。このようにして木から形成できるグラフはコグラフ（補数還元可能グラフの略）と呼ばれ、それらが形成される木はコツリーと呼ばれます。したがって、分離可能な順列は、まさに順列グラフがコグラフである順列です。^{[6]コグラフ（4頂点}誘導パスを持たないグラフ）の禁制グラフの特徴付けは、分離可能な順列の2つの4要素禁制パターンに対応します。

分離可能な順列は、比較グラフがコグラフである半順序集合である直列並列半順序とも密接に関連しています。コグラフや分離可能な順列と同様に、直列並列半順序も 4 要素の禁制部分順序によって特徴付けられる場合があります。すべての順列は、順序次元が 2 である半順序を定義します。この半順序では、順序付けされる要素は順列の要素であり、x の数値がyより小さく、順列内で y の左側にある場合は常にx  ≤  yです。この半順序が直列並列である順列は、まさに分離可能な順列です。

分離可能な順列は、長方形を小さな長方形に階層的に分割する（いわゆる「スライスフロアプラン」、集積回路の設計などで使用される）ことを記述するためにも使用される。分離ツリーの正負の符号を使用して、長方形を水平方向と垂直方向にスライスして小さな長方形に分割することを記述する。^[7]

分離可能な順列には、パターン 231 を回避する スタック ソート可能な順列という特別なケースが含まれます。

• アッカーマン、エヤル、バレケット、ギル、ピンター、ロン Y. (2006)、「順列とフロアプラン間の一対一対応とその応用」、離散応用数学、154 (12): 1674–1684、doi : 10.1016/j.dam.2006.03.018、MR  2233287
• エイビス、デイビッド、ニューボーン、モンロー(1981)、「ポップスタックのシリーズについて」、Utilitas Mathematica、19 : 129–140、MR  0624050。
• Bouvel, Mathilde; Rossin, Dominique; Vialette, Stéphane (2007)、「順列の中で最長の共通分離可能パターン」、Combinatorial Pattern Matching (CPM 2007)、Lecture Notes in Computer Science、vol. 4580、Springer、pp. 316–327、doi :10.1007/978-3-540-73437-6_32、ISBN 978-3-540-73436-9。
• Bose, Prosenjit ; Buss, Jonathan ; Lubiw, Anna (1998)、「順列のパターンマッチング」、Information Processing Letters、65 (5): 277–283、doi :10.1016/S0020-0190(97)00209-3、MR  1620935。
• Ghys、Étienne (2017)、「特異な数学的プロムナード」、リヨン: ENS Éditions、arXiv : 1612.06373、ISBN 978-2-84788-939-0、MR  3702027
• キタエフ、セルゲイ(2011)、「2.2.5 分離可能な順列」、順列と単語のパターン、理論計算機科学のモノグラフ。EATCS シリーズ、ベルリン: Springer-Verlag、pp. 57–66、doi :10.1007/978-3-642-17333-2、ISBN 978-3-642-17332-5、Zbl  1257.68007。
• シャピロ、ルイス; スティーブンス、アーサー B. (1991)、「ブートストラップパーコレーション、シュレーダー数、およびNキング問題」、SIAM 離散数学ジャーナル、4 (2): 275–280、doi :10.1137/0404025、MR  1093199。
• Szepieniec, AA; Otten, RHJM (1980)、「レイアウト問題への系譜学的アプローチ」、第 17 回設計自動化会議 (DAC 1980)、pp. 535–542、doi :10.1145/800139.804582、ISBN 0-89791-020-6、S2CID  2031785。
• ウェスト、ジュリアン（1995）、「生成木とカタラン数およびシュレーダー数」、離散数学、146（1–3）：247–262、doi：10.1016/0012-365X（94）00067-1、MR  1360119。