En matemáticas , una valla , también llamada zigzag poset , es un conjunto parcialmente ordenado en el que las relaciones de orden forman un camino con orientaciones alternas:
- a < b > c < d > e < f > h < i ...
o
- a > b < c > d < e > f < h > i ...
Una cerca puede ser finita o puede estar formada por una secuencia alterna infinita que se extiende en ambas direcciones. Los posets de incidencia de los gráficos de ruta forman ejemplos de vallas.
Una extensión lineal de una valla se llama permutación alterna ; El problema de André de contar el número de diferentes extensiones lineales se ha estudiado desde el siglo XIX. [1] Las soluciones a este problema de conteo, los llamados números en zigzag de Euler o números arriba / abajo, son
El número de antichains en una cerca es un número de Fibonacci ; la celosía distributiva con tantos elementos, generada a partir de una valla mediante el teorema de representación de Birkhoff , tiene como gráfico el cubo de Fibonacci . [2]
Un conjunto parcialmente ordenado es serie-paralelo si y solo si no tiene cuatro elementos que formen una valla. [3]
Varios autores también han investigado la cantidad de mapas que preservan el orden, desde cercas hasta ellos mismos, o hasta cercas de otros tamaños. [4]
Un arriba-abajo poset Q ( un , b ) es una generalización de un poset zigzag en la que hay unas orientaciones hacia abajo para cada uno hacia arriba y b elementos totales. [5] Por ejemplo, Q (2,9) tiene los elementos y relaciones
- a > b > c < d > e > f < g > h > i .
En esta notación, una cerca es un conjunto parcialmente ordenado de la forma Q (1, n ).
Condiciones equivalentes
Las siguientes condiciones son equivalentes para un poset P : [ cita requerida ]
- P es una unión disjunta de posets en zigzag.
- Si un ≤ b ≤ c en P , o bien un = b o b = c .
- < <= , Es decir, nunca es el caso que un < b y b < c , de modo que
- P tiene una dimensión como máximo uno (definida de forma análoga a la dimensión de Krull de un anillo conmutativo ).
- Cada elemento de P es máximo o mínimo .
- La categoría de corte Pos / P es cartesiana cerrada . [6]
Los ideales primos de un anillo conmutativo R , ordenados por inclusión, satisfacen las condiciones equivalentes anteriores si y solo si R tiene una dimensión de Krull como máximo uno. [ cita requerida ]
Notas
- ↑ André (1881) .
- ↑ Gansner (1982) llama al hecho de que esta celosía tiene un número de elementos de Fibonacci un "hecho bien conocido", mientras que Stanley (1986) pide una descripción de la misma en un ejercicio. Véase también Höft y Höft (1985) , Beck (1990) y Salvi y Salvi (2008) .
- ^ Valdés, Tarjan y Lawler (1982) .
- ^ Currie y Visentin (1991) ; Duffus y col. (1992) ; Rutkowski (1992a) ; Rutkowski (1992b) ; Farley (1995) .
- ^ Gansner (1982) .
- ^ Aquí, Pos denota la categoría de conjuntos parcialmente ordenados.
Referencias
- André, Désiré (1881), "Sur les permutations alternées", J. Math. Pures Appl. , (Ser. 3), 7 : 167-184.
- Beck, István (1990), "Órdenes parciales y los números de Fibonacci", Fibonacci Quarterly , 28 (2): 172-174, MR 1051291.
- Currie, JD; Visentin, TI (1991), "El número de mapas de vallas y coronas que preservan el orden", Orden , 8 (2): 133–142, doi : 10.1007 / BF00383399 , hdl : 10680/1724 , MR 1137906 , S2CID 122356472.
- Duffus, Dwight ; Rödl, Vojtěch; Sands, Bill; Woodrow, Robert (1992), "Enumeration of order preserving maps", Order , 9 (1): 15-29, doi : 10.1007 / BF00419036 , MR 1194849 , S2CID 84180809.
- Farley, Jonathan David (1995), "El número de mapas que conservan el orden entre vallas y coronas", Orden , 12 (1): 5–44, doi : 10.1007 / BF01108588 , MR 1336535 , S2CID 120372679.
- Gansner, Emden R. (1982), "En el entramado de los ideales de orden de un poset arriba-abajo", Discrete Mathematics , 39 (2): 113-122, doi : 10.1016 / 0012-365X (82) 90134-0 , Señor 0675856.
- Höft, Hartmut; Höft, Margret (1985), "Una secuencia de Fibonacci de celosías distributivas", Fibonacci Quarterly , 23 (3): 232-237, MR 0806293.
- Kelly, David; Rival, Ivan (1974), "Coronas, vallas y celosías desmontables", Canadian Journal of Mathematics , 26 (5): 1257-1271, doi : 10.4153 / cjm-1974-120-2 , MR 0417003.
- Rutkowski, Aleksander (1992a), "El número de asignaciones estrictamente crecientes de vallas", Orden , 9 (1): 31–42, doi : 10.1007 / BF00419037 , MR 1194850 , S2CID 120965362.
- Rutkowski, Aleksander (1992b), "La fórmula para el número de automapeos que preservan el orden de una cerca", Orden , 9 (2): 127-137, doi : 10.1007 / BF00814405 , MR 1199291 , S2CID 121879635.
- Salvi, Rodolfo; Salvi, Norma Zagaglia (2008), "Secuencias unimodales alternas de números de Whitney", Ars Combinatoria , 87 : 105-117, MR 2414008.
- Stanley, Richard P. (1986), Combinatoria enumerativa , Wadsworth, Inc. Ejercicio 3.23a, página 157.
- Valdés, Jacobo; Tarjan, Robert E .; Lawler, Eugene L. (1982), "The Recognition of Series Parallel Digraphs", SIAM Journal on Computing , 11 (2): 298–313, doi : 10.1137 / 0211023.
enlaces externos
- Weisstein, Eric W. "Fence Poset" . MathWorld .