Ogrodzenie (matematyka)

Diagram Hassego sześcioelementowego ogrodzenia.

W matematyce płot , zwany także zygzakowatym posetem , jest częściowo uporządkowanym zbiorem ( poset), w którym relacje porządku tworzą ścieżkę o naprzemiennych orientacjach:

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

Lub

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

Ogrodzenie może być skończone lub może być utworzone przez nieskończoną naprzemienną sekwencję rozciągającą się w obu kierunkach. Zestawy częstości występowania wykresów ścieżek stanowią przykłady ogrodzeń.

Liniowe przedłużenie ogrodzenia nazywa się permutacją naprzemienną ; Problem André dotyczący liczenia różnych przedłużeń liniowych był badany od XIX wieku. Rozwiązania tego problemu z liczeniem, tak zwane liczby zygzakowate Eulera lub liczby góra/dół, są następujące:

{\ Displaystyle 1,1,2,4,10,32,122,544,2770,15872,101042.}

(sekwencja A001250 w O EIS ).

Liczba antyłańcuchów w ogrodzeniu to liczba Fibonacciego ; krata rozdzielcza z tak wieloma elementami, wygenerowana z ogrodzenia za pomocą twierdzenia Birkhoffa o reprezentacji , ma za swój wykres sześcian Fibonacciego .

Zbiór częściowo uporządkowany jest szeregowo-równoległy wtedy i tylko wtedy, gdy nie ma czterech elementów tworzących ogrodzenie.

Kilku autorów zbadało również liczbę map porządkowych od ogrodzeń do samych ogrodzeń lub do ogrodzeń o innych rozmiarach.

Pozycja góra-dół $Q (a, b)$ jest uogólnieniem pozycji zygzakowatej, w której istnieje $orientacja w dół dla każdego$ elementu w górę iw sumie $b .$ Na przykład $Q (2,9)$ ma elementy i relacje

{\ Displaystyle a> b> c <d> e> f <g> h> i.}

W tej notacji płot jest częściowo uporządkowanym zbiorem postaci $Q (1, n)$ .

Równoważne warunki

Następujące warunki są równoważne dla poset $P$ : ^{[ potrzebne źródło ]}

$P$ jest rozłączną sumą pozycji zygzakowatych.
Jeśli $za \leq b \leq do$ w $P$ , albo $za = b$ albo $b = do$ .
${\ Displaystyle <\ circ <\; = \ pusty zbiór}$ , tj. nigdy nie jest tak, że $a < b$ i $b < c$ , więc $<$ jest próżniowo przechodnie.
$P$ ma wymiar co najwyżej jeden (zdefiniowany analogicznie do wymiaru Krulla pierścienia przemiennego ).
Każdy element $P$ jest albo maksymalny , albo minimalny .
Kategoria wycinka Pos $/ P jest$ kartezjańsko zamknięta .

Ideały pierwsze przemiennego pierścienia $R$ , uporządkowane przez inkluzję, spełniają powyższe równoważne warunki wtedy i tylko wtedy, gdy $R$ ma wymiar Krulla co najwyżej jeden. ^{[ potrzebne źródło ]}

Notatki

André, Désiré (1881), „Sur les permutations alternées”, J. Math. Pures Appl. , (Ser. 3), 7 , s. 167–184 .
Beck, István (1990), „Zamówienia częściowe i liczby Fibonacciego”, Fibonacci Quarterly , 28 (2): 172–174, MR 1051291 .
Currie, JD; Visentin, TI (1991), „Liczba map zachowujących porządek ogrodzeń i koron”, Order , 8 (2): 133–142, doi : 10.1007/BF00383399 , hdl : 10680/1724 , MR 1137906 , S2CID 122356472 .
Duffus, Dwight ; Rödl, Vojtěch; Piaski, Bill; Woodrow, Robert (1992), „Wyliczenie map zachowujących porządek”, Order , 9 (1): 15–29, doi : 10.1007 / BF00419036 , MR 1194849 , S2CID 84180809 .
Farley, Jonathan David (1995), „Liczba map zachowujących porządek między płotami a koronami”, Order , 12 (1): 5–44, doi : 10.1007 / BF01108588 , MR 1336535 , S2CID 120372679 .
Gansner, Emden R. (1982), „Na siatce ideałów porządku pozycji góra-dół”, Discrete Mathematics , 39 (2): 113–122, doi : 10.1016 / 0012-365X (82) 90134-0 , MR 0675856 .
Höft, Hartmut; Höft, Margret (1985), „Sekwencja Fibonacciego sieci dystrybucyjnych” , Fibonacci Quarterly , 23 (3): 232–237, MR 0806293 .
Kelly, Dawid; Rywal, Ivan (1974), „Korony, ogrodzenia i rozbieralne kraty”, Canadian Journal of Mathematics , 26 (5): 1257–1271, doi : 10,4153 / cjm-1974-120-2 , MR 0417003 .
Rutkowski, Aleksander (1992a), „Liczba ściśle rosnących mapowań ogrodzeń”, Order , 9 (1): 31–42, doi : 10.1007/BF00419037 , MR 1194850 , S2CID 120965362 .
Rutkowski, Aleksander (1992b), „Formuła na liczbę samoodwzorowań ogrodzenia zachowujących porządek”, Order , 9 (2): 127–137, doi : 10.1007/BF00814405 , MR 1199291 , S2CID 121879635 .
Salvi, Rodolfo; Salvi, Norma Zagaglia (2008), „Naprzemienne sekwencje unimodalne liczb Whitneya”, Ars Combinatoria , 87 : 105–117, MR 2414008 .
Stanley, Richard P. (1986), Enumerative Combinatoryics , Wadsworth, Inc. Ćwiczenie 3.23a, strona 157.
Valdes, Jacobo; Tarjan, Robert E .; Lawler, Eugene L. (1982), „Rozpoznawanie dwuznaków równoległych serii”, SIAM Journal on Computing , 11 (2): 298–313, doi : 10.1137/0211023 .

Linki zewnętrzne

Weisstein, Eric W. „Fence Poset” . MathWorld .