部分巡回順序

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

意味

与えられた集合において、部分巡回順序とは次のような三項関係である。 ${\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個の三つ組は加算できるが、16個目は加算できないといった具合です。実際、巡回順序は3SATを解くため、NP完全です。これは、線形時間で解ける線形順序の認識問題とは著しく対照的です。^{[5] [6]}

注記

1. ノヴァク 1982.
2. Novák & Novotný 1984a.
3. Novák & Novotný 1984b.
4. メギド 1976、274–275 ページ。
5. メギド 1976、275–276 ページ。
6. ガリルとメギド 1977、p. 179.

参考文献

• Galil, Zvi ; Megiddo, Nimrod (1977年10月)、「巡回順序はNP完全である」(PDF)、理論計算機科学、5 (2): 179– 182、doi : 10.1016/0304-3975(77)90005-6 、 2011年4月30日閲覧
• Megiddo, Nimrod (1976年3月)、「部分巡回順序と完全巡回順序」(PDF)、米国数学会報、82 (2): 274– 276、doi : 10.1090/S0002-9904-1976-14020-7 、 2011年4月30日閲覧。
• Novák、Vítězslav (1982)、「巡回順序集合」(PDF)、チェコスロバキア数学ジャーナル、32 (3): 460–473、doi : 10.21136/CMJ.1982.101821、hdl :10338.dmlcz/101821 、2011 年4 月 30 日に取得
• ノヴァーク、ヴィテズスラフ。 Novotný、Miroslav (1984a)、「巡回順序セットの累乗について」(PDF)、Časopis Pro Pěstování Matematiky、109 (4): 421–424、doi : 10.21136/CPM.1984.118209、hdl :10338.dmlcz/118209、2011年4 月 30 日に取得
• ノヴァーク、ヴィテズスラフ。 Novotný、Miroslav (1984b)、「Universal cyclally順序集合」(PDF)、Czechoslovak Mathematical Journal、35 (1): 158–161、doi : 10.21136/CMJ.1985.102004、hdl :10338.dmlcz/102004 、取得済み2011 年4 月 30 日

さらに読む

• アレス、ピーター。Nešetřil, ヤロスラフ州; Poljak、Svatopluk (1991)、「Extendability, Dimensions, and Diagrams of Cyclic Orders」、離散数学に関する SIAM Journal、4 (4): 453–471、doi :10.1137/0404041
• Bandelt, Hans–Jürgen; Chepoi, Victor; Eppstein, David (2010)「有限および無限平方グラフの組合せ論と幾何学」(PDF)、SIAM Journal on Discrete Mathematics、24 (4): 1399– 1440、arXiv : 0905.4537、doi :10.1137/090760301、S2CID  10788524 、 2011年5月23日閲覧
• チャジダ、イワン。 Novák, Vítězslav (1985)、「周期的命令の拡張について」(PDF)、Časopis Pro Pěstování Matematiky、110 (2): 116–121、doi : 10.21136/CPM.1985.108597、hdl :10338.dmlcz/108597、2011年4 月 30 日に取得
• フィッシュバーン, PC ; ウッドオール, DR (1999年6月)、「サイクル・オーダー」、オーダー、16 (2): 149– 164、doi :10.1023/A:1006381208272、S2CID  37680085
• Haar, Stefan (2001)、「並行性のための巡回的および半順序モデル」(PDF)、並行性理論における幾何学と位相GETCO '01、pp.  51– 62 、 2011年5月23日閲覧。
• イル、ピエール。 Ruet, Paul (2008 年 4 月 30 日)、「Cyclic Extensions of Order Varieties」、Electronic Notes in Theoretical Computer Science、212 : 119–132、CiteSeerX  10.1.1.103.2305、doi :10.1016/j.entcs.2008.04.057
• Jakubík, Ján (1994)、「拡張循環順序について」(PDF)、チェコスロバキア数学ジャーナル、44 (4): 661–675、doi : 10.21136/CMJ.1994.128486、hdl :10338.dmlcz/128486 、取得済み2011 年4 月 30 日
• メリエス、ポール＝アンドレ（2004）「非可換論理の位相的正しさの基準」（PDF）、トーマス・エアハルト、ジャン＝イヴ・ジラール、ポール・ルエット、フィリップ・スコット（編）『線形論理とコンピュータサイエンス』、pp.  283– 323 、2011年5月23日閲覧。
• Novák, Vítězslav (1984)、「いくつかの最小限の問題について」(PDF)、Archivum Mathematicum、20 (2): 95–99、hdl :10338.dmlcz/107191、MR  0784860、Zbl  0554.06003、2011年5 月 23 日取得
• Stehr, Mark-Oliver (1998)、「Thinking in Cycles」、Desel, Jörg、Silva, Manuel (編)、ICATPN '98 Proceedings of the 19th International Conference on Application and Theory of Petri Nets、Lecture Notes in Computer Science、vol. 1420、pp.  205– 225、doi :10.1007/3-540-69108-1_12、ISBN 3-540-64677-9
• Haar, Stefan (2016)、「部分順序による巡回順序付け」(PDF)、Journal of Multiple-Valued Logic and Soft Computing、27 ( 2– 3)、Old City Publishing: 209– 228