部分循環順序

数学において、部分巡回順序は、部分順序が線形順序を一般化するのと同じように巡回順序を一般化する三元関係です。

与えられた集合において、部分巡回順序とは次のような三項関係である。 ${\displaystyle R}$

• 巡回的、つまり巡回置換に対して不変である:${\displaystyle R(x,y,z)\Rightarrow R(y,z,x)}$
• 非対称:${\displaystyle R(x,y,z)\Rightarrow \not R(z,y,x)}$
• 他動詞：そして^[1]${\displaystyle R(x,y,z)}$${\displaystyle R(x,z,u)\Rightarrow R(x,y,u)}$

直和

直接製品

パワー^{[2] [3]}

デデキント・マクニール完成

線型拡張、シュピルライン拡張定理

標準的な例

部分循環順序と全循環順序の関係は、部分線形順序と全線形順序の関係よりも複雑です。まず、すべての部分循環順序を全循環順序に拡張できるわけではありません。例として、アルファベットの最初の13文字の関係を示します。{ acd, bde, cef, dfg, egh, fha, gac, hcb } ∪ { abi, cij, bjk, ikl, jlm, kma, lab, mbc }。この関係は部分循環順序ですが、abcまたはcbaで拡張することはできません。どちらの試みも矛盾が生じます。^[4]

上記は比較的穏やかな例です。また、より高次の障害を伴う部分的な巡回順序を構築することもできます。たとえば、任意の 15 個の 3 組を追加できますが、16 番目は追加できません。実際、巡回順序は3SAT を解くため、NP 完全です。これは、線形時間で解くことができる線形順序の認識問題とはまったく対照的です。^{[5] [6]}