Orden cíclica parcial

En matemáticas, un orden cíclico parcial es una relación ternaria que generaliza un orden cíclico de la misma manera que un orden parcial generaliza un orden lineal .

Definición

Sobre un conjunto dado, un orden cíclico parcial es una relación ternaria que es: ${\displaystyle R}$

• cíclico , es decir, es invariante bajo una permutación cíclica : ${\displaystyle R(x,y,z)\Rightarrow R(y,z,x)}$
• asimétrico : ${\displaystyle R(x,y,z)\Rightarrow \not R(z,y,x)}$
• transitivo : y ^[1] ${\displaystyle R(x,y,z)}$ ${\displaystyle R(x,z,u)\Rightarrow R(x,y,u)}$

Construcciones

Suma directa

Producto directo

Poder ^{[2] [3]}

Finalización de Dedekind-MacNeille

Extensiones

extensión lineal , teorema de extensión de Szpilrajn

ejemplo estándar

La relación entre los órdenes cíclicos parciales y totales es más compleja que la relación entre los órdenes lineales parciales y totales. Para empezar, no todo orden cíclico parcial puede extenderse a un orden cíclico total. Un ejemplo es la siguiente relación sobre las primeras trece letras del alfabeto: { acd, bde, cef, dfg, egh, fha, gac, hcb } ∪ { abi, cij, bjk, ikl, jlm, kma, lab, mbc }. Esta relación es un orden cíclico parcial, pero no puede extenderse ni con abc ni con cba ; cualquiera de los dos intentos resultaría en una contradicción. ^[4]

El ejemplo anterior es relativamente leve. También se pueden construir órdenes cíclicos parciales con obstrucciones de orden superior, de modo que, por ejemplo, se puedan sumar 15 triples cualesquiera, pero no el 16.°. De hecho, el ordenamiento cíclico es NP-completo , ya que resuelve 3SAT . Esto contrasta marcadamente con el problema de reconocimiento de órdenes lineales, que se puede resolver en tiempo lineal . ^{[5] [6]}

Notas

1. Noviembre 1982.
2. Novák y Novotný 1984a.
3. Novák y Novotný 1984b.
4. Megiddo 1976, págs. 274-275.
5. Megiddo 1976, págs. 275–276.
6. Galil y Megido 1977, pág. 179.

Referencias

• Galil, Zvi ; Megiddo, Nimrod (octubre de 1977), "El ordenamiento cíclico es NP-completo" (PDF) , Theoretical Computer Science , 5 (2): 179–182, doi : 10.1016/0304-3975(77)90005-6 , consultado el 30 de abril de 2011
• Megiddo, Nimrod (marzo de 1976), "Órdenes cíclicas parciales y completas" (PDF) , Bulletin of the American Mathematical Society , 82 (2): 274–276, doi : 10.1090/S0002-9904-1976-14020-7 , consultado el 30 de abril de 2011
• Novák, Vítězslav (1982), "Conjuntos ordenados cíclicamente" (PDF) , Checoslovak Mathematical Journal , 32 (3): 460–473, doi : 10.21136/CMJ.1982.101821 , hdl :10338.dmlcz/101821 , consultado el 30 de abril de 2011
• Novák, Vítězslav; Novotný, Miroslav (1984a), "Sobre una potencia de conjuntos ordenados cíclicamente" (PDF) , Časopis Pro Pěstování Matematiky , 109 (4): 421–424, doi : 10.21136/CPM.1984.118209 , hdl :10338.dmlcz/118209 , recuperado el 30 de abril de 2011
• Novák, Vítězslav; Novotný, Miroslav (1984b), "Conjuntos universales ordenados cíclicamente" (PDF) , Checoslovak Mathematical Journal , 35 (1): 158–161, doi : 10.21136/CMJ.1985.102004 , hdl :10338.dmlcz/102004 , consultado el 30 de abril de 2011

Lectura adicional

• Alles, Peter; Nešetřil, Jaroslav; Poljak, Svatopluck (1991), "Extensibilidad, dimensiones y diagramas de órdenes cíclicos", SIAM Journal on Discrete Mathematics , 4 (4): 453–471, doi :10.1137/0404041
• Bandelt, Hans–Jürgen; Chepoi, Victor; Eppstein, David (2010), "Combinatoria y geometría de grafos cuadrados finitos e infinitos" (PDF) , SIAM Journal on Discrete Mathematics , 24 (4): 1399–1440, arXiv : 0905.4537 , doi :10.1137/090760301, S2CID  10788524 , consultado el 23 de mayo de 2011
• Chajda, Iván; Novák, Vítězslav (1985), "Sobre extensiones de órdenes cíclicas" (PDF) , Časopis Pro Pěstování Matematiky , 110 (2): 116–121, doi : 10.21136/CPM.1985.108597 , hdl :10338.dmlcz/108597 , recuperado 30 abril 2011
• Fishburn, PC ; Woodall, DR (junio de 1999), "Órdenes de ciclo", Orden , 16 (2): 149–164, doi :10.1023/A:1006381208272, S2CID  37680085
• Haar, Stefan (2001), "Modelos cíclicos y de orden parcial para concurrencia" (PDF) , Geometría y topología en la teoría de la concurrencia GETCO '01 , págs. 51–62 , consultado el 23 de mayo de 2011
• Ille, Pierre; Ruet, Paul (30 de abril de 2008), "Extensiones cíclicas de variedades de orden", 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), "Sobre órdenes cíclicas extendidas" (PDF) , Checoslovak Mathematical Journal , 44 (4): 661–675, doi : 10.21136/CMJ.1994.128486 , hdl :10338.dmlcz/128486 , consultado el 30 de abril de 2011
• Melliès, Paul-André (2004), "Un criterio de corrección topológica para la lógica no conmutativa" (PDF) , en Thomas Ehrhard y Jean-Yves Girard y Paul Ruet y Philip Scott (ed.), Lógica lineal en la informática , pp. 283–323 , consultado el 23 de mayo de 2011
• Novák, Vítězslav (1984), "Sobre algún problema mínimo" (PDF) , Archivum Mathematicum , 20 (2): 95–99, hdl :10338.dmlcz/107191, MR  0784860, Zbl  0554.06003 , consultado el 23 de mayo de 2011
• Stehr, Mark-Oliver (1998), "Pensar en ciclos", en Desel, Jörg; Silva, Manuel (eds.), ICATPN '98 Proceedings of the 19th International Conference on Application and Theory of Petri Nets , Lecture Notes in Computer Science, vol. 1420, págs. 205–225, doi :10.1007/3-540-69108-1_12, ISBN 3-540-64677-9
• Haar, Stefan (2016), "Ordenamiento cíclico a través de órdenes parciales" (PDF) , Journal of Multiple-Valued Logic and Soft Computing , 27 (2–3), Old City Publishing: 209–228