Częściowy porządek cykliczny

W matematyce częściowy porządek cykliczny jest relacją trójskładnikową , która uogólnia porządek cykliczny w taki sam sposób, w jaki porządek częściowy uogólnia porządek liniowy .

Definicja

W danym zbiorze częściowy porządek cykliczny jest relacją trójskładnikową, czyli: ${\ displaystyle R}$

• cykliczny , tj. jest niezmienny w cyklicznej permutacji : ${\ Displaystyle R (x, y, z) \ Strzałka w prawo R (y, z, x)}$
• asymetryczny : ${\ Displaystyle R (x, y, z) \ Strzałka w prawo \ nie R (z, y, x)}$
• przechodni : ${\ Displaystyle R (x, y, z)}$ i ${\ Displaystyle R (x, z, u )\Strzałka w prawo R(x,y,u)}$

Konstrukcje

Suma bezpośrednia

Produkt bezpośredni

Moc

Zakończenie Dedekinda-MacNeille'a

Rozszerzenia

rozciągłość liniowa , twierdzenie Szpilrajna o rozciągłości

standardowy przykład

Zależność między częściowymi i całkowitymi rzędami cyklicznymi jest bardziej złożona niż zależność między częściowymi i całkowitymi rzędami liniowymi. Zacznijmy od tego, że nie każdy częściowy porządek cykliczny można rozszerzyć do całkowitego porządku cyklicznego. Przykładem jest następująca relacja dotycząca pierwszych trzynastu liter alfabetu: { acd, bde, cef, dfg, egh, fha, gac, hcb } ∪ { abi, cij, bjk, ikl, jlm, kma, lab, mbc }. Relacja ta jest częściowym porządkiem cyklicznym, ale nie można jej rozszerzyć ani o abc , ani o cba ; każda próba skutkowałaby sprzecznością.

Powyższe było stosunkowo łagodnym przykładem. Można również skonstruować częściowe rzędy cykliczne z przeszkodami wyższego rzędu, tak że na przykład można dodać dowolne 15 trójek, ale nie można dodać szesnastej. W rzeczywistości porządkowanie cykliczne jest NP-zupełne , ponieważ rozwiązuje 3SAT . Stoi to w wyraźnej sprzeczności z problemem rozpoznawania rzędów liniowych, który można rozwiązać w czasie liniowym .

Notatki

• Galil, Cwi ; Megiddo , Nimrod ( październik 1977 ) _ _ _ _ _ _ _ 2011
• Megiddo , Nimrod ( marzec 1976 ) _ _ _ _ _ _ 30 kwietnia 2011 r
• Novák, Vítězslav (1982), „Zestawy uporządkowane cyklicznie” (PDF) , Czechoslovak Mathematical Journal , 32 (3): 460–473, doi : 10.21136 /CMJ.1982.101821 , hdl : 10338.dmlcz/101821 , dostęp 30 kwietnia 2011 r .
• Novák, Vítězslav; Novotný, Miroslav (1984a), „O potędze zbiorów cyklicznie uporządkowanych” (PDF) , Časopis Pro Pěstování Matematiky , 109 (4): 421–424, doi : 10.21136/CPM.1984.118209 , hdl : 10338.dmlcz/118209 , pobrane 30 kwietnia 2011 r
• Novák, Vítězslav; Novotný , Miroslav ( 1984b ) _ _ _ _ _ _ _ _ _ _ _ _

Dalsza lektura

• Alles, Piotr; Nešetřil, Jaroslav; Poljak, Svatopluck (1991), „Rozszerzalność, wymiary i diagramy rzędów cyklicznych”, SIAM Journal on Discrete Mathematics , 4 (4): 453–471, doi : 10,1137/0404041
•   Bandelt, Hans-Jürgen; Chepoi, Victor; Eppstein, David (2010), „Kombinatoryka i geometria skończonych i nieskończonych wykresów kwadratowych” (PDF) , SIAM Journal on Discrete Mathematics , 24 (4): 1399–1440, arXiv : 0905,4537 , doi : 10,1137/090760301 , S2CID 10788524 , pobrane 23 maja 2011 r
• Chajda, Iwan; Novák, Vítězslav (1985), „O przedłużeniu zleceń cyklicznych” (PDF) , Časopis Pro Pěstování Matematiky , 110 (2): 116–121, doi : 10.21136/CPM.1985.108597 , hdl : 10338.dmlcz/108597 , pobrane 30 kwietnia 2011 r
•   Fishburn, PC ; Woodall, DR (czerwiec 1999), „Cycle Orders”, Order , 16 (2): 149–164, doi : 10.1023 / A: 1006381208272 , S2CID 37680085
• Haar, Stefan (2001), „Cyclic and parts order models for concurrency” (PDF) , Geometry and Topology in Concurrency Theory GETCO '01 , s. 51–62 , dostęp 23 maja 2011 r.
•   Ille, Pierre; Ruet, Paul (30 kwietnia 2008), „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), „O rozszerzonych zamówieniach cyklicznych” (PDF) , Czechosłowacki Mathematical Journal , 44 (4): 661–675, doi : 10.21136 /CMJ.1994.128486 , hdl : 10338.dmlcz/128486 , dostęp 30 kwietnia 2011 r.
• Melliès, Paul-André (2004), „A topologiczne kryterium poprawności dla logiki nieprzemiennej” (PDF) , w Thomas Ehrhard i Jean-Yves Girard oraz Paul Ruet i Philip Scott (red.), Linear Logic in Computer Science , s. 283–323 , dostęp 23 maja 2011 r.
•    Novák, Vítězslav (1984), „O pewnym minimalnym problemie” (PDF) , Archivum Mathematicum , 20 (2): 95–99, hdl : 10338.dmlcz/107191 , MR 0784860 , Zbl 0554.06003 , dostęp 23 maja 2011
•   Stehr, Mark-Oliver (1998), „Myślenie w cyklach”, w: Desel, Jörg; Silva, Manuel (red.), ICATPN '98 Proceedings of the 19th International Conference on Application and Theory of Petri Nets , Lecture Notes in Computer Science, tom. 1420, s. 205–225, doi : 10.1007/3-540-69108-1_12 , ISBN 3-540-64677-9
• Haar, Stefan (2016), „Cyclic Ordering through Partial Orders” (PDF) , Journal of Multiple-Valued Logic and Soft Computing , Old City Publishing, 27 (2–3): 209–228