Valla (matemáticas)

En matemáticas , una valla , también llamada conjunto en zigzag , es un conjunto parcialmente ordenado (conjunto) en el que las relaciones de orden forman un camino con orientaciones alternas:

a<b>c<d>e<f>h<i\cdots

o

a>b<c>d<e>f<h>i\cpuntos

Una valla puede ser finita o puede estar formada por una secuencia alterna infinita que se extiende en ambas direcciones. Los conjuntos de elementos de incidencia de los grafos de trayectorias forman ejemplos de vallas.

Una extensión lineal de una cerca se llama permutación alternada ; el problema de André de contar el número de extensiones lineales diferentes 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:

1,1,2,4,10,32,122,544,2770,15872,101042.

(secuencia A001250 en la OEIS ).

El número de anticadenas en una cerca es un número de Fibonacci ; la red distributiva con esta cantidad de elementos, generada a partir de una cerca 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 sólo si no tiene cuatro elementos que formen una cerca. ^[3]

Varios autores también han investigado el número de mapas que preservan el orden de las vallas hacia ellas mismas o hacia vallas de otros tamaños. ^[4]

Un poset arriba-abajo $Q (a, b)$ es una generalización de un poset en zigzag en el que hay $a$ orientaciones hacia abajo para cada uno hacia arriba y $b$ elementos en total. ^[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)$ .

Referencias

^ André (1881).
^ Gansner (1982) considera que el hecho de que esta red tenga un número de Fibonacci de elementos es un “hecho bien conocido”, mientras que Stanley (1986) pide una descripción del mismo 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 cols. (1992); Rutkowski (1992a); Rutkowski (1992b); Farley (1995).
^ Gansner (1982).

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 cercas y coronas que preservan el orden", Order , 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), "Enumeración de mapas que preservan el orden", Order , 9 (1): 15–29, doi :10.1007/BF00419036, MR 1194849, S2CID 84180809.
Farley, Jonathan David (1995), "El número de mapas que preservan el orden entre cercas y coronas", Order , 12 (1): 5–44, doi :10.1007/BF01108588, MR 1336535, S2CID 120372679.
Gansner, Emden R. (1982), "Sobre la red de ideales de orden de un conjunto parcial arriba-abajo", Discrete Mathematics , 39 (2): 113–122, doi : 10.1016/0012-365X(82)90134-0 , MR 0675856.
Höft, Hartmut; Höft, Margret (1985), "Una secuencia de Fibonacci de redes distributivas", Fibonacci Quarterly , 23 (3): 232–237, MR 0806293.
Kelly, David; Rival, Ivan (1974), "Coronas, cercas y celosías desmontables", Revista Canadiense de Matemáticas , 26 (5): 1257–1271, doi : 10.4153/cjm-1974-120-2 , MR 0417003.
Rutkowski, Aleksander (1992a), "El número de asignaciones de cercas estrictamente crecientes", Order , 9 (1): 31–42, doi :10.1007/BF00419037, MR 1194850, S2CID 120965362.
Rutkowski, Aleksander (1992b), "La fórmula para el número de autoasignaciones que preservan el orden de una cerca", Order , 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.
Valdes, Jacobo; Tarjan, Robert E.; Lawler , Eugene L. (1982), "El reconocimiento de dígrafos paralelos en serie", SIAM Journal on Computing , 11 (2): 298–313, doi :10.1137/0211023.

Enlaces externos

Weisstein, Eric W. "Poset de vallas". MathWorld .

[1] André (1881).

[2] Gansner (1982) considera que el hecho de que esta red tenga un número de Fibonacci de elementos es un “hecho bien conocido”, mientras que Stanley (1986) pide una descripción del mismo en un ejercicio. Véase también Höft y Höft (1985), Beck (1990) y Salvi y Salvi (2008).

[3] Valdés, Tarjan y Lawler (1982).

[4] Currie y Visentin (1991); Duffus y cols. (1992); Rutkowski (1992a); Rutkowski (1992b); Farley (1995).

[5] Gansner (1982).